Arjun Suresh (talk | contribs) (→Other Undecidable Problems) |
Arjun Suresh (talk | contribs) |
||
Line 78: | Line 78: | ||
# Whether <math>L(G) \subseteq R</math> | # Whether <math>L(G) \subseteq R</math> | ||
# Whether <math>G</math> is ambiguous | # Whether <math>G</math> is ambiguous | ||
− | # Whether <math>L(G)</math> is DCFL | + | # 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: | ||
+ | |||
+ | # Whether <math>(L(G1))^\complement</math> is a DCFL | ||
+ | # Whether <math>L(G1) \cap L(G2)</math> is a DCFL | ||
+ | # Whether <math>L(G1) \cap L(G2)</math> is empty | ||
+ | # Whether <math>L(G) = R</math> | ||
+ | # Whether <math>L(G) \subseteq R</math> | ||
+ | # Whether <math>L(G)</math> is a CFL | ||
Whether <math>R \subseteq L(G)</math> is decidable | Whether <math>R \subseteq L(G)</math> is decidable |
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 |
The following problems are undecidable:
But whether <math>R \subseteq L(G)</math> is decidable
The following problems are decidable:
Whether <math>R \subseteq L(G)</math> is decidable
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 |
The following problems are undecidable:
But whether <math>R \subseteq L(G)</math> is decidable
The following problems are decidable:
Whether <math>R \subseteq L(G)</math> is decidable