CODEWITHSUNDEEP
theorycontext-free-grammarautomatapushdown-automatonautomata-theory
Dan9993
Dan9993

Reputation: 1

Converting a Context-Free Grammar to a PDA

I am attempting to convert the following CFG to a pushdown automaton:

S → AS | A
A → 0A | 1B | 1
B → 0B | 0

I'm not really sure how to approach this problem, or the problem of CFG->PDA in general.

Upvotes: 0

Views: 2800

Answers (2)

Dinesh Kandregula
Dinesh Kandregula

Reputation: 11

Conversation of Context free grammar to Pushdown automata: Steps to convert CFG to Pushdown automata: Step-1:The first symbol on R.H.S. production must be a terminal symbol.

Step-2:Convert the given productions of CFG into GNF.

Step-3:The PDA will only have one state {q}.

Step-4:The initial symbol of CFG will be the initial symbol in the PDA.

Step-5:For non-terminal symbol, add the following rule: δ(q, ε, A) = (q, α)
Where the production rule is A → α.

Step-6:For each terminal symbols, add the following rule: δ(q, a, a) = (q, ε) for every terminal symbol

Upvotes: 1

RobertoCSantosRJ
RobertoCSantosRJ

Reputation: 646

You may use JFlap application to do it for you. http://www.jflap.org/ Beyond this there are several other interesting functionalyties in that application that will help you study formal languages. I've been using it for about two weeks and I'm loving it.

Upvotes: 0

Related Questions