Which of the following is a correct PDA constructed from grammar S -> c | aSb? A

Question

Which of the following is a correct PDA constructed from grammar S -> c | aSb?
A. (0, , S, <pop, push(b), push(S), push(a)>, 0)
B. (0, a, a, pop, 0)
(0, b, b, pop, 0)
(0, c, c, pop, 0)
(0, , S, <pop, push(b), push(S), push(a)>, 0)
(0, , S, <pop, push(c)>, 0).
C. (0, a, a, pop, 0)
(0, b, b, pop, 0)
(0, c, c, pop, 0)
(0, , S, <pop, push(a), push(S), push(b)>, 0)
(0, , S, <pop, push(c)>, 0)
D. (0, a, a, pop, 0)
(0, b, b, pop, 0)
(0, c, c, pop, 0)
(0, , S, <push(b), push(S), push(a)>, 0)
(0, , S, push(c), 0)

Explanation / Answer

The correct answer for the follwing Push Down Automata:

B. (0, a, a, pop, 0)
(0, b, b, pop, 0)
(0, c, c, pop, 0)
(0, , S, <pop, push(b), push(S), push(a)>, 0)
(0, , S, <pop, push(c)>, 0).

Here, in the above question we have to create a push down automata for grammar:

S -> c

S -> aSb

Explanation:

1) Initially the stack is empty and hence it will contain null.

From the terminals a and b we will use algorithm to create the two instructions:

(0, a, a, pop, 0)
(0, b, b, pop, 0)
(0, c, c, pop, 0)

From the production S -> aSb we will use the algorithm to create the instruction

(0, , S, <pop, push(b), push(S), push(a)>, 0)
(0, , S, <pop, push(c)>, 0).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.