View source for Grammar: Decidable and Undecidable Problems ← Grammar: Decidable and Undecidable Problems

You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.

You can view and copy the source of this page.

Templates used on this page:

Return to Grammar: Decidable and Undecidable Problems.

Retrieved from "https://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems"
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 D UD UD UD UD UD UD


Other Undecidable Problems[edit]

For arbitrary CFGs G, G1 and G2 and an arbitrary regular set R[edit]

The following problems are undecidable:

  1. Whether <math>(L(G1))^\complement</math> is a CFL
  2. Whether <math>L(G1) \cap L(G2)</math> is a CFL
  3. Whether <math>L(G1) \cap L(G2)</math> is empty
  4. Whether <math>L(G) = R</math>
  5. Whether <math>L(G) \subseteq R</math>
  6. Whether <math>G</math> is ambiguous
  7. 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[edit]

The following problems are decidable:

  1. Whether <math>(L(G1))^\complement</math> is a DCFL
  2. Whether <math>L(G1) \cap L(G2)</math> is a DCFL
  3. Whether <math>L(G1) \cap L(G2)</math> is empty
  4. Whether <math>L(G) = R</math>
  5. Whether <math>L(G) \subseteq R</math>
  6. Whether <math>L(G)</math> is a CFL

Whether <math>R \subseteq L(G)</math> is decidable