GATE CSE 2015 Set 2 | Question: 51

Question

Which of the following is/are regular languages?

$L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$

$L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}$

$L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$

• A. $L_1$ and $L_3$ only
• B. $L_2$ only
• C. $L_2$ and $L_3$ only
• D. $L_3$ only

Comments

is this DFA for L1?

And why L2 is not regular? We do not need to remember no of a's and no of b's regular or not although m ≠ n ?

Answer 1

Answer is A.

$L_1$: all strings of length $3$ or more with same start and end letter- because everything in middle can be consumed by $x$ as per the definition of $L$.

$L_2$: We need to compare number of $a$'s and $b$'s and these are not bounded. So, we need at least a DPDA.

$L_3$: Any number of $a$'s followed by any number of $b$'s followed by any number of $c$'s. Hence regular.

Comments

Why L2 is wrong? Can you give a brief explanation.

---

if m!=n... then it should be less than or greater than ....it means comparisson is coming so not regular

---

is WcW^r a regular language ? W E (a,b)+ and c is a single symbol .??

Answer 2

$L_{1}$ is Regular Language. The first and the last character must be same, and everything in the middle can be absorbed by x.

$L_{2}$ involves a comparison, hence CFL. (DCFL to be precise)

$L_{3}$ involves no comparison. Pretty easy to make a FA of it. Hence, Regular.

Option A

 

Golden rule

If the language is finite, then regular 100%.
If the language is infinite, but has a "pattern", then regular.
Most of the times, whenever a comparison is involved between two characters, it is CFL. But if we successfully find a "pattern" or a way such that we need not compare, then it'll be Regular. Which is the case with $L_{1}$

Comments

if possible to draw graph it should be regular

Answer 3

W,X belongs to (a+b)* .for eg some arbitrary string is there ' abbabababa....then consider only last character as part of W and rest as part of string X. A DFA can be drawn for a(a+b)* a ll b(a+b)* b