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 , and and an arbitrary regular expression

  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 , and and an arbitrary regular expression

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.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

About Anup Patel

Anup PatelM.Tech Student at Indian Institute of Science
AIR 2 ISRO SC Written Test Dec 2017
AIR 142 GATE 2018

Leave a Reply

Your email address will not be published. Required fields are marked *