Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
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 |
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 |
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
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 |