Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 11: | Line 11: | ||
! <math>L(G_1) = 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_1) \cap L(G_2) = \phi</math> | ||
− | ! <math>L(G)</math> is | + | ! <math>L(G)</math> is regular? |
− | ! $L(G)$ is | + | ! $L(G)$ is finite? |
|- | |- | ||
|Regular Grammar | |Regular Grammar | ||
Line 37: | Line 37: | ||
| {{D}} | | {{D}} | ||
| {{D}} | | {{D}} | ||
+ | | {{UD}} | ||
| {{UD}} | | {{UD}} | ||
| {{UD}} | | {{UD}} | ||
Line 42: | Line 43: | ||
| {{UD}} | | {{UD}} | ||
| {{D}} | | {{D}} | ||
− | |||
|- | |- | ||
|Context Sensitive | |Context Sensitive |
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 regular? | $L(G)$ is finite? |
---|---|---|---|---|---|---|---|---|
Regular Grammar | D | D | D | D | D | D | D | D |
Det. Context Free | D | D | D | UD | D | UD | D | D |
Context Free | D | D | UD | UD | UD | UD | UD | D |
Context Sensitive | D | UD | UD | UD | UD | UD | UD | UD |
Recursive | D | UD | UD | UD | UD | UD | UD | UD |
Recursively Enumerable | UD | 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 L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)
The following problems are decidable:
For any $TM$ $M$, $\Sigma^*-L(M)$, is a $CFL$
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 regular? | $L(G)$ is finite? |
---|---|---|---|---|---|---|---|---|
Regular Grammar | D | D | D | D | D | D | D | D |
Det. Context Free | D | D | D | UD | D | UD | D | D |
Context Free | D | D | UD | UD | UD | UD | UD | D |
Context Sensitive | D | UD | UD | UD | UD | UD | UD | UD |
Recursive | D | UD | UD | UD | UD | UD | UD | UD |
Recursively Enumerable | UD | 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 L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)
The following problems are decidable:
For any $TM$ $M$, $\Sigma^*-L(M)$, is a $CFL$