search
Log In
0 votes
31 views

Provide the inductive proofs needed to complete the following theorems$:$ 

  1. The part of Theorem $7.4$ where we show that discovered symbols really are generating.
  2. Both directions of Theorem $7.6$ where we show the correctness of the algorithm in Section $7.1.2$ for detecting the reachable symbols.
  3. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.
in Theory of Computation 31 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
15 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 15 views
0 votes
0 answers
2
17 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 17 views
0 votes
0 answers
3
53 views
Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$ Show that the CNF grammar has at most $O(n^{2})$ productions. Show that it is possible for the $CNF$ grammar to have a number of productions proportional to $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 53 views
0 votes
0 answers
4
36 views
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}-1)}{(n-1)}$ steps. How close can you actually come to this bound$?$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 36 views
...