for the PDA:


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?

6 Years
Discussion Span
Last Post by pyTony

I do not know about your Personal Digital Assistant to answer this question. Or you mean Pennsylvania Dentist Association:-/

Edited by pyTony: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.