GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 25

Question

Consider the following language definition:
$\small L = \{\langle M \rangle \mid M \text{ is a DFA and }M \text{ accepts some string of the form }ww^R\text{ for some }w \in \Sigma^*\}$

$L$ is

• A. Regular
• B. Context-free but not regular
• C. Recursive but not context-free
• D. Recursively enumerable but not recursive

Comments

First understand the given language. Watch this: https://www.youtube.com/live/CKfxH7tzq6U?feature=shared&t=2842 

Watch the Complete Playlist below to Revision & Understanding of Decidability:

https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI&feature=shared 

Answer 1

We cannot do this using a finite automata and so $L$ is not regular.

$ww^R$ can be detected using a PDA. We can take the intersection of this PDA with $M$ and this gives another PDA say $P.$ Now, if $P = \{\},$ $M$ does not accept any string of the form $ww^R.$ Checking if a CFL is empty is decidable and can be done with a Turing machine (at least LBA required). Thus $L$ is recursive but not context-free.

Comments

@gaurav_kumar, $L = \{ <M> | \text{M is a TM & L(M) contains at least one even palindrome string} \}$ 

Here the problem is about language of Turing Machine, So, we can apply Rice Theorem.

$L$ is Undecidable (i.e. Not Recursive) by Rice Theorem, because the property $P$ “containing at least one even palindrome string” is a Non-trivial property for RE languages. At least one RE language like $\Sigma^*$ satisfies $P$, & At least one RE language like $\phi$ doesn’t satisfy $P$.

$L$ is RE but Not REC.

Watch Complete Revision & Practice Playlist of Decidability & Rice Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI&feature=shared 

---

So the answer is D

But the given answer is C

---

@venkatesh pagadala, the given question is about DFA, & my this comment is about TM. 

Answer 2

L1: {ww^R | w belongs {0,1}*}
This is a CFL but not a DCFL. It can be derived from the following grammar
S -> aSa | bSb | epsilon

so correct answer is B .

this is gate 2005 question.

Comments

What does that have to do with this question other than that having $ww_R?$

---

so why answer is not B . it is DCFL right ? is there any difference between 2005 question and this ?

---

There is no similarity actually. You can watch the Decidability notes on gatecse.in TOC page.