# Recent questions tagged regular-expressions

1
Consider a regular expression over the alphabet set $\{r,s\}$. The following regular expressions are to be considered $( r^{*}s^{*})^{*}+ (r^{+}s^{+})^{*}$ $(r^{+}s^{+}r^{+} )^{+}+ (\varepsilon + r)^{*}$ $(rs^{*}+sr^{*})^{*}+(\varepsilon +s)$ ... $(r+s)^{+}$ all denote an infinite number of strings but not equivalent to $(r+s)^{*}$ all denotes a finite number of strings
2
Let $r, s, t$ be regular expressions. Which of the following identities is correct? $(r + s)^* = r^*s^*$ $r(s + t) = rs + t$ $(r + s)^* = r^* + s^*$ $(rs + r)^* r = r (sr + r)^*$ $(r^*s)^* = (rs)^*$
3
4

5
Is $\{xww \mid w,x \in (a+b)^{+}\}$ regular because there is no restriction on the max length of $x$ ? As mush as I know, if there is no restriction on the maximum value of $x$, then it can expand as much as to cover $ww$, making the language regular. Please correct me if I am wrong.
6
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ? Does this imply that a subset of non regular language can be regular ?
7
Let M be a Non-deterministic Finite Machine. Let G be the Regular Grammar obtained from M. Which is True? (a) G will always be unambiguous (b) G will always be ambiguous (c) G may be ambiguous (d) None of the above
8

1 vote
9
Is L={0, 011, 011000, 0110001111, ....} a regular language? I know that the language should follow some regular pattern and we should be able to construct a regex for it in order to say it a RL. Morever it shouldnt require any kind of extra memory to store the ... S. I wud be thankful if somebody suggests a quick method to identify given set to be RL or NRL based on pattern. Thanks in advance :)
10
Consider R1 and R2 are two regular expression then equality of two regular expression compute in A) polynomial time  B) Exponential time C) logarithmic Polynomial time  D) Constant Time
11
(a+b)*a(a+b)*(a+b)* b * a b * a (a + b)* (a + b)* a b* a b* b * a (a + b)* a b* All are generating same language.
12
Which of the following are not equivalent to expression $(a + b + c)^*$? (A) $(a^* + b^* + c^*)^*$ (B) $\Bigl ( (ab)^* + c^* \Bigr )^*$ (C) $(a^* b^* c^*)^*$ (D) $(a^*b^* + c^*)^*$
13
$(a^*+b^*)^*$ $(a^*b^*)^*$ $(a+b)^*$ $(a+b^*)^*$ $(a^*+b)^*$ $(b^*a+a^*b)^*$ $(a+ab)^*$ $(ba+ab)^*$
14
Regular expression for the complement of language $L=\left\{a^{n}b^{m} \mid n \geq 4, m \leq 3\right\}$ is $(a + b)^{*} ba(a + b)^{*}$ $a^{*} bbbbb^{*}$ $(\lambda + a + aa + aaa)b^{*} + (a + b)^{*} ba(a + b)^{*}$ None of the above
15
(aa*)b (abab)+(aaa+b)*
16
$A + B = C$ $A^R + B^R = C$ $A^R + B = C$ None
17
Q which of the following pair of regular expressions are equal a)a* & ((aa)* + (aa0)*)* b)(r+s)* & (rs)* c)(rr)* & r*r* d)(r1(r1+r2)*)* & r1(r1+r2) answer given is option D but it think option D should be modified to (r1(r1+r2)*)* & r1*(r1+r2)* for being it correct.
18
Q which of the following pair of regular expressions are not equal a)&empty;* & &isin;* b)(01+0)*0 & 0(10+0)* c)r1*(r1+r2)* & (r1 + r2)* d)None of the above in my view option A should be the correct option but answer given is option D
19
Q) which of the following pair of regular expressions are equal a)(0+1)* & 0* + 1* b)&empty;* & &empty;* c)0(120)*12 & 01(201)*2 d)None of the above answer given is option C which i got why.The problem is what is wrong with option B deemed to be true?? .also is 010 present in 0* +1*?? .
20
The regular expression 0*(10)* denotes the same set as: A) (1*0)*1* B) 0+(0+10)+ C) (0+1)*10(0+1)* D) none of the above well according to me in option A we can get 111111...(many no of one's) without the need of 0, but same is not the case with the original R.E posted above, where in i have to get 0's in order to get 1's in my strings. <answer given is option A> what do you say guys??
21
Consider the following regular expressions : (i) ($(a/b)^{*}$ (ii) $(a^{*}/b^{*})^{*}$ (iii) $((\epsilon /a)b^{*})^{*}$ Which of the following statements are correct ? (a) (i) ,(ii) are equal and (ii) , (iii) are not . (b) (i) ,(ii) are equal and (i) , (iii) are not . ... , which can give me (a)* . Isn't it so ? From (i) ($(a/b)^{*}$ : I can not separate a and b . So , how can they all be equal ?
22
Assume $R_1$, $R_2$, and $R_3$ are three regular expressions. Given $R_1 + R_2 \cdot R_3 = (R_1+R_2) \cdot (R_1+R_3)$ for any $R_2$ and $R_3$. Which of the following could be correct condition which always satisfies the above equation. 1. $R_1 = R_2$ 2. $R_1 = R_3$ ... 1 and 2 are correct B) only 1 and 3 are correct C) only 2 and 3 are correct D) 1,2, and 3 are correct Answer is given as D
23
abcd belongs to (b*a*)*(d*c*)*
24
Which of the following statements is TRUE about the regular expression $01^*0$? It represents a finite set of finite strings. It represents an infinite set of finite strings. It represents a finite set of infinite strings. It represents an infinite set of infinite strings.
25
Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$? $(a^* + b^* + c^*)^*$ $(a^*b^*c^*)^*$ $((ab)^* + c^*)^*$ $(a^*b^* + c^*)^*$
26
Which regular expression best describes the language accepted by the non-deterministic automaton below? $(a + b)^* \ a(a + b)b$ $(abb)^*$ $(a + b)^* \ a(a + b)^* \ b(a + b)^*$ $(a + b)^*$
27
Consider the regular expression $R = (a + b)^* \ (aa + bb) \ (a + b)^*$ Which one of the regular expressions given below defines the same language as defined by the regular expression $R$ ? $(a(ba)^* + b(ab)^*)(a + b)^+$ $(a(ba)^* + b(ab)^*)^*(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$
Which of the following regular expressions describes the language over$\{0, 1\}$ consisting of strings that contain exactly two $1$'s? $(0 + 1)^ * \ 11(0 + 1) ^*$ $0 ^* \ 110 ^*$ $0 ^* 10 ^* 10 ^*$ $(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*$
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed integer)
Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string). $(00)^ * (\varepsilon +0)$ $(00)^*$ $0^*$ $0(00)^*$ (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv)