Register

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

• retagged by
306 views

1 Answer

0 votes
0 votes

yeah it is decidable because L(G1)intersectionL(G2) regular intersection [L(G1) context free (in worst case CFL it may be regular language also) and L(G2) is regular language]

and regular intersection is closed under that language so L(G1)INTERSECTIONL(G2) is CFL and CFL is decidable emptiness so it is DECIDABLE

 

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

Related questions

0 votes
0 votes
1 answer
1
Rishi yadav asked Mar 16, 2019
308 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, $\text(c)$ when $G_2$ is regular$?$
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...
User Avatar
0 votes
0 votes
1 answer
3
Rishi yadav asked Mar 16, 2019
226 views
Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
User Avatar
Link Copied!