<p>To precisely define the language A, we first define the con
ID: 3632491 • Letter: #
Question
<p>To precisely define the language A, we first define the context-free grammar G =(V, Σ, R, S), where V = {S, T, X, Y },</p><p>Σ = { a, b, c, . . . , z, +, −, ∗, /, (, ), $ },</p>
<p>(1)the starting variable is S, and the rules are</p>
<p>S → $T $</p>
<p>T → T +T | T -T | T *T | T /T | (T ) | X</p>
<p>X → Y | Y Y</p>
<p>Y → a | b | c | · · · | z</p>
<p> </p>
<p>Note that you cannot use the algorithm in Lemma 2.21 to convert the CFG G into a PDAfor 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 figureout M, it will be easy to implement as a program. (Implementing a nondeterministicmachine is more difficult since the program needs to check every branch in the tree ofcomputation.)</p>
<p> </p>