Dark Mode

4,085 views

9 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?

- $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$
- $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\Sigma^* \}$
- $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\emptyset \}$
- $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$

11 votes

Best answer

**Correct Option: D**

A & B are **recursive**, since for every **regular language**, there exists a **unique minima**l **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:

- https://my.eng.utah.edu/~cs3100/lectures/l18/pda-notes.pdf (pg 257)
- https://www.cse.cuhk.edu.hk/~siuon/csci3130-f17/slides/lec11.pdf (slide 7)
- https://github.com/typesAreSpaces/PDA-to-CFG (if you wanna go crazy)
- https://gatecse.in/grammar-decidable-and-undecidable-problems/ (do check it out)
- 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).

1 vote

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

1

1