79196057

Date: 2024-11-16 21:17:34
Score: 1
Natty:
Report link

Given some CFG with start S you want to be able to add the start S to the PDA's stack only once because if you "Push S onto the empty stack by empty transition to sef" then you can push infinetly many S which is no longer the same language. i.e. this wouldnt work : (q,ε,ε) ->(q, S)

So the trick is to have the transtion:

(q,ε,$) ->(q, SZ)

where $ is the start bottom stack symbol and Z is some dummy variable that will be used as the new bottom stack symbol. This disallows you from re-suing the above transition more than once. Now for every production A -> x where x can be any combination of symbols or variables you have:

(q,ε,A) -> (q,x)

For every symbol c you must also have: (q,ε,c) -> (q,c)

Lastly, a transtion to the accepting state q1 can be added

(q,ε,Z) -> (q1,Z)

Which enforces the stack to be empty before going to the accept state. This creates a PDA with two states for any CFG

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (1):
Posted by: David Ruiz