Skip links

Main navigation

GATE CSE

Resource Portal of GATE Overflow

automata

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)

25,021 total views, 10 views today

Closure Property of Language Families

by 9 Comments

Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose $L_1$ and $L_2$ belong to CFL and if CFL is closed under operation $\cup$, then $L_1 \cup L_2$ will be a CFL. But if CFL is not closed under $\cap$, that doesn’t mean $L_1 \cap L_2$ won’t be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation – it may or may not belong to the class of the operand languages. In short, closure property is applicable, only when a language is closed under an operation.

Now, while applying closure property do remember the language hierarchy.

Regular $\subset$ DCFL $\subset$CFL $\subset$ REC $\subset$ RE.

So, if CFL is closed under Union, and $L_1$ and $L_2$ belong to CFL, then $L_1\cup L_2$ will be a CFL. But $L_1 \cup L_2$ can also be a regular language, which closure property can’t tell. For this we need to see $L_1$ and $L_2$.

Heads Up! Please don’t learn this table by heart . This is just to check your understanding and some of them are not required for GATE

Closure properties of language families

Operation Regular DCFL CFL CSL Recursive RE
Union yes no yes yes yes yes
Intersection yes no no yes yes yes
Complement yes yes no yes yes no
Concatenation yes no yes yes yes yes
Kleene star yes no yes yes yes yes
Homomorphism yes no yes no no yes
$\epsilon$-free Homomorphism yes no yes yes yes yes
Substitution ($\epsilon$-free) yes no yes yes no yes
Inverse Homomorphism yes yes yes yes yes yes
Reverse yes no yes yes yes yes
Intersection with a regular language yes yes yes yes yes yes

37,971 total views, 26 views today

Theory of Computation

by 14 Comments

Syllabus

http://www.gatecse.in/gate-cse-2016-syllabus/#Theory_of_Computation

  1. pumping lemma newly added. So, questions based on pumping length or some examples can be asked.
  2. Recursively enumerable sets removed but Turing machines are there. So, this should not really matter.

Book

Video

You won’t get better video for TOC than Shai Simonson’s.

Web Links

Previous Year Questions

http://gateoverflow.in/questions/automata-theory

Important Questions

http://gateoverflow.in/blog/21/important-questions-in-theory-of-computation

GATE CSE Discussions

2016

2016 – Decidability

58,029 total views, 24 views today

%d bloggers like this:
Skip to toolbar