# Decidable and Undecidable Problems Table | TOC

Table to check Decidable and Undecidable property of all Grammar (Regular, CFL, DCFL, CSL, Recursive, Recursive Enumerable)

D = Decidable
U = Undecidable
? = Open question

Grammar w ∈ L? L = ∅? L = Σ*? L1 ⊆ L2? L1 = L2? L1 ∩ L2 = ∅?
Regular D D D D D D
DCFL D D D U D U
CFL D D U U U U
Context Sensitive D U U U U U
Recursive D U U U U U
RE
(type 0)
U U U U U U

Check Also : Study Resources for TOC – GATE CS

Few More Point :

Language is Finite or Not (Finiteness Property):

• Decidable for Regular, DCFL, CFL .
• Undecidable for CSL, Recursive, RE.

Language Generated by Grammar is Regular or Not :

• Decidable for Regular , DCFL .
• Undecidable for CFL, CSL, Recursive, RE

A Easy Way to remember this table.

Some Important Properties :

1. Membership
2. Finiteness
3. Emptiness
4. Equality

Regular : Decidable for All 1,2,3,4.

*DCFL : Decidable for All 1,2,3,4.

CFL : Decidable for 1,2,3

CSL : Decidable for 1.

Recursive : Decidable for 1.

RE: Undecidable for All 1,2,3,4.

Few More Results

The following problems are undecidable:

### For arbitrary CFGs G , G1 and G2 and an arbitrary regular expression R

1. Whether is a CFL?
2. Whether is a CFL? (undecidable for DCFG also)
3. Whether is empty? (undecidable for DCFG also)
4. Whether ?
5. Whether ?
6. Whether is ambiguous?
7. Whether is a DCFL?
8. Whether is a regular language?

But whether is decidable. (We can test if is )

The following problems are Decidable:

### For arbitrary DCFGs G , G1 and G2 and an arbitrary regular expression R

The following problems are decidable:

1. Whether is a DCFL? (trivial)
2. Whether ?
3. Whether ?
4. Whether ?
5. Whether is a CFL? (trivial)

If you like GatePoint and would like to contribute, you can also write an article and mail your article to [email protected]. See your article appearing on the GatePoint main page and help other Gate Aspirants.