The Gateway to Computer Science Excellence
+20 votes
3.3k views

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 by Veteran (105k points)
edited by | 3.3k views
+6

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

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

by Boss (13.5k points)
edited by
+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
.......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.
0

L2:{anbmmn and m,n0}

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

0
??
+2
@Saurav the regular language for L1 will be
$(a(a+b)^{+}a)+(b(a+b)^{+}b)$
0
Why L2 is wrong? Can you give a brief explanation.
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
by (15 points)
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}$

by Active (2.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,596 answers
195,822 comments
102,067 users