search
Log In
0 votes
35 views
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
in Theory of Computation 35 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
28 views
For an unrestricted grammar $G$, show that the question $“Is \space L(G) = L(G)^*?”$ is undecidable. Argue $\text(a)$ from Rice’s theorem and $\text(b)$ from first principles.
asked Mar 16, 2019 in Theory of Computation Rishi yadav 28 views
0 votes
0 answers
2
25 views
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\cap L(G_2) = \phi $ is undecidable for any fixed $G_2,$ as long as $L(G_2)$ is not empty.
asked Mar 16, 2019 in Theory of Computation Rishi yadav 25 views
0 votes
0 answers
3
0 votes
0 answers
4
...