CODEWITHSUNDEEP
context-free-grammarautomatapushdown-automaton
nimbudew
nimbudew

Reputation: 978

Why is this not CFG?

Though this is a repitition of this, I talking in terms of designing a PDA.

Now, I know I'm wrong, because this is a well publicised example, but where did I go wrong in the PDA design below?

I want to accept language {a^n b^n c^n: n>=0}

I push two 1's on the stack every time I encounter an a, pop one for b and pop one for c and check if I have an empty stack. I defined the transition functions (minimal) as:

(q0, a, Z) = (q0, 11Z)
(q0, a, 1) = (q0, 111)
(q0, b, 1) = (q1, delta)
(q1, c, 1) = (q2, delta)
(q2, delta, Z) = (q-Final, Z) (epsilon move)

Z is empty stack

Doesn't this PDA accept such a language?

Upvotes: 0

Views: 243

Answers (1)

Alex DiCarlo
Alex DiCarlo

Reputation: 4891

Your PDA accepts the language:

{a^n b^i c^j; n >= 0 and i + j = 2n}

Which is not the same as {a^n b^n c^n: n>=0}, a subset of the above language, specifically when i = n and j = n.

Upvotes: 1

Related Questions