# Peter Linz Edition 5 Exercise 11.2 Question 7 (Page No. 290)

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$

## 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.
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$
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.
0 votes
0 answers
4
57 views
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L = L(G)$. Give the details of the proof of the Theorem.