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

Line 65: Line 65:
 
| {{UD}}
 
| {{UD}}
 
|}
 
|}
 +
 +
 +
==Other Undecidable Problems ==
 +
 +
===For CFGs G, G1 and G2 and regular set R===
 +
 +
1.) the compliment of L(G1)\complement 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

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 L(G1)\complement 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
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=2651"
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 L(G1)\complement 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