retagged by
7,154 views
17 votes
17 votes

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?

  1. $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$
  2. $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\Sigma^* \}$
  3. $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\emptyset \}$
  4. $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
retagged by

3 Answers

Best answer
16 votes
16 votes

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).

selected by
10 votes
10 votes

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)

1 votes
1 votes

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.

edited by
Answer:

Related questions

14 votes
14 votes
5 answers
1
18 votes
18 votes
4 answers
4
Arjun asked Feb 18, 2021
10,527 views
Which of the following standard $C$ library functions will always invoke a system call when executed from a single-threaded process in a $\text{UNIX/Linux}$ operating sys...