search
Log In
0 votes
19 views
Show that for 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

                                                                                         $A\rightarrow\lambda$

with $A\in V$
in Theory of Computation 19 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
21 views
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 21 views
0 votes
0 answers
2
19 views
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 $A\rightarrow\lambda$ with $A\in V$ Show that the conclusion still holds if we add the further conditions $|u|\leq2$ and $|v|\leq2$
asked Mar 17, 2019 in Theory of Computation Rishi yadav 19 views
0 votes
0 answers
3
33 views
$\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 33 views
...