Register

Peter Linz Edition 5 Exercise 12.2 Question 7 (Page No. 311)

178 views
0 votes
0 votes
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.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Rishi yadav asked Mar 16, 2019
202 views
Peter Linz Edition 5 Exercise 12.2 Question 8 (Page No. 311)
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.
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 ...
User Avatar
0 votes
0 votes
0 answers
3
Rishi yadav asked Mar 16, 2019
778 views
Peter Linz Edition 5 Exercise 12.2 Question 5 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$$?$
User Avatar
0 votes
0 votes
0 answers
4
Rishi yadav asked Mar 16, 2019
300 views
Peter Linz Edition 5 Exercise 12.2 Question 4 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
User Avatar
Link Copied!