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 ?

22 votes

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\}$

- $L_1$ and $L_3$ only
- $L_2$ only
- $L_2$ and $L_3$ only
- $L_3$ only

38 votes

Best answer

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.

1

yes,it is correct that l1 is a string with same start and end letter but the 2nd and the 2nd last character should also be same.......3rd and the 3rd last character should be same and so on..........if the length of w is n then upto first n character and last n character there should be matching nd obviously it can nt be accepted by nfa or dfa due to its finite amount of memory ......it can be accepted by a pda .so,i think the answer should be D.

6

The a choice is bit tricky. But it is obviously regular. You can see reason here:

http://gatecse.in/wiki/Identify_the_class_of_the_language

4 votes

$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}$