Member Avatar for now how abt tht

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?

  • 2 Contributors
  • 3 Replies
  • 270 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by TrustyTony

Dani AI

Generated

Short answer: the observation is correct — only the production that routes the computation into q1 (so that the pop-phase can begin and the bottom marker can be popped) is needed. The reason is structural: every push happens while the machine is in q0, the single transition that switches to q1 (the read-c) leaves the stack unchanged, and all popping (including the final pop of the bottom marker) is done in q1. There is no transition that pops in q0 or that returns from q1 to q0, so any nonterminal whose target state is q0 cannot derive a terminal string.

A quick, systematic way to see which productions survive:

  • Treat a variable [p X q] as "strings that take the PDA from state p with X on top to state q with X removed."
  • Initialize the set of generating nonterminals with those that directly produce terminals (here the ones that both start and end in q1 — they perform the actual pops).
  • Repeatedly add any [p X q] that has a production whose right-hand nonterminals are all already generating.
  • At the end, remove every nonterminal and production that was never marked.

Because the only base generators are the q1 -> q1 pop variables, every marked variable ends in q1. That kills any production you listed whose RHS requires a nonterminal ending in q0. As @nowhowabtht already noted, a return from q1 to q0 by popping the bottom symbol is impossible in this PDA; was right to call it a pushdown automaton and the grammar a CFG. If the PDA were changed to allow pops in q0 or a path back to q0, some of the eliminated productions would become necessary.

Recommended Answers

All 3 Replies

Member Avatar for TrustyTony

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

Edited by TrustyTony because: n/a
Member Avatar for now how abt tht

It is pushdown automaton!!

Member Avatar for TrustyTony

Ok, in this case logically the configuration (CFG) is a Context Free Grammar.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.