Slide 1
Unrestricted Grammars
Chapter 23
Grammars, SD Languages, and Turing Machines
SD Language
Grammar
Turing Machine
L
Accepts
Unrestricted Grammars
An unrestricted grammar G is a quadruple
(V, , R, S), where:
● V is an alphabet,
● (the set of terminals) is a subset of V,
● R (the set of rules) is a finite subset of (V+ V*),
● S (the start symbol) is an element of V – .
The language generated by G is:
{w * : S G* w}.
Unrestricted Grammars
Example: AnBnCn = {anbncn, n 0}.
S aBSc
S
Ba aB
Bc bc
Bb bb
Proof:
● Only strings in AnBnCn :
● All strings in AnBnCn :
Another Example
{w {a, b, c}* : #a(w) = #b(w) = #c(w)}
S ABCS
S
AB BA
BA AB
BC CB
CB BC
AC CA
CA AC
A a
B b
C c
WW = {ww : w {a, b}*}
Idea:
Generate a string in wwR, plus delimiters
aaabbCbbaaa#
Reverse the second half.
WW = {ww : w {a, b}*}
S T# /* Generate the wall exactly once.
T aTa /* Generate wCwR.
T bTb
T C
C CP /* Generate a pusher P
Paa aPa /* Push one character to the right
Pab bPa to get ready to jump.
Pba aPb
Pbb bPb
Pa# #a /* Hop a character over the wall.
Pb# #b
C#
Equivalence of Unrestricted Grammars and Turing Machines
Theorem: A language is generated by an unrestricted
grammar if and only if it is in SD.
Proof:
Only if (grammar TM): by construction of an NDTM.
If (TM grammar): by construction of a grammar that
mimics the behavior of a semideciding TM.
Given G, produce a Turing machine M that semidecides L(G).
M will be nondeterministic and will use two tapes:
Grammar Turing Machine
For each nondeterministic “incarnation”:
● Tape 1 holds the input.
● Tape 2 holds the current state of a proposed derivation.
At each step, M nondeterministically chooses a rule to try to apply
and a position on tape 2 to start looking for the left-hand side of the
rule. Or it chooses to check whether tape 2 equals tape 1. If any
such machine succeeds, we accept. Otherwise, we keep looking.
q a b a b q q
q 1 0 0 0 0 0 0 q
a S T a a b q
1 0 0 0 0 0 0
Turing Machine Grammar
Build G to simulate the forward operation of a TM M:
The first (generate) part of G:
Create all strings over * of the form:
w = # q q q000 a1 a1 a2 a2 a3 a3 q q #
(Blue copy to store for later, red copy to simulate M on.)
The second (test) part of G simulates the execution of M on a particular string w (the red copy). An example of a partially derived string:
# q q a 1 b 2 c c b 4 q001 a 3 #
Examples of rules:
q100 b b b 2 q101
a a q011 b 4 q011 a a b 4
The Last Step
The third (cleanup) part of G erases the working part if M
ever reaches any of its accepting states, all of which will
be encoded as A. The saved input string is then generated by the grammar (because it was accepted by M).
Rules:
z z A A z /* Sweep A to the left.
x, y #A x y x #A /* Erase working part #A#
● Given a grammar G and a string w, is w L(G)?
● Given a grammar G, is L(G)?
● Given two grammars G1 and G2, is L(G1) = L(G2)?
● Given a grammar G, is L(G) = ?
Or, as languages:
● La = {
● L = {
● L= = {
● L = {
None of these questions is decidable.
Decision Problems for Unrestricted Grammars
Proof: Let R be a mapping reduction from:
A = {
R(
1. From M, construct the description
such that L(G#) = L(M).
2. Return
If Oracle decides La, then C = Oracle(R(
have already defined an algorithm that implements R. C is correct:
● If
Oracle(
● If
Oracle(
But no machine to decide A can exist, so neither does Oracle.
La = {