To precisely define the language A, we first define the context-free grammar G =

Question

To precisely define the language A, we first define the context-free grammar G =
(V, S, R, S), where V = {S, T, X, Y },
= { a, b, c, . . . , z, +, -, *, /, (, ), $ }, (1)
the starting variable is S, and the rules are
S -> $T $
T -> T +T | T -T | T *T | T /T | (T ) | X
X -> Y | Y Y
Y -> a | b | c | • • • | z
Note that you cannot use the algorithm in Lemma 2.21 to convert the CFG G into a PDA
for A since the resulting PDA will not satisfy the last four properties above. However,
those properties ensure that the PDA M is essentially deterministic, so once you figure
out M, it will be easy to implement as a program. (Implementing a nondeterministic
machine is more difficult since the program needs to check every branch in the tree of
computation.)

Must be done deterministic.

Explanation / Answer

Transform CFG into Greibach normal form

Than write production or transition rule for each non terminal and their corresponding production.

There will be two state q0 and q1 .

In q0 read empty string and puch start symbol S in stack and go to state q1

Now write transition for each terminal while on of the non terminal at top.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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