Grammar: Decidable and Undecidable Problems Revision as of 19:13, 3 July 2014 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Heads Up! Please don't byheart this table. This is just to check your understanding

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)</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.

Other Undecidable Problems

Proofs

For arbitrary CFGs <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>

The following problems are undecidable:

1. Whether <math>(L(G_1))^\complement</math> is a CFL?
2. Whether <math>L(G_1) \cap L(G2)</math> is a CFL? (undecidable for DCFG also)
3. Whether <math>L(G_1) \cap L(G2)</math> is empty? (undecidable for DCFG also)
4. Whether <math>L(G) = L(R)</math>?
5. Whether <math>L(R) \subseteq L(G)</math>?
6. Whether <math>G</math> is ambiguous?
7. Whether <math>L(G)</math> is a DCFL?
8. Whether <math>L(G)</math> is a regular language?

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>)

For arbitrary DCFGs <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>

The following problems are decidable:

1. Whether <math>(L(G_1))^\complement</math> is a DCFL? (trivial)
2. Whether <math>L(G) = L(R)</math>?
3. Whether <math>L(G) \subseteq (R)</math>?
4. Whether <math>L(R) \subseteq L(G)</math>?
5. Whether <math>L(G)</math> is a CFL? (trivial)

For any $TM$ $M$, $\Zigma^*-L(M)$ is a $CFL$

Tweet