search
Log In
0 votes
22 views

Complete the proof of theorem $7.27$ by showing that

$(q_{P},w,Z_{0})\vdash(q,\in,\gamma)$ if and only if $(q_{P},q_{A},w,Z_{0}) \vdash((q,p),\in,\gamma),$  where $p =\hat{\delta}(p_{A},w).$

in Theory of Computation
edited by
22 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
2
18 views
In this exercise, we shall show that for every context-free language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that generates $L-\in.$ Recall that a Greibach normal form $(GNF)$ grammar is one where every production body starts with a terminal. ... $,$ down to $A_{1}$ using part $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
0 votes
0 answers
3
21 views
Is it possible to find, for every context-free language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body consisting of three variables$),$ or $A\rightarrow a$ $($i.e., a body consisting of a single terminal$)?$ Give either a proof or a counterexample.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 21 views
0 votes
0 answers
4
40 views
Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating. Both directions of Theorem $7.6$ where we show the correctness of the algorithm in Section $7.1.2$ for detecting the reachable symbols. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 40 views
...