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

  1. $L_1$ and $L_3$ only
  2. $L_2$ only
  3. $L_2$ and $L_3$ only
  4. $L_3$ only
in Theory of Computation
edited by

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 ?

3 Answers

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.

edited by
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 can be accepted by a pda .so,i think the answer should be D.

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

.......i followed the link bt till now i m confused.For language L1 ,the set of string is infinite. So,if L1 is a regular language then it must be converted into its corresponding NFA or DFA. so,can u send me the structure of its NFA/DFA /transition table.

L2:{anbmmn and m,n0}

m and n are not equal . but answer l1 and l2 not l3 bcoz p=q=r(may be)

@Saurav the regular language for L1 will be
Why L2 is wrong? Can you give a brief explanation.
if m!=n... then it should be less than or greater than means comparisson is coming so not regular
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}$

if possible to draw graph it should be regular
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

Related questions

27 votes
4 answers
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
asked Feb 13, 2015 in Theory of Computation jothee 4k views
37 votes
9 answers
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
asked Feb 12, 2015 in Theory of Computation jothee 5.9k views
49 votes
2 answers
Which one of the following well-formed formulae is a tautology? $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$ $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$ ... $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
asked Feb 13, 2015 in Mathematical Logic jothee 7.5k views
29 votes
4 answers
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.
asked Feb 13, 2015 in Set Theory & Algebra jothee 3.3k views