GATE CSE 2021 Set 1 | Question: 12

Question

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive?

• A. $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$
• B. $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\Sigma^* \}$
• C. $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\emptyset \}$
• D. $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$

Comments

We do need a option to convert comments to answers...

---

It is there already -- but I guess for Editors and above.

---

There is an option. Is it not visible?

Answer 1

Correct Option: D

---

A & B are recursive, since for every regular language, there exists a unique minimal DFA and we’ve a minimization procedure for the same. We could therefore compare any two regular languages which makes options A and B recursive (corresponding problem is decidable)

Option C is recursive.
For every PDA there is a corresponding CFG and vice versa. Moreover they’re inter-convertible (see the references). So, we can convert the given PDA to its equivalent CFG. Then, we have algorithms to remove empty, unit and useless productions. If the language of the given PDA is empty then the Start Symbol would be useless (not generating any strings) which is decidable using an algorithm.

Option D is the Universality problem of CFLs and it is not decidable (not even semi-decidable). So, the given language is neither recursive nor recursively enumerable. 

---

References:

1. https://my.eng.utah.edu/~cs3100/lectures/l18/pda-notes.pdf  (pg 257)
2. https://www.cse.cuhk.edu.hk/~siuon/csci3130-f17/slides/lec11.pdf  (slide 7)
3. https://github.com/typesAreSpaces/PDA-to-CFG  (if you wanna go crazy)
4. https://gatecse.in/grammar-decidable-and-undecidable-problems/ (do check it out)
5. https://gatecse.in/closure-property-of-language-families/

Try coming up with counter-examples for undecidability, and try to at least remember for RG, CFG and UG.
$$\scriptsize \begin{array}{|l|c|c|c|c|c|c|c|}\hline \text{Problem}&\text{RL}&\text{DCFL}&\text{CFL}&\text{CSL}&\text{RL}&\text{REL}\\\hline
\text{Is}\ w\in L?\text{(Membership problem)}&D&D&D&D&D&UD\\\hline
\text{Is}\ L=\phi?\text{(Emptiness problem)}&D&D&D&UD&UD&UD\\\hline
\text{Is}\ L=\Sigma^*?\text{(Completeness problem)}&D&D&UD&UD&UD&UD\\\hline
\text{Is}\ L_1=L_2?\text{(Equality problem)}&D&D&UD&UD&UD&UD\\\hline
\text{Is}\ L_1\subseteq L_2?\text{(Subset problem)}&D&UD&UD&UD&UD&UD\\\hline
\text{Is } L_1\cap L_2=\phi?&D&UD&UD&UD&UD&UD\\\hline
\text{Is L finite? (finiteness problem)}&D&D&D&UD&UD&UD\\\hline
\text{Is complement of ‘L' a language of the same class?}&D&D&UD&D&D&UD\\\hline
\text{Is intersection of two languages of the same class?}&D&UD&UD&D&D&D\\\hline
\text{Is L a regular Language?}&D&D&UD&UD&UD&UD\\\hline
\end{array}$$
PS:

Some of the references I presented here notably 1 & 3 do go a stretch beyond what’s necessary I hope someone will find them useful which is why I added them. I believe it’s suffice to know that such an algorithm does exist but beyond that is unnecessary (arguable though).

Comments

This site is 7 years old 😃 Ofcourse I can see actual number in Pragys app as well.

---

@gatecse  ok :)

---

Thanks for this answer :)

Answer 2

ANS IS D. 

IT IS SIMPLE DECIDABILITY TABLE RELATED QUESTION. I REMEMBERED THE TABLE WITH TRICK. HOPE IT WILL HELP YOU(IT IS IMPORTANT TO KNOW THE REASON THEN IT IS EASY TO REMEMBER)

Comments

thanks for the tip man, this will be very helpful.

Answer 3

We can get minimal DFA for both A and B, as minimal DFAs for both of them are just single state DFAs,

And we know minimal DFA for any regular language is always unique. So they should be isomorphic to $DFA_{min}(\phi)$ and $DFA_{min}(\sum^{*})$ respectively.

It’s easy to check if $DFA_{min}$ for A is isomorphic to $DFA_{min}(\phi)$ as there’s only 1 state, if they are isomorphic we say ‘Yes’, otherwise we say ‘No’. 

Same procedure can be applied to check if $DFA_{min}$ for B = $DFA_{min}(\sum^{*}).$

Another algorithm to prove both cases can be found here. (reference)

Hence both (A) and (B) are decidable.

For every PDA we can covert it into a CFG, minimize the CFG (removing all useless symbols and productions), if Start symbol is useless then we can say ‘Yes’, otherwise we can say ‘No’. Hence (C) is decidable.

Only option left is (D). It is undecidable, There’s no way to determine if a CFG can generate everything or not. Proof (not meant for GATE) is given here.

Final ans is D.

Comments

Thanks, I got the idea,  This is same kinda Algorithm that can be used to test emptiness, if at the end we don’t have any final state checked then it’s empty, otherwise it’s not.

---

This is an easy way

https://cs.stackexchange.com/questions/81813/is-the-equality-of-two-dfas-a-decidable-problem

More options

---

Thank you Sir, this paper is really nice.. got some very good insight towards the problem.