search
Log In
0 votes
50 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.
in Theory of Computation 50 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
17 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 17 views
0 votes
0 answers
2
15 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 15 views
0 votes
0 answers
3
0 votes
0 answers
4
31 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 31 views
...