in Theory of Computation
178 views
1 vote
1 vote
$\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.
in Theory of Computation
178 views

Please log in or register to answer this question.

Related questions