search
Log In

Recent questions tagged regular-expressions

2 votes
1 answer
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
asked Nov 5, 2015 in Theory of Computation focus _GATE 187 views
19 votes
3 answers
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)^*$
asked Oct 10, 2015 in Theory of Computation makhdoom ghaya 1.3k views
3 votes
3 answers
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.
asked Sep 29, 2015 in Theory of Computation Mojo-Jojo 899 views
2 votes
2 answers
6
2 votes
1 answer
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
asked Sep 28, 2015 in Theory of Computation Mojo-Jojo 468 views
0 votes
2 answers
8
1 vote
2 answers
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 :)
asked Sep 15, 2015 in Theory of Computation Tushar Shinde 436 views
2 votes
6 answers
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
asked Sep 13, 2015 in Theory of Computation Ankit Chourasiya 512 views
2 votes
5 answers
11
3 votes
3 answers
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^*)^*$
asked Aug 17, 2015 in Theory of Computation ari 2.1k views
6 votes
1 answer
13
6 votes
6 answers
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
asked Jul 17, 2015 in Theory of Computation Vivek sharma 5.8k views
4 votes
2 answers
15
5 votes
3 answers
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.
asked Jun 22, 2015 in Theory of Computation sumit kumar 350 views
4 votes
2 answers
18
Q which of the following pair of regular expressions are not equal a)∅* & ∈* 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
asked Jun 22, 2015 in Theory of Computation sumit kumar 257 views
4 votes
4 answers
19
Q) which of the following pair of regular expressions are equal a)(0+1)* & 0* + 1* b)∅* & ∅* 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*?? .
asked Jun 22, 2015 in Theory of Computation sumit kumar 259 views
6 votes
3 answers
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??
asked Jun 12, 2015 in Theory of Computation sumit kumar 860 views
5 votes
4 answers
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 ?
asked May 30, 2015 in Theory of Computation worst_engineer 2k views
5 votes
2 answers
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
asked Jan 27, 2015 in Theory of Computation Vikrant Singh 712 views
4 votes
1 answer
23
26 votes
3 answers
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.
asked Nov 3, 2014 in Theory of Computation Ishrat Jahan 4.7k views
20 votes
5 answers
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^*)^*$
asked Nov 2, 2014 in Theory of Computation Ishrat Jahan 4.8k views
20 votes
7 answers
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)^*$
asked Oct 31, 2014 in Theory of Computation Ishrat Jahan 2.4k views
26 votes
7 answers
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)^+$
asked Oct 31, 2014 in Theory of Computation Ishrat Jahan 6.7k views
18 votes
2 answers
28
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) ^*$
asked Oct 28, 2014 in Theory of Computation Ishrat Jahan 4.3k views
19 votes
5 answers
29
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)
asked Oct 17, 2014 in Theory of Computation Arjun 3.3k views
24 votes
4 answers
30
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)
asked Oct 9, 2014 in Theory of Computation Kathleen 4.7k views
...