Skip links

Main navigation

GATE CSE

Resource Portal of GATE Overflow

Grammar: Decidable and Undecidable Problems

by 9 Comments

Heads Up! Please do not by heart this table. This is just to check your understanding
Grammar: Decidable and Undecidable Problems
Grammar $w \in L(G)$ $L(G) = \phi$ $L(G) = \Sigma^*$ $L(G_1) \subseteq L(G_2)$ $L(G_1) = L(G_2)$ $L(G_1) \cap L(G_2) = \phi$ $L(G)$ 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 $L(CFG)$ is finite is decidable because we just need to see if $L(CFG)$ contains any string with length between $n$ and $2n-1$, where $n$ is the pumping lemma constant. If so, $L(CFG)$ is infinite otherwise it is finite.

Other Undecidable Problems

Proofs

For arbitrary CFGs $G$, $G_1$ and $G_2$ and an arbitrary regular expression $R$

The following problems are undecidable:

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

But whether $L(G) \subseteq L(R)$ is decidable. (We can test if $L(G) \cap compl(L(R))$ is $\phi$)

For arbitrary DCFGs $G$, $G_1$ and $G_2$ and an arbitrary regular expression $R$

The following problems are decidable:

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

Loading