UGC NET CSE | December 2013 | Part 2 | Question: 28

Question

Given the following statements:

$S_1$: If $L$ is a regular language then the language $\{uv \mid u \in L, v \in L^R\}$ is also regular.

$S_2$: $L=\{ww^R\}$ is regular language.

Which of the following is true?

• A. $S_1$ is not correct and $S_2$ is not correct
• B. $S_1$ is not correct and $S_2$ is correct
• C. $S_1$ is correct and $S_2$ is not correct
• D. $S_1$ is correct and $S_2$ is correct

Answer 1

Answer C: S1 is correct and S2 is not correct

• If L is regular then reversal of L is also regular. hence u and v are regular
• Concatenation of regular languages are regular.
• Hence uv is regular

S1 is correct

• To find wwR we need to remember what is w.
• Regular grammar is checked by finite automata, which has no memory (stack)
• To find wwR we need at least NPDA

S2 is incorrect

Comments

Given a word $w$ how to check if it is of the form $uv$? I mean can you give a more formal way of saying S1 is correct?

---

How wwR can be accepted by npda