Line 71: Line 71:
 
===For CFGs G, G1 and G2 and regular set R===
 
===For CFGs G, G1 and G2 and regular set R===
  
1.) the compliment of L(G1)\complement is a CFL
+
1.) the compliment of <math>L(G1)\complement</math> is a CFL
 
       2.) L(G1) intersected with L(G2) is a CFL
 
       2.) L(G1) intersected with L(G2) is a CFL
 
  3.) L(G1) = R
 
  3.) L(G1) = R
 
It is undecidable whether an arbitrary CFG is ambiguous
 
It is undecidable whether an arbitrary CFG is ambiguous
 
     It is undecidable for arbitrary CFG's G1 and G2 whether L(G1) intersected with L(G2) is empty
 
     It is undecidable for arbitrary CFG's G1 and G2 whether L(G1) intersected with L(G2) is empty

Revision as of 18:28, 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 CFGs G, G1 and G2 and regular set R

1.) the compliment of <math>L(G1)\complement</math> is a CFL

     2.) L(G1) intersected with L(G2) is a CFL
3.) L(G1) = R

It is undecidable whether an arbitrary CFG is ambiguous

   It is undecidable for arbitrary CFG's G1 and G2 whether L(G1) intersected with L(G2) is empty
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]

1.) the compliment of <math>L(G1)\complement</math> is a CFL

     2.) L(G1) intersected with L(G2) is a CFL
3.) L(G1) = R

It is undecidable whether an arbitrary CFG is ambiguous

   It is undecidable for arbitrary CFG's G1 and G2 whether L(G1) intersected with L(G2) is empty