for the PDA:
d=delta
d(q0,a,Z) = {(q0,AZ)}
d(q0,b,Z) = {(q0,BZ)}
d(q0,a,A) = {(q0,AA)}
d(q0,b,A) = {(q0,BA)}
d(q0,a,B) = {(q0,AB)}
d(q0,b,B) = {(q0,BB)}
d(q0,c,Z) = {(q1,Z)}
d(q0,c,A) = {(q1,A)}
d(q0,c,B) = {(q1,B)}
d(q1,a,A) = {(q1,e)}
d(q1,b,B) = {(q1,e)}
d(q1,e,Z0) = {(q1,e)}
the cfg rules are:
S -> [q0 Z q]
[q0 Z q] -> a[q0 A p] [p Z q]
[q0 Z q]-> b[q0 B p] [p Z q]
[q0Aq] -> a[q0Ap] [pAq]
[q0Aq] -> b[q0Bp] [pAq]
[q0Bq] -> a[q0Ap] [pBq]
[q0Bq] -> b[q0Bp] [pBq]
[q0Zq] -> c[q1Zq]
[q0Aq] -> c[q1Aq]
[q0Bq] -> c[q1Bq]
[q1Aq1] -> a
[q1Bq1] -> b
[q1Z0q1] -> e
where p and q can take any of q0 or q1
after removing unnecessary rules we shd get:
S -> [q0Z0q1]
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]
[q0 Z q1] -> b[q0 B q1] [q1 Z q1]
[q0 A q1] -> a[q0 A q1] [q1 A q1]
[q0 A q1] -> b[q0 B q1] [q1 A q1]
[q 0B q1] -> a[q0Aq1] [q1Bq1]
[q0Bq1] -> b[q0Bq1] [q1Bq1]
[q0Zq1] -> c[q1Zq1]
[q0Aq1] -> c[q1Aq1]
[q0Bq1] -> c[q1Bq1]
[q1Aq1] -> a
[q1Bq1] -> b
[q1Zq1] -> e
my question:
of these:
[q0 Z q0] -> a[q0 Aq 0] [q0 Z q0]
[q0 Z q0] -> a[q0 A q1] [q1 Z q0]
[q0 Z q1] -> a[q0 A q0] [q0 Z q1]
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]
only :
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]
is necessary the rest are not.
i understand
[q0 Z q0] -> a[q0 A q1] [q1 Z q0]
is not possible as u cannot go from q1 to q0 by popping Z.
but y are rest not necessary?
