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 ?

The Gateway to Computer Science Excellence

+20 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

+37 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.

+5

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

0 votes

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,596 answers

195,822 comments

102,067 users