Arjun Suresh (talk | contribs) (→For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R) |
Arjun Suresh (talk | contribs) |
||
| Line 73: | Line 73: | ||
The following problems are '''undecidable''': | The following problems are '''undecidable''': | ||
| − | # Whether <math>(L(G1))^\complement</math> is a CFL | + | # Whether <math>(L(G1))^\complement</math> is a CFL? |
| − | # 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(G) = R</math> | + | # Whether <math>L(G) = R</math>? |
| − | # Whether <math>L(G) | + | # Whether <math>R \subseteq L(G)</math>? |
| − | # Whether <math>G</math> is ambiguous | + | # Whether <math>G</math> is ambiguous? |
| − | # Whether <math>L(G)</math> is a DCFL | + | # Whether <math>L(G)</math> is a DCFL? |
| − | But whether <math> | + | But whether <math>L(G) \subseteq R</math> is decidable. (We can test if <math>L(G) \cap compl(R)</math> is <math>\phi</math>) |
===For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R=== | ===For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R=== | ||
The following problems are '''decidable''': | The following problems are '''decidable''': | ||
| − | # Whether <math>(L(G1))^\complement</math> is a DCFL (trivial) | + | # Whether <math>(L(G1))^\complement</math> is a DCFL? (trivial) |
| − | # Whether <math>L(G) = R</math> | + | # Whether <math>L(G) = R</math>? |
| − | # Whether <math>L(G) \subseteq R</math> | + | # Whether <math>L(G) \subseteq R</math>? |
| − | # Whether <math>R \subseteq L(G)</math> | + | # Whether <math>R \subseteq L(G)</math>? |
| − | # Whether <math>L(G)</math> is a CFL (trivial) | + | # Whether <math>L(G)</math> is a CFL? (trivial) |
| 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 | UD | UD | UD | UD | UD | UD | UD |
Checking if <math>L(CFG)</math> is finite is decidable because we just need to see if <math>L(CFG)</math> contains any string with length between <math>n</math> and <math>2n-1</math>, where <math>n</math> is the pumping lemma constant. If so, <math>L(CFG)</math> is infinite otherwise its finite.
The following problems are undecidable:
But whether <math>L(G) \subseteq R</math> is decidable. (We can test if <math>L(G) \cap compl(R)</math> is <math>\phi</math>)
The following problems are 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 | UD | UD | UD | UD | UD | UD | UD |
Checking if <math>L(CFG)</math> is finite is decidable because we just need to see if <math>L(CFG)</math> contains any string with length between <math>n</math> and <math>2n-1</math>, where <math>n</math> is the pumping lemma constant. If so, <math>L(CFG)</math> is infinite otherwise its finite.
The following problems are undecidable:
But whether <math>L(G) \subseteq R</math> is decidable. (We can test if <math>L(G) \cap compl(R)</math> is <math>\phi</math>)
The following problems are decidable:
GATECSE