Prove formally that the language of all the grammar rules constructed in the proof of Theorem 3.7 

 
 

Transcribed Image Text:

Theorem 3.7. If A is a pushdown automaton, then L(A) is a context-free language. Proof. Non-constructive proof of existence. Let B be a PDA equivalent to A constructed with the specifications given in Lemma 3.2. Thus, in particular, L(B) = L(A). Now, the computation of each w = a₁ an L(B) produces at least one accepting computation path. Select one such path and plot the pairs (qi, y), qi Q, in the order that they appear in the path. Now, since each variable used in the construction of the rules is indexed with a pair in Q x Q, there are at most, 1. Q rules of type 3, Theorem 3.7. If A is a pushdown automaton, then L(A) is a context-free language. Proof. Non-constructive proof of existence. Let B be a PDA equivalent to A constructed with the specifications given in Lemma 3.2. Thus, in particular, L(B) = L(A). Now, the computation of each w = a₁ an L(B) produces at least one accepting computation path. Select one such path and plot the pairs (qi, y), qi Q, in the order that they appear in the path. Now, since each variable used in the construction of the rules is indexed with a pair in Q x Q, there are at most, 1. Q rules of type 3,

Answer rating: 100% (QA)

The problem is to prove that the language of all the grammar rules constructed in the proof of Theor... View the full answer