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

(→‎For CFGs G, G1 and G2 and regular set R)
(→‎For CFGs G, G1 and G2 and regular set R)
Line 69: Line 69:
 
==Other Undecidable Problems ==
 
==Other Undecidable Problems ==
  
−
===For CFGs G, G1 and G2 and regular set R===
+
===For arbitrary CFGs G, G1 and G2 and regular set R===
 
The following problems are undecidable:
 
The following problems are undecidable:
  
Line 75: Line 75:
 
# Whether <math>L(G1) \cap L(G2)</math> is a CFL
 
# Whether <math>L(G1) \cap L(G2)</math> is a CFL
 
# Whether <math>L(G1) \cap L(G2)</math> is empty
 
# Whether <math>L(G1) \cap L(G2)</math> is empty
−
# Whether <math>L(G1) = R</math>
+
# Whether <math>L(G) = R</math>
 
# Whether <math>G</math> is ambiguous
 
# Whether <math>G</math> is ambiguous

Revision as of 18:32, 26 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) is finite</math>
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 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>G</math> is ambiguous
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=2656"
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) is finite</math>
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[edit]

For CFGs G, G1 and G2 and regular set R[edit]

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(G1) = R</math>
  5. Whether <math>G</math> is ambiguous