edited by
11,014 views
30 votes
30 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\}$

  1. $L_1$ and $L_3$ only
  2. $L_2$ only
  3. $L_2$ and $L_3$ only
  4. $L_3$ only
edited by

3 Answers

Best answer
53 votes
53 votes

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.

edited by
5 votes
5 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}$

1 votes
1 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
Answer:

Related questions

36 votes
36 votes
6 answers
1
go_editor asked Feb 13, 2015
15,512 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
88 votes
88 votes
5 answers
3
38 votes
38 votes
5 answers
4