## Regular-Expression

 Question 1

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions

```Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε ```
 A Theory Explanation.
Theory-of-Computation       Regular-Expression       GATE 1998
 Question 2

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

 A 10*(0*10*10*)* B ((0 + 1)*1(0 + 1)*1)*10* C (0*10*10*)*10* D (0*10*10*)*0*1
Theory-of-Computation       Regular-Expression       GATE 2020
Question 2 Explanation:
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
 Question 3
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∊ is divisible by three.
 A (0+1 (01*0)*1)* B (0+11+10(1+00)*01)* C (0*(1(01*0)*1)*)* D (0+11+11(1+00)*00)*
Theory-of-Computation       Regular-Expression       GATE 2021 CS-Set-2
Question 3 Explanation:

Transition table

 0 1 ->*q0 q0 q1 q1 q2 q0 q2 q1 q2

DFA of divisible by 3 The regular expression will be

Three paths to reach to final state from initial state

Path 1: self loop of 0 on q0

Path 2: q0->q1->q0  hence 11

Path 3: q0->q1->q2->q1->q0 hence 10(1+00)*01

So finally the regular expression will be

(0+11+10(1+00)*01)*

Other regular expression is (if we consider two paths)

Path 1: Path 1: self loop of 0 on q0

Path 2: q0->q1->q2*->q1->q0

Hence regular expression

(0+1 (01*0)*1)*

Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)

q0->q1->q2->q1->q0

Another regular expression is

(0*(1(01*0)*1)*)*

So A,B, C are correct.

Option D generates string 11100 which is not accepted by FA hence wrong.

 Question 4
Which one of the following regular expressions correctly represents the language of the finite automaton given below? A ab * bab * ba * aba * B ( ab * b ) * ab * ( ba * a ) * ba * C ( ab * b ba * a ) * ( a * b * ) D ( ba * a ab * b ) * ( ab * ba * )
Theory-of-Computation       Regular-Expression       GATE 2022       Video-Explanation
Question 4 Explanation:
Regular expression ab*bab* +ba*aba* does not generate the string “abb” which is accepted by FA hence this is not true.
(ab*b)*ab*+(ba*a)*ba* does not generate the string “abbaa” hence this is also wrong.
(ab*b+ba*a)*(a*+b*) generates epsilon hence this is also wrong.
(ab*b+ba*a)*(ab*+ba*) is the correct regular expression.
GATE 2022 Computer Science and Information Technology (CS)
 Question 5
In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
 A (L + D)* B (L.D)* C L(L + D)* D L(L.D)*
Theory-of-Computation       Regular-Expression       ISRO-2017 May
Question 5 Explanation:
Option C is correct because it indicates L followed by (L + D)* where * means 0 or more occurences of L or D.
 Question 6
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
 A Set of strings with 2 a’s and 2 b’s B Set of strings with 2 a’s 2 b’s followed by b C Set of strings with 2 a’s followed by b’s which is a multiple of 3 D Set of strings with even number of a’s followed by odd number of b’s
Theory-of-Computation       Regular-Expression       ISRO-2017 December
Question 6 Explanation:
→ Given expression denotes language that accepts set of all strings with even number of a’s followed by the odd number of b’s.
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
 Question 7
Let L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ?
 A (0*10*1)* B 0*(10*10*)* C 0*(10*1*)*0* D 0*1(10*1)10*
Theory-of-Computation       Regular-Expression       ISRO-2016
Question 7 Explanation:
→ The best way to find correct answer is option elimination method.
→ We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (Regular expression: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (Regular expression: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (Regular expression: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
 Question 8
Which of the words below matches the regular expression a(a + b)* b + b(a + b)* a?
 A aba B bab C abba D aabb
Theory-of-Computation       Regular-Expression       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 8 Explanation:
Word should start with an a and end with b, or start with b and end with a.
 Question 9
Regular expression (a|b)(a|b) denotes the set
 A {a,b,ab,aa} B {a,b,ba,bb} C {a,b} D {aa,ab,ba,bb}
Theory-of-Computation       Regular-Expression       Nielit Scientist-C 2016 march
Question 9 Explanation:
● The Regular expression (a|b)(a|b) generates strings of length of 2.
● (a|b) means either a or b.
● The expression consists of two symbols of (a|b),which strings starting with either a or b and ending with either a or b.
 Question 10
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?
 A a*b* B (a | b)* C (ab)​ * D (a | b*)
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 2016 march
Question 10 Explanation:
It is clearly saying that all possible strings over the alphabet {a,b} is (a | b)*
 Question 11
The CFG S → aS|bS|a|b is equivalent to regular expression
 A (a+b) B (a+b)(a+b)* C (a+b)(a+b) D all of these
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 2016 march
Question 11 Explanation:
● The option A gives either a or b expression which is of length of 1
● The option C gives aa,ab,ba or bb which are of length of 2
● But the CFG will produce strings, which of length of greater than 2 also.
● The option B gives string starts with either a or b followed by any number of a’s or b’s which is equivalent to CFG.
 Question 12

Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.

Consider the following:
(i)   L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)

Choose the correct answer from the code given below :

Code :
 A Only (i) is correct B Both (i) and (ii) are correct C Only (ii) is correct D Neither (i) nor (ii) is correct
Theory-of-Computation       Regular-Expression       UGC-NET CS 2018 DEC Paper-2
Question 12 Explanation:
L(s) = {∊, a, b, ab, bb, aa, ba, aab, baa,aaab, aaab,......}
L(r) = { ab, aab, aaab, aaaab, ………… }
L(t) = { b, ab, aab, aaab, aaaab, ……… }
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible string over a, b.
So L(s) ⊆ L(r) and L(t) ⊆ L(r).
L(r) can’t generate “b” but L(t) can’t.
So L(s) ⊆ L(t).
 Question 13
(00+01+10)(0+1)* represents:
 A Strings not starting with 11 B Strings of odd length C Strings starting with 00 D Strings of even length
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 4-12-2016
Question 13 Explanation:
From the expression we can generate strings with any length (even and odd).So option B and D are incorrect.
We can’t generate strings with only 00, we can generate strings starting with 00, 01 and 10 also, So option C is incorrect.
From the given expression (00+01+10)(0+1)*, we can’t generate strings with 11 , we can generate strings starting with 00, 01 and 10.
 Question 14
Which of the following expression results in zero?
 A (0+0+1)(0+0+1) B (0+0+0)(0+1+1) C (1+0+0)(1+1+1) D (0+1+0)(1+0+1)
Theory-of-Computation       Regular-Expression       KVS 22-12-2018 Part-B
Question 14 Explanation:
→ The second option gives zero value.
→ (0+0+0) gives the value 0
→ (0+1+1) gives either 0 or 1.
→ (0+0+0)(0+1+1) gives ), as product of 0 with anything is 0
 Question 15

If r and s are regular expression representing the languages L(r) and L(s), respectively, then which of the following is FALSE?

 A (r)|(s) is a regular expression representing L(r)UL(s) B (r)|(s) is a regular expression representing (L(r))* or (L(s))* C (r)* is a regular expression representing (L(r))* D (r)(s) is regular expression representing L(r)L(s)
Theory-of-Computation       Regular-Expression       JT(IT) 2018 PART-B Computer Science
Question 15 Explanation:
If r and s are regular expressions denoting the languages L(r) and L(s), then
1. Union : (r)|(s) is a regular expression denoting L(r) U L(s)
2. Concatenation : (r)(s) is a regular expression denoting L(r)L(s)
3. Kleene closure : (r)* is a regular expression denoting (L(r))*
(r) is a regular expression denoting L(r).
 Question 16
Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non negative decimal values, does not include even values ?
 A 0*1​ +​ 0*1* B 0*1*0​ +​ 1* C 0*1*0*1​ + D 0+1*0*1*
Theory-of-Computation       Regular-Expression       UGC NET CS 2017 Nov- paper-2
Question 16 Explanation:
Binary numbers can easily find for odd numbers using LSB is 1 and even numbers LSB is 0. Option C won’t contain even numbers
 Question 17
Which of the following strings would match the regular expression : p+ [3 – 5]∗ [xyz]?
I. p443y
II. p6y
III. 3xyz
IV. p35z
V. p353535x
VI. ppp5
 A I, III and VI only B IV, V and VI only C II, IV and V only D I, IV and V only
Theory-of-Computation       Regular-Expression       UGC NET CS 2017 Jan -paper-2
Question 17 Explanation:
This problem looks very difficult but solving procedure is very easy.
Given regular expression is p+[3-5]*[xyz]
It means we have to start with p.
[3-5]* means (3+4+5)* It can generate these numbers many number of times.
[xyz] → ends with either x or y or z or any combination but not violate order of occurrences
I. p443y → matched because it satisfied above regular expression.
Il. p6y → not matched because 6 not present in regular expression.
III. 3xyz → not matched because it not starts with p.
IV. p35z → matched because it satisfied above regular expression.
V. p353535x → matched because it satisfied above regular expression.
Vl. ppp5 → not matched because it is not end with x or y or z or any combination.
 Question 18
The number of strings of length 4 that are generated by the regular expression (0​ +​ 1​ + ​ | 2​ +​ 3​ +​ )*, where | is an alternation character and {+, *} are quantification characters, is:
 A 08 B 09 C 10 D 12
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 Aug- paper-2
Question 18 Explanation:
Consider a=0+1+ and b=2+3+
Hence (0+1+ | 2+3+)* = (0+1+ + 2+3+)* = (a+b)*
Now since the min string in 0+1+ is "01" hence "a" has min length two.
Similarly the min string in 2+3+ is "23" , hence "b"has min length two.
We require 4 length strings. + We can generate 4 length strings using "a" only, or using "b" only or using both.+ Using "a" one time only → 0+1+ only: {0001, 0011, 0111}
using "b" one time only → 2+3+ only : {2223, 2233, 2333}
Using two time, i.e., aa, ab, ba, bb
aa→ 0101
ab→ 0123
ba→ 2301
bb→ 2323
'Hence total 10 strings {0001, 0011, 0111, 2223, 2233, 2333, 0101, 0123, 2301, 2323}
 Question 19
The number of strings of length 4 that are generated by the regular expression (0|∈)1​ +​ 2* (3|∈), where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is :
 A 08 B 10 C 11 D 12
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 July- paper-2
Question 19 Explanation:
Possible strings of length 4 generated by given regular expression are:
1111, 0111, 1112, 0122, 0123, 1222, 1223, 0122, 0113, 1123, 0112, 1113.
So, total 12 strings of length 4 are possible.
 Question 20
Regular expression a+b denotes the set :
 A {a} B {ε, a, b} C {a, b} D None of these
Theory-of-Computation       Regular-Expression       UGC NET CS 2005 Dec-Paper-2
Question 20 Explanation:
The regular expression a+b denotes the set {a, b}.
 Question 21
Which of the regular expressions corresponds to this grammar ?
S →AB/AS, A→a/aA, B→b
 A aa*b​ + B aa*b C (ab)* D a(ab)*
Theory-of-Computation       Regular-Expression       UGC NET CS 2006 Dec-paper-2
Question 21 Explanation: It is clearly representing
aa*b
 Question 22
let r= a(a + b)*, s=aa*b and t=a*b be three regular expressions. Consider the following:
(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)
 A Only (i) is correct B Both (i) and (ii) are correct C Only (ii) is correct D Neither (i) nor (ii) is correct
Theory-of-Computation       Regular-Expression       UGC NET CS 2018-DEC Paper-2
Question 22 Explanation:
L(s) = {∊, a, b, ab, bb, aa, ba, aab, baa,aaab, aaab,......}
L(r) = { ab, aab, aaab, aaaab, ............}
L(t) = { b, ab, aab, aaab, aaaab, .........}
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible
string over a, b. So L(s)⊆L(r) and L(t)⊆L(r)
L(r) can’t generate “b” but L(t) can’t. So L(s)⊆L(t).
 Question 23
Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is
 A (1 + 010)* B (01 + 10)* C (1 + 010)* (0 + λ) D (1 + 01)* (0 + λ)
Theory-of-Computation       Regular-Expression       UGC NET CS 2013 Sep-paper-2
Question 23 Explanation:
L={ null, 0, 1, 01, 10, 11, 010, 011, 101, 110, 111, ...........}
Option A is incorrect because it can generate 010010 string which is having a pair of consecutive zeros.
Option B is incorrect because it can generate 1001 string which is having a pair of consecutive zeros.
Option C is incorrect because it can generate 0100 string which is having a pair of consecutive zeros.
Option D is correct because it will generate all the strings mentioned in the given language L
 Question 24
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
 A a*b B a*baa* C a*ba* D None of the above
Theory-of-Computation       Regular-Expression       UGC NET CS 2013 June-paper-2
Question 24 Explanation:
L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2
L1={ba, baa, baaa, .........................aba, aaba, aaaba,................abaa, abaaa, ....................}
L2={a, ab, abb, abbb, ..........................}
Take "a" from L1:
L1/a ={ b, ba, baa, .................ab, aab, aaab, ....................aba, abaa, .....................}
So we get : a*ba*
If you take "ab" from L2
Like:
L1/ab = you will not get any string i,e. empty set will be in result in case of L1/ab
as no string in L1 end with "ab"
 Question 25
“My Lafter Machin(MLM) recognizes the following strings :
(i) a
(ii) aba
(iii) abaabaaba
(iv) abaabaabaabaabaabaabaabaaba
Using this as an information, how would you compare the following regular expressions ?
(i) (aba)3x
(ii) a.(baa)3x–1. ba
(iii) ab.(aab).3x–1.a
 A (ii) and (iii) are same, (i) is different. B (ii) and (iii) are not same. C (i), (ii) and (iii) are different. D (i), (ii) and (iii) are same.
Theory-of-Computation       Regular-Expression       UGC NET CS 2010 June-Paper-2
Question 25 Explanation:
m is generating single "a".
If you observe all of them is generating (aba)x
Note: This question is ambiguous, the wordings are not very clear.
 Question 26
In a MIU puzzle, either of the letters M, I or U could go as a start symbol. Production rules are given below :
R1 : U → IU
R2 : M.x → M.x.x where . .. is string concatenation operator. Given this, which of the following holds for
(i) MIUIUIUIUIU
(ii) MIUIUIUIUIUIUIUIU
 A Either (i) or (ii) but not both of these are valid words. B Both (i) and (ii) are valid words and they take identical number of transformations for the production. C Both (i) and (ii) are valid words but they involve different number of transformations in the production. D None of these
Theory-of-Computation       Regular-Expression       UGC NET CS 2009 Dec-Paper-2
Question 26 Explanation:
(i) string-> MIUIUIUIUIU
It has M (5 times ) IU
Production 2 says: M.x-> M.x.x
So
MU-> MUU again using it
MUU-> MUUU -> MUUUU ->MUUUUU
Now using prod 1: Last U-> IU
MUUUUU -> MIUUUUU
MIUUUUU -> MIUIUUUU
MIUIUUU ----------------> MIUIUIUIUIU
 Question 27
The regular expression (a ∗ + b) ∗ is equivalent to which of the following regular expressions:
 A a ∗ b ∗ B (a ∗ b + b) ∗ C (a + b ∗ ) ∗ D (a ∗ b) ∗
Theory-of-Computation       Regular-Expression       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 27 Explanation:
(a ∗ + b) ∗ allows any string over {a, b} and is the same as (a + b) ∗ . Option (a) only allows strings of the form a i b j . Options (b) and (d) do not allow strings of the form a i with no b’s.
 Question 28
The regular expression given below describes : r=(1+01)* (0+λ)
 A Set of all string not containing ‘11’ B Set of all string not containing ‘00’ C Set of all string containing ‘01’ D Set of all string ending in ‘0’
Theory-of-Computation       Regular-Expression       UGC NET CS 2007 June-Paper-2
Question 28 Explanation:
L= { λ, 0, 1λ, 01λ, 10, 010, 110, .............}
According to the language L generated by given regular expression
Option(A) is incorrect because L contains 110.
Option(B) is correct because no string is containing 00
Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.
Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.
Hence correct answer is option (B)
 Question 29
For a regular expression e, let L(e) be the language generated by e. If e is an expression that has no Kleene star ∗ occurring in it, which of the following is true about e in general?
 A L(e) is empty. B L(e) is finite. C Complement of L(e) is empty. D Both L(e) and its complement are infinite.
Theory-of-Computation       Regular-Expression       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 29 Explanation:
This is proved by a simple induction on the structure of the regular expression, using the fact that L(a) is finite for each letter a, and that unions and concatenations of finite languages are also finite.
 Question 30
The regular expression for the complement of the language L = {anbm|n ≥ 4, m ≤ 3} is:
 A (λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)* B (λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)* C (λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)* D (λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)*
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 July- paper-3
Question 30 Explanation:
DFA for given language L is  Question 31
Consider the following identities for regular expressions:
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true?
 A (a) and (b) only B (b) and (c) only C (c) and (a) only D (a), (b) and (c)
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 Aug- paper-3
Question 31 Explanation:
The given identities are the closure properties of regular expressions. Following are few identities for regular expressions:
∅* = ε
ε* = ε
RR* = R*R
R*R* = R*
(R*)* = R*
RR* = R*R
(PQ)*P =P(QP)*
(r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)*
Hence option(D) is correct.
 Question 32
How many states are there in a minimum state automata equivalent to regular expression given below?
regular expression is a*b(a+b)
 A 1 B 2 C 3 D 4
Theory-of-Computation       Regular-Expression       UGC NET June-2019 CS Paper-2
Question 32 Explanation:
L={ba,bb,aba,abb,...}
Please note: it is asked about minimum finite automata (so its about min NFA and not min DFA) Question 33
Consider the following non-deterministic automaton, where s1 is the start state and s4 is the final (accepting) state. The alphabet is {a, b}. A transition with label  can be taken without consuming any symbol from the input. A (a + b)∗aba B aba(a + b)∗aba C (a + b)aba(b + a)∗ D aba(a + b)∗ E (ab)∗aba
Theory-of-Computation       Regular-Expression       TIFR PHD CS & SS 2018
 Question 34
The regular expression corresponding to the language L where L = { x ε {0, 1}*|x ends with 1 and does not contain substring 00 } is:
 A (1 + 01) * (10 + 01) B (1 + 01) * 01 C (1 + 01) * (1 + 01) D (10 + 01) * 01
Theory-of-Computation       Regular-Expression       UGC NET CS 2015 June Paper-3
Question 34 Explanation:
L = { 1, 01, 11, 111, 001, ............}
Option(A) is not correct because it can generate “10” which is not ending with “1”.
Option(B): It can’t generate “1” which is a string belongs to given language L. So it is not a correct option.
Option(C) : It is the correct option because it can generate all the strings generated by a given language.
Option(D): It is not the correct answer because it can’t generate strings like 1,11,........
 Question 35
Let L be the language on A={a,b,c} which consists of all words of the form w=ar bs ct where r,s,t>0. Which of the following is the valid regular expression ‘r’ such that L=L(r)?
 A r= a*b*c B r= aa*bb*c C r= aa*b*cc D r= aa*bb*cc*
Theory-of-Computation       Regular-Expression       CIL Part - B
Question 35 Explanation:
→From the given question, w=ar bs ct where r,s,t>0 which means that the minimum value is r=s=t=1,
→Substitute in r=s=t=1 in w then L= abc
→So option D gives the regular expression abc
 Question 36
Consider the following grammar:
```S → Ax |By
A → By|Cw
B → x|Bw
C → y ```
Which of the regular expressions describes the same set of strings as the grammar?
 A xw+y+xw*yx+ywx B xwy+xw*xy*ywx C xw*y+xw*yx+ywx D xwxy+xww*yywx
Theory-of-Computation       Regular-Expression       TNPSC-2012-Polytechnic-CS
Question 36 Explanation:
Option A do not contain xy which is generated by the grammar.
Option B do not contain xy which is generated by the grammar.
Option C do not contain xy which is generated by the grammar.
 Question 37
Let a and b be the regular expressions, then (a*∪b*)* is not equivalent to
 A (a∪b)* B (b*∪a*)* C (b∪a)* D (a∪b)
Theory-of-Computation       Regular-Expression       TNPSC-2012-Polytechnic-CS
Question 37 Explanation:
The given regular expression is not equal to option D.
 Question 38
Regular expression for the complement of language L = {an bm | n ≥ 4, m ≤ 3} is
 A (a + b)* ba(a + b)* B a* bbbbb* C None of the above
Theory-of-Computation       Regular-Expression       UGC NET CS 2014 Dec - paper-3
Question 38 Explanation:
L= { aaaa, aaaab,aaaab,aaaabb,aaaabbb,aaaaa,..............}
Option (A) is incorrect because the smallest string it can generate is “ba” which does not belong to L.
Option (B) is incorrect because the smallest string it can generate is “bbbb” which does not belong to L.
Option (C) is incorrect because the smallest string it can generate is “λ” which does not belong to L.
Regular expression for given language L is aaaaa*(λ +b+bb+bbb)
Hence option(D) is the correct answer.
 Question 39
Consider the following non-deterministic automaton, where s1 is the start state and s4 is the final (accepting) state. The alphabet is a, b . A transition with label s can be taken without consuming any symbol from the input.
Which of the following regular expressions corresponds to the language accepted by this automaton?
 A (a + b)∗aba B (a + b)∗ba∗ C (a + b)∗ba(aa)∗ D (a + b)∗ E (a + b)∗baa∗
Theory-of-Computation       Regular-Expression       TIFR PHD CS & SS 2019
 Question 40
Which of the following regular expressions correctly accepts the set of all 0/1-strings with an even (possibly zero) number of 1s?
 A (10∗10∗)∗ B (10∗10∗1)∗ C 0∗1(10∗1)∗10∗ D 0∗1(0∗10∗10∗)∗10∗ E (0∗10∗1)∗0∗
Theory-of-Computation       Regular-Expression       TIFR PHD CS & SS 2017
 Question 41
Let a, b, c be regular expressions. Which of the following identities is correct ?
 A (a + b)* = a*b* B a(b + c) = ab + c C (a + b)* = a* + b* D (ab + a)*a = a(ba + a)* E None of the above
Theory-of-Computation       Regular-Expression       TIFR PHD CS & SS 2015
 Question 42
A string that is NOT generated by the Regular Expression 1*(01)*0* is
 A 00 B 10 C 010 D 011
Theory-of-Computation       Regular-Expression       HCU PHD CS 2018 December
Question 42 Explanation:
All the strings given in options except option D are generated by the given regular expression.Means 011 is not generated by given regular expression.
 Question 43
A word that does NOT get accepted by the Regular Expression (01* + 10)* is
 A 00 B 11 C 100 D 1001
Theory-of-Computation       Regular-Expression       HCU PHD CS 2018 June
Question 43 Explanation:
whatever string is generated by given regular expression ,it must contain atleast one 0, but option B do not have any 0.So string in option B cannot be generated.
 Question 44
A Regular Expression for the language L over the alphabet Σ={a,b)* consisting of strings with exactly 2b's is
 A a*ba*ba* B a*bba* C bba* D a*bb
Theory-of-Computation       Regular-Expression       HCU PHD CS MAY 2015
Question 44 Explanation:
Option B is false because string abab will not be generated by the given regular expression.
Option C is false because string abab will not be generated by the given regular expression.
Option D is false because string abab will not be generated by the given regular expression.
Option A can generate all the strings with exactly two b’s.
 Question 45
Which of the following regular expression is equivalent to (a* + b)*(c + d) ?
 A a*(c + d) + b(c + d) B a*(c + d) + b(c + d) C (a* + b)c + (a* +b)d D (a+b)*c + (a + b)*d
Theory-of-Computation       Regular-Expression       HCU PHD CS MAY 2016
Question 45 Explanation:
Lets check option D,
Given (a+b)*c + (a + b)*d
Now take (a+b)* out as common ,then we will get (a+b)*(c+d).and we know that
(a*+b)* = (a+b)*.So we can also write (a+b)*(c+d) as (a* + b)*(c + d) .
 Question 46
Which of the following regular expression is equivalent to (a* + b)*(c + d)?
 A a*(c * d) + b(c + d) B a*(c * d) + b*(c + d) C (a + b)*c + (a + b)*d D (a* + b)c + (a* + b)d
Theory-of-Computation       Regular-Expression       HCU PHD CS MAY 2012
Question 46 Explanation:
Option A cant generate string ‘c’ which can be generated by the regular expression in the question.
Option B cant generate string ‘abc’ which can be generated by the regular expression given in question.
Option D cant generate string ‘abbc’ which can be generated by the regular expression given in the question.
Option C is correct answer because
(a + b)*c + (a + b)*d = (a+b)* (c+d) = (a*+b)*(c+d)
 Question 47
Consider the following regular expressions: a) r=a(b+a)* b) s=a(a+b)* c) t=aa*b Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:
 A L(r)⊆L(s)⊆L(t) B L(r)⊇L(s)⊇L(t) C L(r)⊇L(t)⊇L(s) D L(s)⊇L(t)⊇L(r)
Theory-of-Computation       Regular-Expression       UGC NET JRF November 2020 Paper-2
Question 47 Explanation:
r={a,aa,ab,aaa,aab,aba,aaab,......}
s={aa,ab,aaa,aab,aba,aaab,......}
t={ab,aab,aaab,....}
If you notice then r⊇s⊇t
 Question 48
Let L1 and L2 be languages over Σ =(a,b) represented by the regular expressions (a* + b)* and (a+b)* respectively. Which of the following is true with respect to the two languages?
 A L1 ⊂ L2 B L2 ⊂ L1 C L1 = L2 D L1 ∩ L2 = ɸ
Theory-of-Computation       Regular-Expression       UGC NET JRF November 2020 Paper-2
Question 48 Explanation:
(a+b)* is a universal set which can generate all the strings possible over the alphabet “a” and “b”.
(a+b)* = (a* +b)*= (a+b*)=(a*b*)*= (a* +b*)*= a*(ba*)*=b*(ab*)*
 Question 49
Consider the following regular expressions over alphabet {a, b}, where the notation (a + b)+ means (a + b)(a + b)* :
r1 = (a + b)+ a (a + b)*
r2 = (a + b)*b (a + b)+
Let L1 and L2 be the languages defined by r1 and r2, respectively. Which of the following regular expressions define L1 ∩ L2?
 A (a + b)+ a (a + b)*b (a + b)+ B (a + b)* a b (a + b)* C (a + b)*b (a + b)* a (a + b)* D (a + b)* a (a + b)*b (a + b)*
Theory-of-Computation       Regular-Expression       CMI 2020
Question 49 Explanation:
L1 is the set of all words of length n ≥ 2 containing an a at one of the positions 2, · · · , n. L2 is the set of all words of length n ≥ 2 containing a b in one of the positions 1, · · · , n − 1. The intersection L1 ∩ L2 is the set of all words containing a b at one of the positions 1, . . . , n − 1 and an a at one of the positions 2, . . . , n. This is given by the expression in (c).
Option (a) is incorrect since it accepts only words of length at least 4.
Option (b) is incorrect since it accepts ab, which is not in L1 ∩ L2.
Option (d) is incorrect once again as it accepts ab.
 Question 50
Which of the following regular expressions represents binary strings that are multiples of 3? Note that we consider the leftmost bit to be the most significant.
 A ((11)0*)* B 1(01*)* C (10*)* D (11 + 101*01 + 0)*
Theory-of-Computation       Regular-Expression       CMI 2021
Question 50 Explanation:
Let L(r) denote the language represented by the regular expression r.
(a) It can be checked that L(((11)0*)*) does not contain the string 1001, which represents 9.
(b) L((10*)*) contains 1, which represents a non-multiple of 3.
(c) L(1(01*)*) contains 101 (representing 5), as also 1 (representing 1).
(d) This is the only remaining option. One can prove it by first constructing a DFA for binary strings that are multiples of 3 and converting it to a regular expression.
 Question 51 A Only (i) is false B Only (ii) is false C Only (iii) is false D Both (i) and (iii) are false E None of the above
Theory-of-Computation       Regular-Expression       TIFR PHD 2022
There are 51 questions to complete.