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 = ∅?|
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 :
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
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.
M.Tech Student at Indian Institute of Science
AIR 2 ISRO SC Written Test Dec 2017
AIR 142 GATE 2018
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.