Log In
0 votes
Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form

                                                                                         $u\rightarrow v,$

with $u,v\in (V \cup T)^+$ and $|u| \leq |v|$, or


with $A\in V$

Show that the conclusion still holds if we add the further conditions $|u|\leq2$ and $|v|\leq2$
in Theory of Computation 26 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form $u\rightarrow v$, where $u$ is nit $(V\cup T)^+$ and $v$ is int $(V\cup T)^*$ Some authors give a definition of unrestricted grammars that ... definition is basically the same as the one we use, in the sense that for every grammar of one type, there is an equivalent grammar of the other type.
asked Mar 17, 2019 in Theory of Computation Rishi yadav 67 views
0 votes
0 answers
0 votes
0 answers
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$. Construct a Turing machine for $L(01(01)^*)$, then find an unrestricted grammar for it using the construction in Theorem. Give a derivation for $0101$ using the resulting grammar.
asked Mar 17, 2019 in Theory of Computation Rishi yadav 52 views