Difference between revisions of "Grammar: Decidable and Undecidable Problems"

Revision as of 12:06, 27 February 2014

Grammar: Decidable and Undecidable Problems

Grammar	<math>w \in L(G)</math>	<math>L(G) = \phi</math>	<math>L(G) = \Sigma^*</math>	<math>L(G_1) \subseteq L(G_2)</math>	<math>L(G_1) = L(G_2)</math>	<math>L(G_1) \cap L(G_2) = \phi</math>	<math>L(G)</math> is finite
Regular Grammar	D	D	D	D	D	D	D
Det. Context Free	D	D	D	UD	?	UD	D
Context Free	D	D	UD	UD	UD	UD	D
Context Sensitive	D	UD	UD	UD	UD	UD	UD
Recursive	D	UD	UD	UD	UD	UD	UD
Recursively Enumerable	D	UD	UD	UD	UD	UD	UD

Other Undecidable Problems

For arbitrary CFGs G, G1 and G2 and an arbitrary regular set R

The following problems are undecidable:

1. Whether <math>(L(G1))^\complement</math> is a CFL
2. Whether <math>L(G1) \cap L(G2)</math> is a CFL
3. Whether <math>L(G1) \cap L(G2)</math> is empty
4. Whether <math>L(G) = R</math>
5. Whether <math>L(G) \subseteq R</math>
6. Whether <math>G</math> is ambiguous
7. Whether <math>L(G)</math> is a DCFL

But whether <math>R \subseteq L(G)</math> is decidable

For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R

The following problems are decidable:

1. Whether <math>(L(G1))^\complement</math> is a DCFL
2. Whether <math>L(G1) \cap L(G2)</math> is a DCFL
3. Whether <math>L(G1) \cap L(G2)</math> is empty
4. Whether <math>L(G) = R</math>
5. Whether <math>L(G) \subseteq R</math>
6. Whether <math>L(G)</math> is a CFL

Whether <math>R \subseteq L(G)</math> is decidable