Register

Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)

432 views

1 Answer

0 0 votes
Since because language L1 is regular,

And every regular language is context free language so using L1 we would be able to construct equivalent CFG.

Then the main problem will become whether the language generated by one context free grammar is a subset of language generated by another context free grammar, which is Undecidable.
Voting & Accepting an answer helps improve the community
← Previous · Peter Linz Edition 5...Next → · Peter Linz Edition 5...
← Previous in category · Peter Linz Edition 5...Next in category → · Peter Linz Edition 5...
Position:
Show:

Related questions

0 0 votes
1 1 answer
568
568 views
Rishi yadav asked Mar 16, 2019
568 views
Peter Linz Edition 5 Exercise 12.4 Question 8 (Page No. 321)
Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted,$\text(b)$ when $G_2$ is context-free...
0 0 votes
1 1 answer
551
551 views
Rishi yadav asked Mar 16, 2019
551 views
Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$
0 0 votes
0 0 answers
333
333 views
Rishi yadav asked Mar 16, 2019
333 views
Peter Linz Edition 5 Exercise 12.4 Question 6 (Page No. 321)
Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation ...
0 0 votes
0 0 answers
300
300 views
Rishi yadav asked Mar 16, 2019
300 views
Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in The...