Basic TOC Regular - Sloution

GATE Computer Science & IT
BASIC
THEORY OF COMPUTATION
ctice Questions Booklet

ANALYSIS OF THEORY OF COMPUTATION GATE PAPER
Years Marks
2015 5
2016 9
2017 10
2018 8
2019 5
2020 9
2021 Set-1 8
2021 Set-2 10
THEORY OF COMPUTATION FOR GATE SYLLABUS
 Chomsky classification of grammar.
 Regular languages
 Regular expression
 Regular grammar
 Finite Automata (DFA/NFA)
 Conversion from NFA to DFA
 Minimization of DFA
 Closure Properties
 Mealy /Moore machine
 Pumping Lemma for regular language
 Context free language
 Properties
 Context –free grammar
 PDA (Push down-automata)
 Chomsky Normal Form
 Greibach Normal Form
 CYK algorithm
 Pumping Lemma for Context Free Language
 Turing Machine
 TM Construction
 Turing decidable Language (Recursive language)
 Turing Machine recognizable(Recursively enumerable language)
 Undecidable / decidable problem.
 Countable / uncountable sets.
 Book Reference:
 An Introduction to formal languages and automata by “PETER LINZ”
 An introduction to Automata Theory, Language & computation by
“Ullmann, Hopcraft&Motwani”
TABLE OF CONTENTS
S. No. CHAPTERS P. No.

1 REGULAR LANGUAGE 1
2 CONTEXT FREE LANGUAGE 53
3 TURING MACHINES 92
4 TOC-TEST- 1 111
5 TOC-TEST- 2 115
REGULAR LANGUAGE
Q1. Consider the follwing grammar G:

SaSa | aAa
ABb
Bc
The grammar G belongs to which type of Chomsky classification?

(A) Type 3
(B) Type 2 but not type 3
(C) Type 1 but not type 2
(D) Type 0 but not type 1
Q2. Consider the following grammar G with start symbol S

Sa SC| T
TbTd|R
dCCd
RCCr
R
BASIC THEORY OF COMPUTATION Page 1

What is the highest type number that can be assigned to the following grammar?
(A)Type 0 (B) Type1
(C) Type2 (D) Type 3
Q3. Consider the following grammar G with start symbol S

S→Aa,
A→Ba,
B→abc.
(A) Type 0 (B) Type 1
(C) Type 2 (D) Type 3
Q4. What is the highest type number that can be assigned to the following grammar?
S → aA | bB
A → aB | bC
B → aB | bB
C → aC | bC | λ

(A) Type 0
(B) Type 1
(C) Type 2
(D) Type 3
Q5. Consider the following grammar G with starting symbol S:

S → bTbb
T → bTbb | Acccb
A → aAc | λ
(A) Type 0
(B) Type 1
(C) Type 2
(D) Type 3

Q6. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
AB → CD
CD → CE
C → aC
C → b
bE → bc is
(A)is type 3 (B) is type 2 but not type 3
(C)is type 1 but not type 2 (D) is type 0 but not type 1

Q7. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = (a, b, c}
P : S → ABCD
BCD → DE
D → aD
D → a
E → bE
E → c is
(A) is type 3 (B) is type 2 but not type 3
(C) is type 1 but not type 2 (D) is type 0 but not type 1
Q8. A grammar has the following productions:

S  aSSb | a | bSa
Which of the following sentences are in the language that is generated by this grammar?
(A) aaaaabb (B) aabbaabb
(C) bbbaabbaa
(D) All of the answers above are correct

Q9. Consider the grammar below, with start symbol S.
S  AS | SB | 
A  Aa | a
B  Bb | b
Which of the following strings can‟t be generated by this grammar?
(A) a (B) abb (C) abba (D) aaabbb

Q10. Consider the following grammar G:
S→AB |aB A→aab| λ B→bbA
If the language accepted by G is L(G) then which of the following set of string is the subset
of the L(G)?
(A) {bbaa, abb,bb} (B) {bbaa, bba, abb}
(C) {aab, abb} (D) None of these

Q11. Consider the language L = {w : for some u  Σ*, w = uRu}.Which of the following
strings belongs to L?
(i) aaabbb (ii) abab
(iii) abba (iv) 
(A) (i) and (ii) (B) (iii) only
(C) (iv) only (D) (iii) and (iv)
Q12. Consider the grammar G:

S → AB
A → 0A1 | 2
B → 1B | 3A
Which of the following strings is in L(G)?
(A) 0211300021 (B) 021300211
(C) 00213021 (D) 0021113002111

Q13. Identify in the list below a sentence of length 6 that is generated by the grammar
S →(S)S| λ
(A) ( ) ( ) ( ) (B) ) ) ) ( ( (
(C) ) ) ( ( ) ( (D) ) ( ( ) ( )

S → AB
A → 0A1 | 2
B → 1B | 3A
Which of the following strings are in L (G)?
i) 021300211 ii) 002111300211
iii) 00211100211 iv) 0021113002111
(A)i and ii (B)iii only
(C)iii and iv (D)i,ii and iv
Q15. A grammar is described as follow:

SaS
S  b
S bA
A bB
B  a
Which of the following strings cannot be derived from the above grammar?
(A) abba (B) abbb
(C) bba (D) aab

Q16. Which of the following strings cannot be derived from the symbol S using the rules
S → SS | aaa | aaaaa ?
(A) aaaaaa (B) aaaaaaa
(C) aaaaaaaa (D) aaaaaaaaa

Q17. Consider the grammar given below
S →xB | yA
A → x | xS | yAA
B → y | yS | xBB
Consider the following strings.
i. xxyyyxyxyxy ii. yyxxyyxx
iii. yxxyxyxy iv.xxyyxy
Which of the above strings are generated by the grammar?
(A) i and ii only (B) ii , iii and iv only
(C) i, ii and iii only (D) All the above

Q18. Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S
as the start symbol:
S ->abScT | abcT
T ->bT | b
Which of the following string is not generated by given grammar?
(A) ababcbbcbbb (B) ababcbcb
(C) abababcbcbbcbb (D) ababcbcbbcb

Q19. Consider the following grammar
S → XY | W
X → aXb | 
Y → cY | 
W → aWc | Z
Z → bZ | 
What is the language generated by this grammar?
(A){ aibjck | i, j, k ≥ 0, and i = j = k }
(B){ aibjck | i, j, k ≥ 0, and i = j or i = k }
(C){ aibjck | i, j, k ≥ 0, and i = j or j = k }
(D){ aibjck | i, j, k ≥ 0, and i ≠ j or i ≠ k }
S → aSc | X
X → bXc | 

(A) { aibjck | i, j, k ≥ 0, and i + j = k }
(B) { aibjck | i, j, k ≥ 0, and i = j+ k }
(C) { aibjck | i, j, k ≥ 0, and k= i- j }
(D) None of the above

Q21. Consider the following language
S ->AX | Y C
A aA |
C cC | |
X bXc | |
YaY b ||
L(G) is
(A) L(a*b*c*)
(B) {anbncn | n >=0}
(C) {aibjck | i = j or j = k}
(D) none of the above

Q22. What is the language of the grammar with the following production rules?
S ASb | c Aa
(A) {ancbn | n  N}
(B) {xcb | x {a}*}
(C) {acy | y  {b}*}
(D) All of the answers above are incorrect
Answer: D
Solution: S ASb | c A a
⟹ S aSb | c
⟹ 𝐿 = 𝑎𝑛 𝑐𝑏𝑛 𝑛 ≥ 0}
If You take N = {0, 1, 2, 3 …} then option (a) will be correct. But it is not mention in the
question N contains 0 or not. So, option D is correct.
Q23. Which language generates the grammar G given by the productions?

S → aSa | aBa B → bB | b
(A) L(G) = { anbman | n >0, m >0}. (B) L(G) = { anbman | n >0, m <0}.
(C) L(G) = { banb| n >0, m >0}. (D) None of these

S → aSbb|
The language generated by the above grammar is:
(A)L={anbn:n≥0} (B)L={anb2n:n≥0}
(C) L={ambn:n≥0} (D)None

Q25. The language generated by the following grammar is:
S  0S1 | C C  1C0 | 
(A) L1 = {0 1 0 1n | n, m ≥0}
n m m (B) L1 = {0m12n0n1n | n, m ≥ 0}
(C) L1 = {0n1m02m1n | n, m ≥ 0} (D) L={0n1n1m0m |n, m ≥ 0}
Q26. Consider the following grammar G with start symbol S over the alphabet Σ = {a, b}
S → aSaa | B
B → bB | λ
The language generated by G is
L1 = {anbna2m |n, m ≥ 0} L2 = {anb2m |n, m ≥ 0}
L3 = {anbma2n |n, m ≥ 0} L4 = {anbma2m |n, m ≥ 0}
(A)L1 (B) L2
(C)L3 (D)L4

Q27. Consider the following language:
L = {akb2k | k >=2}
Which of the following grammar generates L?
(A) S  aSbb | λ
(B) S  aSbb | abb
(C) S  aSbb | aabbbb
(D) S  aX | bbY X  aX | λ Y  bbY | λ
Answer: C
Solution: L = {akb2k | k >=2} = {aabbbb, aaabbbbbb …}
(A) S  aSbb | λ  L = {akb2k | k >=0}
(B) S  aSbb | abb  L = {akb2k | k >=1}
(C) S  aSbb | aabbbb  L = {akb2k | k >=2}
(D) S  aX | bbY X  aX | λ Y  bbY | λ
 L = aa* + bb(bb)*
So, option C is correct.
Q28. Consider the following language:
L = {abn | n >= 0}  {(ba)m | m > = 0}
(A) S  abS | baS | λ
(B) S  aX | bY X  bX | λ Y  baY | λ
(C) S  aX | baY X  bX | λ Y  baY | λ
Answer: D
Solution:

Q29. Consider the Grammar G, with productions.
SaA | , AbS
Which of the following language are generated by G?
(A) L = {anbn|n>0}
(B) L = {anbm| n>0, b>0}
(C) L = {(ab)n | n≥0}
(D) L = {(ab)n |n>0

Q30. Which language generates the grammar G given by the productions
S → aSdd | A
A → bAc | bc
(A) L(G) = { an bmcm d2n | n 0, m >0}
(B) L(G) = { ambmcnd2n | n 0, m >0}
(C) L(G) = {aibmcm d2n |i>0, n 0, m >0}
(D) L(G) = { an bicjd2n | n 0, i>0, j > 0}

S → aXa | bXb | a | b
X → aX | bX | λ
(A) All strings that start and end with the same symbol.
(B) All nonempty strings that start and end with the different symbol.
(C) All nonempty strings that start and end with the same symbol.
(D) None of the above.

Q32. The language generated by the following grammar is
S→ aB| bA
A→ a|aS|bAA
B→ b|bS|aBB
(A) Strings contain equal number of a's and equal number of b's.
(B)Strings contain odd number of a's and odd number of b's.
(C)Strings contain odd number of a's and even number of b's.
(D)Strings contain even number of a's and even number of b's.

S → 0S0 | 0S1 | 1S0 | 1S1 | 0
(A){w  {0, 1}* | the length of w is odd }
(B){w  {0, 1}* | the length of w is odd and the middle symbol is 0 }
(C){w  {0, 1}* | the length of w is odd and the middle symbol is 1 }
(D){w  {0, 1}* | w contains 0 in middle }

S → Aa | MS | SMA
A → Aa | λ
M → λ | MM | bMa | aMb
(A) All strings with more a‟s than b‟s.
(B) All strings with one more a‟s than b‟s.
(C) All strings with more b‟s than a‟s.
(D) All strings with equal a‟s and b‟s.

Q35. How many of the following is/are true? _________
(i) baa a*b*a*b* (ii) b*a*  a*b* = a*  b*
(iii) a*b*  c*d* =  (iv) abcd (a(cd)*b)*

Q36. Determine whether the strings in the table belong to any of the languages described
by the following regular expressions
(i) For 1001 : T, F, F, F, F (ii) For 110 : F, F, F, F, T

(A) i only (B) ii only
(C) Both i & ii (D) Neither i nor ii
Can be deived
Q37. Which of the following is not in the set of strings denoted by the regular expression R = (a*
b c*)*?
(A) aabc (B) bacd
(C) abcbc (D) babbc

Q38. Which of the following strings are generated by the regular expression
(ab)*..(a+b+∅).ba?
(i) 
(ii) aba
(iii) ababba
(iv) abababa
(A) ii, iii and iv only (B) ii and iv only
(C) i and ii only (D) All the above

Q39. Which of the following strings is a member of the language described by the regular
expression: (a*ba*ba*ba*)*
(A) bbbb (B)bbaaabb
(C) bbaaabbbabb (D) bbabbbab

Q40. Someone has asserted that the following two regular expressions describe the same
language: R1 = ((ab*a) + (ba*b))* and R2 = ((ab*a) + b*)*. Which of the following
strings is contained in one of the languages but not in the other?
(A) ababab (B) bbbbbb
(C) abba (D) bbabba

Q41. The regular expression b*ab*ab*ab* represents the language
(A) L = {w : w *, na(w) = 3}
(B)L = {w : w * na(w) <=3}
(C) L = {w : w * na(w) >= 3 }
(D) none
Q42. The regular expression b* + b*ab*+ b*ab*ab* represents the language

(A) L = {w : w *, na(w) = 2}
(B) L = {w : w * na(w) <=2}
(C) L = {w : w * na(w) >= 2 }
(D) none

Q43. Which of the following pair of regular expression is/are true?
I. (01 +0)*0  0(10 +0)* II. 0(120)*12 01(201)*2
III. * λ* IV. (0*1*)*  (1*0*)*
(A) I, III and IV only (B) II and III only
(C) II, III and IV only (D) All the above
Q44. Regular expression r = (aa*b)* (aa* + ) is equivalent to:

(I) (ab)* (a+)
(II) a*(ab)*
(III) (b+ba)*
(IV) (a+ab)*
(V) (aa*b)*
(A) IV and V (B) I, II and III
(C) II, IV and V (D) IV only

Q45. Identify the pairs of regular expressions that are equivalent (in that they describe
the same sets of strings):
(I) (ab)+ (ab)*ab
(II) ab* (ab)*
(III) (a|b+) (a|(b)+)
(IV) a+* a+
(V) a*a (ba*a)* (a + ab)*a.
(A)I, II and III only (B)I and III only
(C)I, III and V only (D)All are equivalent

Q46. Match the regular expression with its description
(1) (0∪1)*01(0∪1)* i. All strings which doesn‟t contain the substring 101.
(2) 1*0* ii. Strings containing the substring 01.
(3) (10∪0)*(1∪10)* iii. Strings of the form 111 . . . 000 . . ., that is, strings that
begins with Zero or more ones followed by zero or more
zeroes
(4) 0*(1∪000*)*0* iv. All strings where each occurrence of 00 precedes all
Occurrences of 11

(A) 1-ii,2-iii,3-i,4-iv (B) 1-ii,2-iii,3-iv,4-I
(C) 1-iv,2-iii,3-ii,4-i (D) 1-iii,2-ii,3-i,4-iv
Q47. How many of the following is/are true? __________

(i) (ab)*a = a(ba)*
(ii) (a b)* b (a  b)* = a* b (a  b)*
(iii) [(a  b)* b (a  b)*  (a  b)* a (a  b)*] = (a  b)*
(iv) [(a  b)* b (a  b)*  (a  b)* a (a  b)*] = (a  b)+
(v) [(a  b)* b a (a  b)*  a*b*] = (a  b)*

Q48. [MSQ]
Which of the following regular expressions are equivalent to the regular expression
R = (bba + aab + ab + b + a)+ + λ
(A)(a*b*)* (B)(a*b*)+ + λ
(C)(a + b + aa)* (D) (a + b)*

Hence all (A), (B), (C), (D) are Correct .
Q49. [MSQ]
Which of the following regular expression is equivalent to given regular expression:
ε+1*(011) *(1*(011) *) *
(A) (1+011) * (B) (1*(011) *)
(C) (1+(011) *) * (D) (1011) *
Answer: A, C
Explanation: We know that ε + RR*= ε + R*R= ε + R+= R*.
So, ε + 1*(011) *(1*(011) *) * = (1*(011)*)* = (1 + 011)*.
It is also equivalent to (1 + (011)*)*.

Q50. If r and s are regular expressions, write r ≤s to mean that the language of strings matching r
is contained in the language of strings matching s. Then which of the
following is/ are true?
(i) r*|s*≤(r|s)*
(ii) (r|s)*≤r*|s*
(iii)(r*s*)*≤ (r|s)*
(iv) (r|s)*≤(r*s*)*
(v) (rs|r)*r≤r(sr|r)*
(A) i, ii, iii only (B)i, iii, iv only
(C)ii, iii, iv only (D) All except ii

Q51. Which of the following is true?
(i) (01)*0 = 0(10)*
(ii)(0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
(iii) (0+1)*01(0+1)*+1*0* = (0+1)*
(iv) (0(0+1)*1 + 1(0 + 01)*0)* = (01 + 10)*
(A) i only (B) i and iii only
(C) i, ii and iii only (D) All the above

Q52. Consider the following four regular expressions over the alphabet {a, b}:
E1 = (ab + a*b*b*)*
E2 = ((ab)* (a*b*b*)*)*
E3 = (a + b)*
E4 = a(a + b)*
Which of the following statements is true?
(A) L(E2) = L(E3) (B) L(E3) = L(E4)
(C) L(E1) = L(E4) (D) L(E2) = L(E4)

Q53. What will be the regular expression for language L = {xwx : x, w  {0, 1}*, |x|≤3}?
(A) (0+1)3 (0 + 1)*(0+1)3
(B) ((0+1)+(0+1)2+(0+1)3) (0 + 1)* ((0+1)+(0+1)2+(0+1)3)
(C) (λ + (0+1)+(0+1)2+(0+1)3) (0 + 1)*(λ + (0+1)+(0+1)2+(0+1)3)
(D) None of these

Q54. What will be the regular expression for the following language
L1 = {pwp: p, w {0, 1}*, |p|=7, kI+}?
(A) (0+1)7 (0 + 1)*(0+1)7
(B) ((0+1)+(0+1)2+(0+1)3 +… +(0+1)7) (0 + 1)* ((0+1)+(0+1)2+(0+1)3+… +(0+1)7)
(C) (λ + (0+1)+(0+1)2+(0+1)3+… +(0+1)7) (0 + 1)*(λ + (0+1)+(0+1)2+(0+1)3+… +(0+1)7)
(D) Both a and b
Answer: None
Solution: L1 = {pwp: p, w {0, 1}*, |p|=7}
Both p should be same AND |p| = 7. So, it has 27 possibilities.
L1 = 07 (0+1)* 07 + 061(0+1)* 06 1 + … + 17 (0+1)*17
Q55. The regular expression (a + b)*a(a + b)* represents the language

(A) Contains exactly 1 a
(B) Contains at least 1 a
(C) Contains at most 1 a
(D) none
Q56. The regular expression (b*ab*ab*)* represents the language
(A) L = {w : w *, na(w) is divisible of 2 }
(B) every b is followed by at least one a
(C) L = {w : w * na(w) >= 2 }
(D) None of these.

Q57. Which of the following regular expressions generate all the strings with even
Numbers of 0?
(i)1*(00)*1* (ii) 1*(010)*1* .
(iii) (1*01*01*)* (iv) 1*(01*0)*1*
(A)iii and iv only (B)ii, iii and iv only
(C)iv only (D)iii only

Q58. Which of the following expression best describes the language L = {{0, 1}* |  contains
1‟s only}
(A) 1* (B) 1+
(C) 0 + 1* (D) 1.(1)+
Q59. Which of the following expression best describes the language

L = {{0, 1}* |  contains only 0‟s or only 1‟s}
(A) 0* + 1* (B) (00+) + (11+)
(C) 0+ + 1+ (D) 0(0 + 1)*1
Q60. Let  = {0, 1}, and language over, L = {*|  contains odd number of 1‟s}. Which
Of the following regular expression best describes the given language?
(A) 0*(10*10*)*10* (B) 0*1(11)* 0*
(C) 0*1*0*1*0*1 (D) 1(11)*

Q61. Let  = {0, 1}, and language over ,
L = {*| any two 0‟s in  are separated by three 1‟s}. Which of the following
regular expression best describes the given language?
(A) (01110)* (B) (01110)* + 1*
(C) 1*(01110)* + 1* (D) 1*(0111)*01* +1*
Q62. Let  = {0, 1}, and language over, L = {*|  is a binary number divisible by 4}.
Which of the following regular expression best describes the given language?
(A) (0+1)*00 (B) (0+1)*0
(C) (0+1)* 000 (D) (0+1)* 100

Q63. Let  = {0, 1}, and language over, L = {*|  does not contain 11}. Which of the
Following regular expression best describes the given language?
(A) 0*(10)* (B) 0*(10+)* (1+)
(C) (0*10*10*)* (D) (0+10)*

Q64. Which of the following regular expression generate all the strings with odd numbers
of 1?
(A) 0*10*(10*1)* (B) 0*10*(10*1)*0*
(C) 0*10*(101)*0* (D) 0*(10*10*1)*0*
Answer: None
Solution:

Q65. Which of the following regular expressions define the same language?
(1) (ab)* (2) (aa*b)* a*
(3) a*b* (4) a* (aba*)*
(A) 1 and 3 only (B) 2 and 4 only
(C) 3 and 4 only (D) All define different languages

Q66. Consider the language defined by the regular expression (a|b)*b+. Which of the
following regular expression(s) also define that language?
(1) (a*b+) | (b*b+)
(2) (ab | bb)* b*
(3) (a | b | ba)*b+
(A) (1) and (2) (B) (2) and (3)
(C) Only (3) (D) Only (2)

Q67. Which of the following defines a language different than the others?
(A)The regular expression (a | b)* a b c
(B) The regular expression (a* b*)* a b c
(C)The regular expression (a | b) (a | b)* c
(D)All are same

Q68. Which of the following statement is / are correct?
I. (a* b*) a b c ≡ (a | b )* a b c
II. (a*b*)*a b c ≡ (aa + ba + a*b + (bb)*a)* a b c
(A) I only
(B) II only
(C) Both I & II
(D) Neither I nor II

Q69. What is the best description of languages denoted by the following regular
expressionR = 0( 0+1)*0?
(A) strings of zeros and ones with zeros occurring more frequently than ones
(B) strings from alphabet {0,1} which begin and end with a zero
(C) strings from alphabet {0,1} which begin and end with a zero and have an even
number of zeroes
(D) strings from alphabet {0,1} which begin with one or more zeros, followed by zero
or more 3ones, followed by a zero.

Q70. What is the best description of the languages denoted by the following regular
expressionsR = ((11 + 0)*)*
(A)strings from the alphabet {0,1} in which there are an even number of 1s
(B) strings from the alphabet {0,1} in which ones always appear in pairs
(C) strings from the alphabet {0,1} in which ones occur twice as frequently as zeros
(D) strings from the alphabet {0,1} in which there are an even number of 1s and an
odd number of zeroes.

Q71. Which of the following languages denoted by the regular expressions
R = 0*10*10*10*
(A) strings from the alphabet {0, 1} in which there are an odd number of 1s
(B) strings from the alphabet {0, 1} in which ones never appear together
(C) strings from the alphabet {0, 1} in which there are exactly three ones.
(D) strings from the alphabet {0, 1} in which there are exactly three ones or no ones
Q72. How many of the regular expression(s) which matches all strings of 0‟s and 1‟s that
do not contain the substring 011? ____________
(1) ((011)0*1*)* (2) (0*1)+0* + 1*0*
(3) (01|010|100|110)* (4) (0+1)*0*|1*0*

Q73. How many strings of length less than 4 contains the language described by the regular
expression (a + d)*b(a + bc)*?_______

Or
Solution:
(a+d)*b(a+bc)*
string of length 1 = b =1
String of length 2= ab , db, ba = 3
String of length 3= aab, adb, ddb, dab, baa,bbc, aba , dba = 8
So number of string = 1+3+8=12
Answer: 12

Q74. How many strings are there in the language defined by regular expression?
__________((∅*∩ a) ∪ (∅∪ b*)) ∩ ∅*
Answer: 1
Solution: ((∅*∩ a) ∪ (∅∪ b*)) ∩ ∅* = (∅ ∪ b*) ∩ 𝜆 = 𝜆. So, the cardinality = 1.
Q75. How many strings are there in the language defined by regular expression?____________
((∅*∪ b) ∩ (b*∪∅))
Answer: 2
Solution: ((∅*∪ b) ∩ (b*∪∅)) = {λ ∪ b} ∩ b* = {λ ∪ b}. So, the cardinality = 2.
Q76. How many strings of length less than 5 contains the language described by the regular
expression 0*1(0 + 1)* 01*? ______________

Answer: 16
Solution: All the strings of length less than 5 generated by given regular expression
are
{10, 010, 100, 110, 101, 0010, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101, 1110}.
So, the total number of required strings = 16.
Q77. Let L be the language generated by regular expression ((a + b)*b(a + ab)*). How many
strings of length less than four are there in L? ______
Answer: 11
Solution: Required number of strings of length less than four
= (21 − 1) + (22 − 1) + (23 − 1) = 1 + 3 + 7 = 11

Q78. What is the regular expression for the language generated by the following grammar? S
→Aab A→ Aab | B B→a
(A) aab(ba)* (B) aab(ab)*
(C) aa(ab)* (D) ab(ab)*
Solution:
S→Aab S→Aab S→Aab
S→Bab S→Aabab S→Aabab
S→aab --- S→Babab S→Aababab
(1) S→aabab S→Bababab
S→aabab---(2) S→aab(abab) ----(3)
So expression is: aab(ab)*
Answer: B
S →AabB, A→ b | bA | λ, B → aB | aa | λ
Which of the following regular expression is equivalent to the language generated by G?
(A) b*abaa* (B) a*abb*
(C) b*aba* (D) b+aba+

S →AB | aAb A→ b | baA | λ B → aB | abB | λ
Which of the following regular expression is equivalent to the language generated by G?
(A) (ba)*(b + λ)(a + b)*
(B) (ba)*(b + λ)(a + ab)*
(C) (ba)*(b + λ)(a + ab)* + a (b + ab)*b
(D) a((ba)*(b + λ))b + (ba)*(b + λ)(a + ab)*

Q81. Which of the following grammar generates the language generated by given regular
expression R = a(a+b)*a + b(a+b)*b
(A) S  aSa | bSb | aS | bS | λ
(B) S  aAa | bAb A  aA | bA | λ
(C) S  aAa | bAb A  aA | bA | aAa | bAb| λ
(D) Both b & c

Q82. Which of the following grammar generates the language generated by given regular
expression R = aaa+ + (ba+bb)*a
(A) S  aaX | Ya X  aX | λ YbaYbbY | λ
(B) S  aX | Ya X  aX | a YbaY | bbY | λ
(C) S  aaX | Ya X  aX | a YbaY | bbY | λ

Q83. Which of following Grammar generates the language L(a*a(a+ba)*)?
(A) S S1|S2, S1aA, AaA|, S2aS2|baS2 |
(B) S S1S2|S1, S1aA, AaA|, S2aS2|baS2|
(C) S S1S2|a, S1aA, AaA|a, S2aS2|baS2 |
(D) Both B and C
Answer: D
Solution:

Q84. Which of the following grammars is a right regular grammar with the same language
as the regular expression (a* b*)  (a*b*)?
(A) S → AB A → aA | ε B → bB | ε
(B) S → A | B A→ Aa | ε B → Bb | ε
(C) S → A | B A → aA | a B → Bb | a
(D) S → A | B A → aA | ε B → bB | a

Q85. Consider the following NFA
Which of the following string is not accepted by the following NFA?

(A) 00000000 (B) 01001
(C) 111110010 (D) None

Q86. Which of the following string is accepted by given NFA?
(A) aaabbbbbb (B) aababb

(C) abab (D) babaa
Answer: C
Solution:
(a) When we run given NFA for string „aaabbbbbb‟ then we will reach on q2, which is a
non-final state and there is no transition for „a‟ from q2. So, NFA will not accept this
string.
(b) When we run given NFA for string „aababb‟ then we will reach on q2, which is a
string.

(c) When we run given DFA for string „abab‟ then we will reach on q3, which is a
final state. So, DFA will accept this string.
(d) When we run given NFA for string „babaa‟ then we will reach on q2, which is a
string.
.
Q87. Consider the following DFA:
If the input is 011100101, which edge of the automaton is NOT traversed?

(A) CD (B) AC
(C) BC (D) BD
Answer: A
Solution:
If the input „011100101‟ is run on given DFA then following edge are traversed:
String 0 1 1 1 0 0 1 0 1
Edges AB BD DB BD DA AB BD DA AC
CD is not traversed and BC is not an edges of given automaton.
Q88. Consider the following DFA:
If string S is accepted by this DFA, which of the following strings cannot be a suffix of S?
(A)111 (B) 111001
(C) 11011 (D) 0010111
Answer: B
Solution:
(A) Yes; because 111 is a suffix of 0111 and it is accepted by given DFA
(B) No; because after two zeroes we need two 1.
(C) Yes; because 11011 is a suffix of 011011 and it is accepted by given DFA.
(D) Yes; because 0010111 is a suffix of 00010111and it is accepted by given DFA.

Q89. How many of the following strings are accepted by the NFA given below? ________
(i) 00 (ii) 01001 (iii) 10010

(iv) 000 (v) 0000
Q90. Which of the following strings is accepted by DFA given below?
(A) aabbbcca (B) aabbbcccca

(C) abbbcccc (D)bccccabc
Solution: It accept the string that end with c and if c is occurred than after that no other
alphabet occurred.
Answer: C

Q91. What is the complement of the language accepted by the following NFA? ( = {a})
(A) ∅ (B) {}

(C) a* (D) a+
Answer: B
Solution: The language accepted by NFA is {ak| k>0}. So, the complement of this
language is {}.
Data for next two questions: Consider the following DFA D:
Q92. Let the language accepted by G is L(D) then complement of L(D) is equivalent to
(A) 1+ (B) 1*
(C) 1* + 0* (D) 1(0+1)*

Q93. Let the language accepted by G is L(D) then reverse of L(D) is equivalent to
(A) 01*
(B) 1*0(0+1)*
(C) (0+1)*01*
(D) (0+1)* + 01*
Data for next twenty questions: Consider the following two DFA‟s D1 and D2:
It is given the language accepted by D1 and D2 are L (D1) and L (D2), respectively.
Q94. [MSQ]
If L (D) = L(D1) ∪ L(D2), then which of the following regular expression is/are
equivalent to L(D)?
(A) (0 + 1)* (B) (01 + 10)(0 + 1)*
(C) (0*1 + 1*0) (0 + 1)* (D) (0 + 1)+

Q95. If L(D) = L(D1) ∩ L(D2), then the regular expression for L(D) is equivalent to
(A) ∅ (B) (01 + 10)(0 + 1)*
(C) (00*1 + 11*0)(0 + 1)* (D) None of these

Q96. If L(D) = L(D1) − L(D2), then the regular expression for L(D) is equivalent to
(A) 1* (B) 1+
(C) 1(0 + 1)* (D) None of these
Answer: B
Solution: L(D) = L(D1) − L(D2) = 𝐿 𝐷1 ∩ 𝐿(𝐷2 ) = 0*1(0 + 1)* ∩ {1*} = 1+
Q97. If L(D) = L(D1).L(D2), then the regular expression for L(D) is equivalent to
(A) 0*11*0 (0 + 1)* (B) 0*1(0+1)*1*0(0+1)*
(C) (0 + 1)* (D) (0 + 1)+
Q98. If L(D) = L(D1)R.L(D2)R, then the regular expression for reverse of L(D) is
(A) (0 + 1)* (B) (0 + 1)*1*0(0 + 1)*10*
(C) 0*1(0 + 1)*1*0(0 + 1)* (D) (0 + 1)*01*(0 + 1)*10*

Q99. If L(D) = L(D1) ∪ L(D2), then the regular expression for complement of L(D) is
(A) λ (B) 0+ + 1+
(C) 0* + 1* (D) 0*1*

Q100. If L(D) = L(D1) ∩ L(D2), then the regular expression for complement of L(D) is
(A) λ (B) 0+ + 1+
(C) 0* + 1* (D) (0+1 + 1+0)(0+1)*
Answer: C
Solution: The product automaton for D1 and D2 is shown below:
Now, the DFA for its complement is
The regular expression for complement of L(D) is 0* + 1*. So, correct answer is C.
Q101. [MSQ]
If L(D) = L(D1)*∪ L(D2)*, then which of the following regular expression is/are
equivalent to L(D)?
(A) (01 + 10)*
(B) (0 + 1) *
(C) 0*1*(0+1)*
(D) none of these

Q102. Minimum how many states are required to construct the DFA for L(D1) ∪ L(D2)? ____

Q103. Minimum how many states are required to construct the DFA for L(D1) ∩ L(D2)? ____
Answer: 4
Solution: The product automaton for D1 and D2 is shown below:
So, required number of states is 4.
Q104. Minimum how many states are required to construct the DFA for 𝐿(𝐷1) ∩ 𝐿(𝐷2)? ____

Q105. Minimum how many states are required to construct the DFA for 𝐿(𝐷1) ∪ 𝐿(𝐷2)? ____
Q106. Minimum how many states are required to construct the DFA for 𝐿(𝐷1). 𝐿(𝐷2)? ____

Q107. Minimum how many states are required to construct the DFA for L(D1) . L(D2)? ____
Answer: 3
Solution:

Q108. [MSQ]
Which of the following Grammars accept the language L(D1) ∪ L(D2)?
(A) S  0S | 1S | 0 | 1
(B) S  0A | 1B, A  0A | λ, B  1B | λ
(C) S  0S1 | 1S0 | 0S | 1S | 0 | 1
Q109. [MSQ]
Which of the following Grammars accept the language L(D1) ∩ L(D2)?
(A) S  0X1A | 1Y0A, X  0X | λ, Y  1Y | λ, A  0A | 1A | λ
(B) S  XY, X  0A1 | 1B0, A  0A | λ, B 1B | λ, Y  0Y | 1Y | λ
(C) S  0S | 1S | 0 | 1

Q110. [MSQ]
Which of the following Grammars accept the language L(D1)R∪ L(D2)R?
(A) S  0S | 1S | 0 | 1
(B) S  0A | 1B, A  0A | λ, B  1B | λ
(C) S  0S1 | 1S0 | 0S | 1S | 0 | 1

Q111. [MSQ]
Which of the following Grammars accept the language L(D1) . L(D2)?
(A) S  AB,AX1Z, X 0X | λ, BY0Z, Y 1Y | λ, Z  0Z | 1Z | λ
(B) S  0S | 1S | 0 | 1
(C) S  0S1 | 1S0 | 0S | 1S | 0 | 1

Q112. [MSQ]
Which of the following Grammar(s) accept the language 𝐿(𝐷1). 𝐿(𝐷2)?
(A) S  0S | 1S
(B) S  λ
(C) S  0S | 1S | 0 | 1
(D) S  XY X  0X | λ Y  1S | λ

Q113. Which of the following Grammar accepts the language 𝐿(𝐷1) ∩ 𝐿(𝐷2)?
(A) S  0S | 1S (B) S  λ
(C) S  1S | 0S | 0 | 1 (D) None of the above

Q114. Consider the following NFA M: :
If the language accepted by M is L(M) then the regular expression for reverse of L(M)
is
(A) (a + b)*{λ + a + aa + aab + aaba + aabbab}
(B) (aabab)(a + b)*
(C) babaa (a + b)*

Q115. [MSQ]
Consider the following NFA with  (epsilon): :
Which of the following statement is/are true?

(A) ∈ −closure {q0 } = 𝑞0 , 𝑞1 , 𝑞2
(B) ∈ −closure {q1 } = 𝑞1 , 𝑞2
(C) ∈ −closure {q2 } = 𝑞0 , 𝑞2
(D) ∈ −closure {q3 } = 𝑞3

Q116. [MSQ]
Consider the following NFA with  (epsilon):
Which of the following statement is/are true?

(A) ∈ −closure {A} = 𝐴, 𝐵, 𝐶
(B) ∈ −closure {B} = 𝐵, 𝐶
(C) ∈ −closure {C} = 𝐶
(D) ∈ −closure {A} = 𝐴, 𝐵

Q117. Consider the following NFA with  (epsilon): :
Which of the following option(s) is/are true about -closure of different states of
given NFA?

(A (D)
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑝 = 𝑝, 𝑞, 𝑟 ∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑝 = 𝑝, 𝑞, 𝑟
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑞 = 𝑝, 𝑞, 𝑟 ∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑞 = 𝑞, 𝑟
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑟 = 𝑝, 𝑞, 𝑟 ∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑟 = 𝑟
(C) (D)
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑝 = 𝑝, 𝑞, 𝑟 None of these
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑞 = 𝑞
∈ −𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑟 = 𝑟
Q118. Consider the following NFA with  (epsilon):

The regular expression of the following non-deterministic finite automaton is
(A)ac + b(ab)* (B) (ac + b)(aac + ab)*

(C)(aca +ba)(b + ac)* (D) Both b and c

Solution:
Option (A) is false.
because acab generate by automata.

But acab does not generate by option.(a).
(b) option B is correct.
(c ) option c is false because expression c generate aca, but NDFA doesnot generate
aca.
Answer: B
Q119. [MSQ]
Consider the following FSA: (Where state „3‟ is final state) :
Which of the following statements is/are true?

(A) The FSA accepts 011111101.
(B) The FSA accepts 11101000.
(C) The FSA rejects 0000.
(D) The FSA accepts all bit strings with an odd number of

Q120. What is the language accepted by the following DFA?
(A) 0*1*
(B) 1*0*
(C) (1+0)* 1*(0+1)*
(D) (1+0)1*0(0+1)*

Q121. The regular expression for following automata will be:
(A) (011)*10(00 +1)*

(B) 0*11*10(00 +1)*
(C) (0+11)*10(00)*1*
(D)(0+11)*10(00 +1)*
Answer: D
Solution:
Option a: False
Because our automata generate 000010, but our regular expression can‟t generate this.
so option (a) is false.
Now check for option (b)
Automata generate 10, but regular expression 0* 11*10(00+1)* does not generate 10.
Option c is also false.
011101100 string generate by automata, but regular expression
(0+11)*10(00)* 1* does not generate it.
So answer is D

Q122. What is the regular expression corresponding to the language accepted by the following
finite state automata?
(A) ((a + b)(a*(bb)*)*b(+a))*

(B) (a(a*(bb)*)*b+b(a*(bb)*)*a)
(C) (a+b)(a*(bb)*)*a
(D)None
Answer: D
Solution:
Option(a) is false:
(( a+b)(a*(bb)*)*(+a))*
((a+b)(a*(bb)*) b(+a))2
(ab)2= abab
so it generate abab.
but abab does not generate by automata.
So option( a) is false.
(b) option (b) is also false.
because option (b) does not generate , but our automata generate .
so option (b) is false.
(c) is also false, because expression (c) does not generate , but our automata

generate .
Answer: D
Q123. How many of the following regular expressions that denotes a subset of the language
recognized by the given DFA? ___________
(1) 0*(11)*0*
(2) 0*1(10*1)*1
(3) 0*1(10*1)*10∗
(4) 0*1(10*1)0(100)*
(5) (0*1(10*1)*10* + 0*)*

Q124. What is the language accepted by the following finite state automata?
(i) a(bb + bba)*ba

(ii) ab(bb + bab)*a
(iii) ab(b+ba)*a
(A) i only (B)ii and iii only
(C)All of these (D)i and iii only
Answer: i & ii Only
Solution:
Similarly, There is another path to reach final states. First we move from q1 to q2 then
q2 to q4. After that, we have two loop (q4q2, q2q4)* and (q4q3, q3q2, q2q4)* then we
will traverse q4q5 edge to reach final state q5.
So, its regular expression will be a(bb + bab)*a. So, i & ii are correct.

Q125. [MSQ]
What will be the regular expression for following automata?
(A) a*(a+b)b
(B) a*(a+b)ba*
(C) a*{((a+b)b)*a* + λ}
(D) (a +(a+b)b)*
Q126. What is the language accepted by following automata?
(A) Any string starts or ends with b

(B) The strings with an even number of characters
(C) The strings with an even number of characters and length of at least 2
(D) The strings with an even number of a‟s or b‟s and length of at least 2
Solution:
Option(a) is false.

Any string start or end with b is false
because automata also generate string that start with a and end with a.
(b)option(B) is partially true, but not defined accurate language.
(c)true string with an even number of characters and length of at least 2.
(d) false abbb(this string generate by automata)
but this string contain neither even number of a or b.
Answer is C
Q127. The language accepted by the following DFA is:
(A) All strings of the form 0+w, where w contains an even number of ones.
(B) All strings of the form 000+w, where w contains an even number of ones.
(C) All strings of the form 00+w, where w contains an odd number of ones.
(D) All strings of the form 00+w, where w contains an even number of ones.
Solution:
Option (a):
All string of the form 0w, where w contain an even number of one‟s is false because
string contain at least two zero‟s.
Option (b) is false. all string contain at least 3a‟s this also false, because automata
generate string at least two zero‟s and even number of ones .
So option d is correct.
Answer: D

(A) L= {w| w has number of „a‟ divisible of 4 and number of „b‟ divisible of 3}
(B) L= {w| w has exactly two a‟s and at least two b‟s}
(C) L= {w | w has exactly two a‟s and number of b‟s divisible by 2}
(D) L= {w | w has at least two a‟s and number of b‟s divisible by 2}

(A)L= {w| w has an even number of a‟s and one or two b‟s}
(B)L= {w| w has an even number of a‟s and at least two b‟s}
(C)L= {w| w has an at least two a‟s and one or two b‟s}
(D)L= {w| w has an at least two a‟s and one or two b‟s}

Q130. Consider the following DFA D:
If L(D) is language accepted by DFA D, then which of the following language is exactly
equivalent to L(D)?
(A) All the strings containing substring 100101
(B) All the strings start with 10 and end with 01
(C) All the strings start with 100 and end with 101
(D) All the strings of length greater than or equal to six.

Q131. The following DFA accepts
(A) All the strings that contains 101 as substring

(B) All the strings that ends with 101
(C) All the strings does not end with 0
(D) All the strings that ends with 01
(A) (00+11)+
(B) All the strings containing 00 and 11 as substring
(C) All the strings end with 00 or 11
(D) All the strings of length greater than or equal to two

(A) All the strings containing 111 as the substring.

(B) All the strings containing 111and 000 as the substring.
(C) All the strings start with 111 and ends with 000.
(D) All the strings containing 111 a substring and ends with 000.

Q134. Which of the following finite automata accepts different language than other three?

Answer: C
Solution: (a)
(b)
(c)
(d)

Option (c) generates different language.
Answer: C
Q135. Consider the following two DFAs
Let the language accepted by DFA1 is L1 and that of DFA2 is L2. Which of the following
is true?
(A) L1  L2
(B) L2  L1
(C) L1= L2
(D) L1 ≠ L2

Q136. Minimum number of states in a deterministic finite state automaton (FSA) that recognizes
all bit strings with a multiple of three 1's. (For example, the following strings are in the
language: 111, 111111, 1110, 0111, 10011, but not 1, 11, 1111, 0110. ______

Q137. Minimum number of states in a deterministic finite state automaton (FSA) that
recognizes all strings over a and b that has at least three a‟s and at least two b‟s i.e.
L = {w| w has at least three a‟s and at least two b‟s}__________
Q138. Consider the following language:L = {w ∈ {a, b}∗| every a‟s in w is followed immediately
by the string bb}. Minimum number of states in a deterministic finite state automaton for
L is __________

Q139. Minimum number of states in a DFA for the language L = {abnam | n>3, m>2 } is___

Q140. The minimum number of state in the DFA for the language
L = {w |(na(w)+ 2nb (w)) mod 3< 2} is ______
Q141. How many number of states are required to construct the minimized DFA for following
languages over {a, b}whose languages of accepted strings (exactly) are:
(i) {a, aa, aaa, aaaa}. ________
(ii) all strings not in {a, aa, aaa, aaaa}. ____________
(iii) all strings whose length is divisible by 2 or 3. ___________
(iv) all strings matching the regular expression (aa|b)*+(bb|a)*.____
(v) all strings not matching the regular expression (*)*_________

(iii)L= all strings whose length is divisible by 2 or 3 = L1 U L2 ;
Where L1 = {w |w ∈ 𝑎, 𝑏 ∗ and |w| mod 2 = 0 } and
L2 = {w |w ∈ 𝑎, 𝑏 ∗ and |w| mod 2 = 0 }
Apply minimization algorithm:

𝜋0 = 24, 25 , 13, 15, 23, 14
𝜋1 = 24, 25 , 13, 14 , {15, 23}
𝜋2 = 24}, {25 , 13}, {14 , {15}, {23}
𝜋3 = 24}, {25 , 13}, {14 , {15}, {23}
So, minimized DFA contains 6 states.
Q142. Consider the following DFA D over the alphabet  = {a, b, c}:
The number of state states in minimized DFA will be _______

Answer: 3
Solution:

Q143. Consider the following DFA over {a, b}
How many states does the minimized DFA have? _________

Answer: 2
Solution:

Q144. Consider the finite automaton MDL = ({S, S1, S2, S3, D1, D2}, {a, b, c} , S,{D1,D2},
where  is defined as follows:
(S, a)  S1 (S, b)S2 (S, c)  S3 (S1, a)  D1
(S1, b) S2 (S1, c)  S3 (S2, a)  S1 (S2, b)  D2
(S2, c)  S3 (S3, a)  S1 (S3, b)  S2 (S3, c)  D2
(D1, a) D1 (D1, b)  D1 (D1, c)  D1  (D2, a)  D2
(D2, b)  D2 (D2, c) D2
Minimum number of states in DFA of given MDL is___________
Answer: 5
Solution:

The number of states in the equivalent minimized DFA will be? ____________

The number of states in the equivalent minimized DFA will be? ___________
Answer: 3
Solution: We will apply minimization algorithm:
𝜋0 = 𝑞𝜆 , 𝑞0 , 𝑞1 , 𝑞00 , 𝑞01 , 𝑞10 , 𝑞11 .
𝜋1 = 𝑞𝜆 , 𝑞0 , 𝑞00 , 𝑞10 , {𝑞01 ,𝑞1 } 𝑞11 .
𝜋2 = 𝑞𝜆 , 𝑞0 , 𝑞00 , 𝑞10 , {𝑞01 ,𝑞1 } 𝑞11 .
𝜋3 = 𝑞𝜆 , 𝑞0 , 𝑞00 , 𝑞10 , {𝑞01 ,𝑞1 } 𝑞11 .
So, minimized DFA contains 3 states.

The number of states in the equivalent minimized DFA will be? _________

Q148. Consider the following DFA D over the alphabet ΣD = {a, b, c}:
The numbers of states in the equivalent minimized DFA is__________

Q149. Find out how many states exist when we draw minimized DFA for the regular language
given below L = {w x wr |w(a+b)+ and x(a+b)*} ?__________
Solution:
Given= L= {wxwr|w(a+b)+, x(a+b)* }
Draw its NFA.
Here we have consider w as a single alphabet, so every string that accepted by this
language will start and end with same symbol, and rest will be covered by x.
a b
𝑞0 𝑞1 𝑞2
𝑞2 𝑞2 𝑞2 𝑞3
𝑞1 𝑞1 𝑞3 𝑞1
Draw its corresponding DFA transition table.
Hence the minimized DFA has 5 states.

Answer: 5.
Q150. What is the minimum number of states of an equivalent DFA corresponding to

Following NFA? (Assume  = {a, b, c})

(A) 2 (B) 3 (C) 4 (D) 5
Solution:
NFA
a b c
→𝑞0 𝑞1- 𝑞2 -
𝑞- 1 - 𝑞1
𝑞- 2 - 𝑞2
Now convert it into DFA:
{𝑞0 ,𝑞𝑡 }{𝑞12 , 𝑞1 ,𝑞2 }

{𝑞0 }{𝑞𝑡 }{𝑞12 ,𝑞1 , 𝑞2 }
{𝑞0 }{𝑞𝑡 }{𝑞12 ,𝑞1 }{𝑞2 }
{𝑞0 }{𝑞𝑡 }{𝑞12 }{𝑞1 }{𝑞2 }

So number of state is 5
Answer: D
Q151. Minimum numbers of states required to construct the equivalent DFA of the following
NDFA? __________
Solution:
Now remove  closure

- Closure of 𝑞1
{𝑞1 ,𝑞𝐹 }, so now copy the all outgoing transaction of 𝑞𝐹 .
Now 𝑞1 also become final, because 𝑞𝐹 is final and definition said that if any state of 
closure contain final state that 𝑞1 is also become final.
NFA:

0 1
𝑞1 𝑞1 𝑞𝐹 𝑞𝐹
𝑞2 𝑞𝐹 𝑞2
𝑞𝐹 𝑞𝐹 𝑞𝐹
Now convert it into DFA.
{𝑞1 ,𝑞1𝐹 ,𝑞𝐹 }

So, only one state is in its minimized DFA.
Answer is 1
Q152. S Supposewe apply minimization to the following DFA over {a, b}:
Which of the following correctly describes the resulting DFA M?

(A) M has 3 states, 1 of which is accepting.
(B) M has 3 states, 2 of which area accepting.
(C) M has 2 states, 1 of which is accepting.
(D) M has 4 states, 2 of which are accepting
Solution:

Now perform minimization of this DFA.
{𝑞1 , 𝑞2 }{𝑞3 ,𝑞4 }
So M has 2 state, 1 of which accepting.
So answer is C
Q153. Suppose that there are two DFA's D1 and D2. DFA D1 has 7 states out of which 3
states are final states. DFA D2 has 6 states out of which 4 states are final states. In the
product DFA for the intersection of their languages, maximum how many final states
Will be there?
(A) 12 (B) 9
(C) 3 (D) 1
Solution: In product automata of two DFA.
Maximum number state is final = number of state final in Ist DFA* number of state final
in IInd DFA = 3*4 = 12 and maximum number of state occurred, when all state make pair
with each other.
Answer: A

Q154. Suppose that there are two DFA's D1 and D2. DFA D1 has 7 states out of which 3 states
are final states. DFA D2 has 6 states out of which 4 states are final, In the product DFA for
the union of their languages, how many final states will be there?
(a) 42 (b) 34
(c) 2. (d) 18
Solution:
In case of union in product automata if one of the state is final than resulting state is
final. So, total number of final states = 3*6 + 4*7 – 3*4 = 18 + 28 – 12 = 46 – 12 = 34.
Answer: B
Q155. Suppose we have a DFA D = (Q, Σ, δ, q0, F) and know that D accepts every string.
What can we infer about D?
(A) Every state in D is a final state.
(B) There is at least 1 state in D that is not final.
(C) Every reachable state from q0 in D is a final state.
(D) There is only 1 character in the alphabet.

Let A = {0n1m | n<=m} and B = {0n1m | m<=n} then which options are incorrect?
Q156.
(i) A U B is regular.
(ii) A intersection B is regular.
(iii) Both A and B are regular.
(A) ii & iii only (B) i & ii only
(C) i & iii only (D) All
Solution:
(i) A = {0n1m | n<=m} and B = {0n1m | m<=n }

Union of this either n<m or m<n or m=n
So it generate 0*1*
So it is regular of option (i) is true.
(ii) is false.
A∩B = {0n1m |m=n}
So it is not possible to write a regular expression, and design a NFA/DFA for it because
FA is memory less device.
(iii) A and B is not regular because by NFA/DFA, we can‟t ensure that number of 1 is
more than 0 and number of 0 is more than.
So option (A) is true.
Q157. Which of the following languages is/are regular?
(A) L1 = {wz: |w| = |z|, w  (a + b)* and z  (b + c)*}.
(B) L2 = {w: every a in w is followed by at least one b and at least one c}.
(C) L3 = {w: w does not have the same number of a‟s, b‟s, and c‟s}.
(D) L4 = {w: w contains the same number of patterns ac and abc}.
Answer: B
Solution:
(A) It is non-regular because w and z both have different set of alphabets.
(B) Regular expressions for L2 = b*c*(ab+c+)*b*c*.
(C) FA can‟t remember. So, it is non-regular.
(D) We cannot write regular expressions for L4. So, it is non-regular.
Q158. Which of the following is/are regular?

(i)L1 = {akbmcn | (k = m or m = n) and k + m + n  2}
(ii) L2 = {akbmcn | (k = m or m = n) and k + m + n ≤ 2}
(iii) L3 = {akbmcn | k + m + n  2}
(A) i, ii, iii only (B) ii, iii only
(C) ii only (D) iii only
Solution:
(i) Regular expression I is not regular because we cannot ensure k=m or m=n by FA.
Because finite automata cannot remember.
(ii) Regular expression II is regular, because it is finite.

(iii) It is also regular.
Answer is B
Q159. Which of the following languages over Σ = {a, b} is/are not regular?
(i) {ambn|m, n  N};
(ii) {ambn |m  n};
(iii) { ambn| m + n  4};
(iv) {w*|wL}; where L is some given language which is regular.
(v) {w*|wL}; where L is some given language which is not regular.
(A) i and iii only (B) i, iii and iv only
(C) ii and v only (D) ii, iv and v only
Solution: (i) is regular { ambn |m,n N}
a*b* (Regular expression for it)
ii. { ambn |mn}
for this we can‟t design DFA ,NFA for it .
So it is not regular.
iii. { ambn |m+n4}

It is regular
v. It is not regular.
So answer is C
Q160. For which of the following languages over the alphabet {a, b} is /are not regular?
(i) L1 = {w | w is not a palindrome}
(ii) L2 = {ak | k is multiple of 4}
(iii) L3 = {ak | k mod 6 = 1 or 5}
(iv) L4 = {wxw | „x‟ can be any non-empty string and |w|<=3}
(A) i and iv only (B) ii and iii only
(C) iii and iv only (D) i only
Solution:
(i) Is not regular.
Palindrome said that if we read string from either MSB or LSB , than string should be
same.ex: {aba, abba}. So for this we can‟t design NFA/DFA.
(ii) & (iii) are regular because L2 = (aaaa)* and we can design DFA for L3.
(iv)L4 is also regular because w is finite.
Answer is D
Q161. For which of the following languages over the alphabet {a, b} is/are regular?
(i) L1 = { ww | w∈ 𝑎 ∗ }
(ii) L2 = { ww | w∈ 𝑎, 𝑏 ∗ }
(iii) L3 = { w1w2 | w1∈ 𝑎 ∗ 𝑎𝑛𝑑w2∈ 𝑏 ∗ }
(iv) L4 = {w | w∈ 𝑎, 𝑏 ∗ and w contains the same number of a's and b's}
(v) L5 = {w | w∈ 𝑎, 𝑏 ∗ and w contains the same number of a's and b's and that number
is no more than 128}
(A) i, iii and v only (B) iii and v only
(C) ii and iv only (D) i, ii and iii only

Solution:
(i) L1 = {ww| w{a}*}
It is tell that first w than again w, so it will generate even number of a‟s string aa, aa,
aaaa, aaaaaa.
So (i) is regular
(iii) also regular.
L3= { w1w2 |w1{a}* and w2 {b}* }
It is regular , it said that
(v) It is regular number of a‟s = number of b‟s , and that is no more than 128 . so it is
finite.
Answer is A

(A) L1 = {wz: |w| = |z|, w  (a + b)* and z  (b + c)*}.
(B) L2 = {w: every a in w is followed by at least one b and at least one c}.
(C) L3 = {w: w does not have the same number of a‟s, b‟s, and c‟s}.
(D) L4 = {w: w contains the same number of patterns ac and abc}.
Answer: B
Solution:
(A) It is non-regular because w and z both have different set of alphabets.
(B) Regular expressions for L2 = b*c*(ab+c+)*b*c*.
(C) FA can‟t remember. So, it is non-regular.
(D) We cannot write regular expressions for L4. So, it is non-regular.

Q163. Which of the following language is/ are not regular?
(i) L1 = {ak!: k≥1}
(ii) L2= (ak : k is perfect square}
(iii) L3 ={wϵ{a, b}*: |w| = 4 *na(w)}
(A) L1 and L2 only (B) L2 and L3 only
(C) L1 and L3only (D) All the above
Solution:
(i) L1= { ak!: k 1}

factorial k if k =1 a1
k=2 a2
k= 3 a6
k=4 a24
Here there is no relation in a, 1,2, 6,24,120 …….
so it is not regular because there is no pattern in accepting string of a).
(ii) L2 = {ak: k is perfect square { a2 , a4, a9,a25…..here also there is no pattern are catch . In
accepting a, so we can‟t make NDFA /DFA for it , so it is also not regular.
(iii) |w|> 4*na(w)).
Here length of w is greater than number of a, because we can not memorized that how
many a is accepted.
Answer: D
Q164. Which of the following language is/ are regular?

i) L1 = {w{0, 1}* | (n0(w) − n1(w)) mod 3) = 0 }.
ii) L2 = {w {0, 1}*| (|n0(w) − n1(w)| mod 3) = 1 }.
(A) I only (B) ii only
(C) Both L1 and L2 (D) Neither L1 nor L2
Answer: C
Solution: i & ii are regular. We can make DFA for Both.
i) L1 = { anbl : n ≥ 100, l ≤ 100 }.
ii) L2 = {uwwRv : u, v, w ∈ {a, b}+}
iii) L3 = {uuRv : u, v ∈ {a, b}+ }
(A) i and ii only (B)i and iii only
(C)i, ii &iii (D)None of three

L1 = {uwwRv: u, v, w ϵ{a,b}+}
L2 = {uwwRv: u,v, wϵ{a,b}+,|u|≥|v|}
L3 = {wwRv: v,wϵ{a,b}+}
(A) L1 only (B) L2 and L3 only
(C) L1 and L2only (D) L1 and L3 only
Solution:
Regular expression for it
(0+1)+00(0+1)+
(0+1)+11(0+1)+
so this language is regular.
So L1 is regular language.
L2: is non- regular.
because by NDFA/DFA, we can not ensure that |u||v|.
So L2 is not regular.
L3:- It is not regular.
wwR v {Here we can not ensure that first w, than reverse of w, than other string .
Answer: A

Q167. Which of the following language are not regular?
L1 = {anblak: k≥n+l}
L2 = {anbl: n+l≥0}
L3 = {anbk: n≥100 and k≤100}
(A) L1 only (B) L2 and L3 only
(C) L1 and L2 only (D) L1 and L3 only
Solution:
L2= {anb1! n+10}
So this is FA for language L2.
L3:- = {anbk:n100 and k 100}

In FA after accepting 100 a, make loop on state , and k can be 0 to 100.
so for a we can make DFA , and b is finite so this is regular langue.

So L1 is not regular
Answer: A

L1={akbk: k≥1}{akbl: k≥1, l≥1}
L2 = {ak+1bk+1: k≥0} (ak+1bk+3:k≥ 0}
L3 = {ww: wϵ {a}+}
(a) (A) All the above (B) L2 and L3 only
(C) L1 and L2 only (D) L1 and L3 only
Solution:
L1 = {akbk, k 1} {akb1: k1, 11}
L1 = {an bn | n1} a+ b+ = a+b+
So, L1 is regular.
L3 is also regular.

So it is also regular.
Answer: D
Q169. Which of the following language is/ are regular?

1. L = {anbman : m, n  0}
2. L = {anananbmbmbm : m, n  0}
3. L = {anbm : mn and m≤10, n  0}
(A) 2 only (B) 2 & 3 only
(C) 1 only (D) none of these

Q170. Which of the following language is/ are not regular?
1. L = {xy : x L1 and yL1; where L1 is regular}
2. L = {w1w2 :w1, w2  L2; where L2 is regular}
3
3. L = {𝑎𝑖 : 𝑖 ≥ 0 𝑎𝑛𝑑 𝛴 = {𝑎}}
(A)1& 3 only (B) 2 only
(C) 3 only (D)All

Q171. [MSQ]
Which of the following languages is/are regular?
(A) L1 : { wxwR |w, x ∈ {a, b}*} , wR is the reverse of string w

(B) L2 : { an b2m | m≤1000 or n1000 }
(C) L3 : { ap bq cr |p<10 and q>100 and r ≥ 0 }
(D) L4 : {anbnw | n >= 0 and w ∈ {a, b}*}

Q172. [MSQ]
Which of the following languages is/are not regular?
(A) L1 = {wRxw : w, x Σ*}
(B) L2 = {wwRx : w, x Σ+}
(C) L3 = {wxwR : w, x Σ+}
(D) L4 = {wxw : w, x Σ+}

Q173. [MSQ]
Which of the following languages is/are not regular?
(A) L = {w :na(w)nb(w)}
(B) L = {aibjck : i j+k}
(C) L = {aibjck : j  2i+k}
(D) L ={aibjck : i = j or j  k}

Q174. 𝑖
If L1 = {1P : P is a prime number} and L2 = {12 ∶ 𝑖 ≥ 0} then which of the following
statement is/ are true?
I. {(L1)+ U *} is regular.
II. (L2)*is also regular.
III. (L1.(L2  λ))* is also regular.
(A)I & II only
(B)II& III only
(C)I & III only
(D) All the above

Q175. [MSQ]
Let L1 and L2 are two regular languages over  then which of the following is/are
regular?
(A) L = {xΣ* | either xL1 or xL2}
(B) L = {xΣ* | xL1 but xL2}
(C) L = {xΣ* |xyL1 or xyL2; where yΣ*}
(D) L = {xΣ* | xyL1 and |x| = |y|}

Q176. Which of the following language is regular?
(A) L = {ak : k is not perfect square}
(B) L = {ak : k is perfect cube}
(C) L = {ak : k is either prime or product of two or more prime numbers}
(D) L = {ak : k = 2i for some i  0}

Q177. [MSQ]
Which of the following language/s is/are not regular?
(A) L = {aibjck: i+j+k>4}
(B) L = {aibjck: i<10, j>5 and k >i}
(C) L= {aibj: i+2j is a prime number}
(D) L = {aibj : |i – j| = 3}

Q178. [MSQ]
Which of the following language/s is are regular?
(A) L = {aibj : i =j or i<j or i>j}
(B) L = {anbn : n1}U {anbm : n, m 1}
(C) L = {w1w2: w1 = w2 and w1, w2 Σ*}{anbn : n1}
(D) L = {an: n = k3 for some k0}

Q179. Which of the following is/are true?
(A) Union of two non-regular languages is always non-regular.
(B) Union of a regular language with a disjoint non-regular language is always non-
regular.
(C) L ((ab*ba*) ∩ (ba*ab*)) = {ε}.
(D) L = {1n : n ≤ 1000 and n is prime}. A DFA accepting L may have less than 900 states.

Q180. Which of the following languages are not regular?
1. L = {wwwwR : w{a, b}*}
2. L = {w{a, b}*| w = wR}
3. L = { w{a, b}*| w has more a‟s than b‟s} 4. L = {a2nb4nan}
(A)1 & 2 only (B) 2, 3 & 4 only
(C)1, 3& 4 only (D)All the above

Q181. Given that L is regular and
L1 = {wx: wΣ* and xL},
L2 = {w: wxL and |w| = |x|}, and
L3 = {w: wxL1, for some xL2}
Which of the above language is/are regular?
(A) L1, L2 only (B) L2, L3 only
(C) L1, L3 only (D) All are regular

Q182. Which of the following statement/s is are true?
I. If A is a non-regular language and B is a language such that B ⊆ A, then B must be
Non-regular.
II. If (L1.L2 U L3) is regular, L3 is regular and complement of L2 is regular then L1
must be regular.
(A) I only (B)II only
(C)Both (D)Neither I nor II
Solution: I. A = {anbn: n>=0} and B = {λ}
III. L1 = {anbn: n>=0}, L2 = , and L3 = a*

Q183. Select the correct statement
1. A DFA with n states must accept at least one string of length greater than n.
2. A DFA with n states that accepts an infinite language must accept at least one string x
such that 2n < |x| ≤ 3n.
3. If R is a regular language and L is some language, and L ∪ R is a regular language,
then L must be a regular language.
4. If F is a finite language and L is some language, and L − F is a regular language, then L
must be a regular language.
(A) 2 only (B) 1 and 3 only
(C) 2 and 4 only (D) None

Q184. Which of following is/are correct?
S1: Let r1 and r2 be two regular expressions. Then L ((r1 + r2)*) = L ((r1*r2*)*).
S2: Let L4 = L1 · L2 · L3. If L1 and L2 are regular and L3 is not regular, it is possible
that L4 is regular.
(A) Only S1 (B) Only S2
(C) Both S1&S2 (D)either S1 nor S2

Q185. Which of following is/are correct?
S1: L1 ⊆ L ⊆ L2 where L1 and L2 are regular, then L must be regular.
S2: {w = xyzy | x, y, z ∈ {0, 1}+} is regular.
(C) Both S1&S2 (D )either S1 nor S2

Q186. Which of following statement is/are correct?
S1: (∅* · ∅)* · ∅* = ∅
S2: {xyxR | x, y ∈ {a, b}+} is regular.
(C) Both S1&S2 (D)either S1 nor S2

Q187. Which of following statement is/are correct?
S1: If L1.L2 is regular then at least one of them (L1 or L2) is regular.
S2: If L1.L2 is non-regular then at least one of them (L1 or L2) is non-regular.
(C)Both S1&S2 (D)None of them

Q188. Select the correct statement:
(A) If L1 is regular and L2 L1, then L2 is regular as well.
(B) If L1 is regular and L2 is not regular, then L1 U L2 is not regular.
(C) If L1 is regular and L1 U L2 is not regular, then L2 is not regular.
(D) If L1 is regular and L2 is not regular, then L1 L2 is not regular.

Q189. Select the correct statements
(1) L1 = L2 if and only if L1* = L2*
(2) For any languages L1, L2 and L3, L1 (L2  L3)  (L1L2)  (L1L3)
(3) For any languages L1, L2 and L3, (L1L2)  (L1L3)  L1 (L2  L3).
(A) 1 and 3
(B) 2 and 3
(C) 2 only
(D) None.

Q190. Consider the following statements:
1. An infinite language can have an infinite complement.
2. All infinite languages have infinite complements.
3. The union of infinitely many regular languages is always regular.
Which of the above statements is/are true?
(C) 1 and 3 only (D) 2 and 3 only

Q191. Consider the following statements
1. If L is regular then so is {xx : x L}.
2. If L is regular then so is {xy : x, y L}.
𝑝
3. Let A = {12 : p is prime}. Then A* is regular.
Which of the above statements is true?
(C) 1 and 3 only (D) 2 and 3 only

Q192. Select correct statements:
S1: If L1 and L2 are non-regular languages then L1  L2 is also non-regular.
S2: IfL1 is non-regular language and L2 is regular language then L1.L2 may be
regular language.
S3: If L1L2 and L2 are regular then L1 may not be regular.
(A) S1 and S2 only (B) S2 and S3 only
(C) S1 and S3 only (D) All the above.
Answer :- (B) S2 and S3 only
Solution:
If L1 is non-regular language L1= {ambn, mn}
If L2 is non-regular language L2 = { ambn ,nm}
L1+L2 = (L1L2) = am bn m n + ambn ,nm
=a*b* (Which is regular)
So statement S1 is false.
S2:- Now check for statement 2.
L1= NR(non-regular) L2= Regular.
L1= anbn
L2=
anbn . ={Where () , is regular}
So statement S2 is true.
S3 : - L1L2 = Regular
L2= Regular a*b*
L1= Non-regular (anbn)
anbn+a*b* = a*b* (Regular)

So L1 is not regular here.
So statement is also true.
Answer: B
Q193. Select correct statements:

S1: For every regular language L, every subset of L is regular as well.
S2: Every non-regular language is infinite.
S3: The intersection of any two non-regular languages is non-regular.
S4: If each of the languages L1, L2 . . . is regular, then ∞
𝑖=1 𝐿𝑖 is regular as well.
(A) S1 and S2 only (B) S2 and S3
(C) S3 and S4 (D) S2 and S4
Answer :- None
Solution:
S1: Statement S1 is false, because not every subset of L is regular.
For example: Let L1 = a*b* (L is regular)
One of the subset of L = {anbn| n>=0}i.e. {anbn| n>=0}a*b* but anbn is not regular.
So statement S1 is false.
S2:- Every non- regular language is infinite.
Because every finite language is regular.
So statement S2 is true.
S3: It is False.
L1 = {anbn | n1}
L2 = {bnan | n1}
L1  L2 = {which is regular language}
So, S3 is false.
S4 is false, because regular language is not closed under infinite union.
Answer: None
Q194. Let L1 and L2 are two languages over  and it is given that L1.L2 is non-regular
languages. Then which of the following statement is not always true?
(A) 𝐿1 is not regular.
(B) L1 ∪ 𝐿1 is regular.
(C) L1, L2 ⊆ Σ*
(D) L1∪L2 contain infinitely many strings.
Answer: - (A)𝐿1 is not regular.
Solution:
(a) It is not always true.
L1.L2 =non-regular
(a*b*).{anbn| n>=0}= Non regular
a∗ b ∗ = Regular (its complement is regular).
So, option (a) is not always true.
(b) L1L1 is always regular.
If L1= anbn then L1L1 = anbnan b n = (a+b)*
So, it is always regular.
(c) It is true ; because every language is subset of *.
(d)If L1L2 contain infinite string is always true. Because L1.L2 = non-regular so at least
one language is infinite.
Answer: A
Q195. Let L= 01* + 10*. Which of the following is regular expression of LR (reverse of L)?
(A)0*1 + 1*0 (B) 1*0 + 01*
(C) 1*0 + 0*1 (D) (10)* + (01)*
Answer: - (C) 1*0 + 0*1
Solution:
L= 01* + 10*
LR = 1*0+0*1 = 0*1 + 1*0
Answer: C
Q196. The set of non-regular languages is closed under which of the following operations?
(A) Complement (B) Union
(C) Intersection (D) Concatenation
Answer: - (A) Complement
Solution:
(a) Non- regular language is closed under complement, because complement of non-
regular is always non-regular.
(b) {ambn | m  n}  {ambn |n  m} = a*b*
So, union of two non-regular languages may be regular. Sometimes it may not be
regular.

(c) {am bn | m>n}  {anbn | n>=0}is  which is regular, so intersection of two non-
regular may or may not regular.
(d) Non regular language is not closed under concatenation. For example: Let L 1is non-
regular language then L1  {λ} and 𝐿1  {λ} are also non-regular language. But its
concatenation is(L1  {λ}).(𝐿1  {λ}) = *; which is regular language.
Answer: A
Q197. Let L1 = {anbncm | n, m>=0} and L2 = {anbmcm | n, m>=0} then what is𝐿1𝐿2 ?
(A) L1U 𝐿2 (B)* - {anbncn | n>=0}
(C) {anbncn | n>=0} (D) a*b*c*
Answer: - none
Solution:
L1 = {anbncm|n, m>=0 } = {abc, aabbc….}and L2= {anbmcm|n, m>=0 {abc, abbcc}
𝐿1𝐿2 =L1L2= {𝑎𝑛 𝑏𝑚 𝑐 𝑘 | 𝑛, 𝑚, 𝑘 ≥ 0 ; 𝑤ℎ𝑒𝑟𝑒 𝑛 = 𝑚 𝑜𝑟 𝑚 = 𝑘}

Answer: none
Q198. The right quotient of a language L1 with respect to L2 is defined as L1/L2 = {x: yL2,
xyL1} Let L1 = L(a*ba+) and L2 = {aba*} then what will be the L1/L2?
(A)a* (B)a+
(C)a*b (D)a+b

Q199. Which of the following strings is NOT in the Kleene closure of the language
{abb, ba, bba}?
( (A) abbbabbaabb (B) abbbba
(C)abbbbababb (D) abbbabbababbaba

Answer :- (C)
Solution:
Option (a) Language L={abb,ba,bba}
L0+L1+L2+……..+Ln {Kleen closure}
L1= {abb, ba, bba}L1.L1=L2
L3= {abb}.{ba}.{bba}
L3.L= L4 = {abb}.{ba}.{bba}.{abb}
So (a) is in kleene closure of L.
Now check for option (b).
L1.L1= {abb}.{bba} = abbbba.
So it also in kleene closure of the language.
Now same way to check option (c)
C is not in kleen closure of L.
Answer: C
Q200. Let L1 = {a, ab, c, d, λ}, L2 = {d} and L3 = L1.L2. Which string is not in L3?
(A) a (B)abd
(C) cd (D) d
Q201. If L = {001, 1101, 101} then the prefix of L is

(A) {𝜆, 0, 00, 001, 1, 11, 110, 1101, 1, 10, 101}
(B) {𝜆, 0, 00, 001, 1, 11, 110, 1101, 10, 101}
(C) {λ, 1, 01, 001, 101, 1101}
Answer :- (B)
Answer: B
Solution: If L = {001, 1101, 101} then
prefix (001) = {λ, 0, 00, 001}, prefix (1101) = {λ, 1, 11, 110, 1101},
prefix (101) = {λ, 1, 10, 101}.

Then the prefix of L = prefix (001)  prefix (1101)  prefix (101)
= {λ, 0, 00, 001, 1, 11, 110, 1101, 10, 101}.
Q202. If L = {001, 1101, 101} then the suffix of L is
(A) {𝜆, 0, 00, 001, 1, 11, 110, 1101, 1, 10, 101}
(B) {λ, 1, 01, 001, 101, 1101, 10, 110}
(C) {λ, 1, 01, 001, 101, 1101}
Answer :- (C)
Answer: C
Solution: If L = {001, 1101, 101} then
suffix (001) = {λ, 1, 01, 001}, suffix (1101) = {λ, 1, 01, 101, 1101},
suffix (101) = {λ, 1, 01, 101}.
Then the prefix of L = prefix (001)  prefix (1101)  prefix (101) = {λ, 1, 01, 001, 101,
1101}.
Q203. Consider the following NFA:
Which of the following grammar generates the language accepted by NFA given above?
(A) S →1S/0A, A→1A/0B/0C, B→0C, C→1B/0C
(B) S →1S/0A, A→1A/0B, B→0C/, C→1B/0C
(C) S →1S/0A, A→1A/0B/0C, B→0C/, C→1B/0C/
(D) S →1S/0A, A→1A/0B/0C, B→0C/, C→1B/0C

Which Regular grammar corresponds to the following NFA?

(A) S  bA | aS, A aB | , BbA
(B) S  bA | aS, A bB | , BbA
(C)S  Ba, A  aB | , B  bA
(D)None

Q205. Consider the following NFA.
Which of the following is a left linear grammar for the language accepted by M?
(A) S 1S0|
(B) S 10S|
(C) S 1A|, A0S
(D)S A0| , AS1

Q206. How many of the following statement(s) is/are true? ________
(i)The language generated by the grammar G = ({S}, {a}, S, {S → Saaa | aS | a }) is not
regular.
(ii) The language generated by the grammar G = ({S}, {a}, S, {S → aSSa | aS | a }) is
regular.
(iii) The language generated by the grammar
G = ({S}, {a}, S, {S → bSb | aSa | a | b })is regular.
(iv) The language generated by the grammar G = ({S}, {a}, S, {S → bSa | λ | a }) is not
regular.

Q207. Consider a generated grammar G with production
S abA
AbaB
BaA | bb
How many states are required to construct minimized DFA for language accepted by
G?
(A) 2
(B) 3
(C) 4
(D) more than 4

Data for next two question: Consider a language L = {anbm : n2, m3}
Q208. Which of the following grammar is left-linear grammar for given L?
(A) SS1S2, S1aaA, AaA|λ, S2bbbB, BbB|λ
(B) SS1bbb, S1S1b | A, AaaB, BaB|λ
(C) SaaA, AaA|B, BbbbC, CbC|λ
(D) none of these
Answer:D

But option B is not left-linear grammar.

Q209. Which of the following grammar is right-linear grammar for given L?
(A) SS1S2, S1aaA, AaA|λ, S2bbbB, BbB|λ
(B) SS1bbb, S1S1b | A, AaaB, BaB|λ
(C) SaaA, AaA|B, BbbbC, CbC|λ
(D) None of these
Answer :-C

Q210. Consider following grammar G
SaA|bB|λ,
AbC|aS,
BaC|Bs
CaB|bA
Which of the following language is generated by G?
(A) L = {w :na(w) + nb(w) is even}
(B) L = {w : |na(w) - nb(w)| is even}
(C) L = {w :na(w) and nb(w) are both even}
(D) L = {w :na(w) and nb(w) are both odd}

Q211. Consider following grammar G
S aA|bB
A abA | λ
B ccB | λ
Which of the following regular expression is for language generated by G?
(A)a(ab)*b(cc)*
(B) a(ab)+b(cc)+
(C) a(ab)*+b(cc)*
(D) a(ab)++b(cc)+

Q212. The language generated by the grammar with productions where  = {a, b} is?
S → AaAaAaA,
A → aA|bA|.
(A) All the strings over * with at least three a's.
(B) All the strings over * with at most three a's
(C) All the strings over * with at least three a's or three b's

(D) None of these

S → XY
X → aX | bX | a
Y→Ya|Yb|b
The regular expression for the language generated by G is
(A) (a + b)+
(B) (a + b)*ab(a + b)*
(C) (a + b)+ab(a+ b)+
(D) (a + b)+ (a + b)+

For the next two questions: Let Σ1 ={0, 1, 2} and Σ2 = {a, b, c, d}and define h(0) = aab, h(1)=aabc, h(2)
= cccd.
Q214. Then holomorphic image of L = {010, 102, 1011, 0100} is
(A) h(L) = {aabaabcaab, aabcaabccccd, aabcaabaabaab, aabaabcaabaab}
(B) h(L) = {aabaabcaab, aabcaabcccd, aabcaabaabaabc, aabaabcaabaab}
(C) h(L) = {aabaabcaab, aabcaabcccd, aabcaabaabaab, aabaabcaabaabc}
(D) h(L) = {aabaabcaab, aabcaabcccd, aabcaabaabcaabc, aabaabcaabaab}

Q215. Let h(L) = {aabaabaabccccdaab, cccdaabccccdaabaabc} then L will be
(A){00020, 21201}
(B){00120, 20201}
(C){00120, 21201}
(D) {00020, 20201}

Q216. Let A = {xx | x  {a, b}*}. Consider homomorphism h : {a, b}* → {0, 1}* with h(a) = 00,
h(b) = ϵ. What is h(A)?
(A) {04n | n ≥ 0}
(B) {0n | n ≥ 0}
(C) {02n | n ≥ 0}
(D) none of these
For next three questions suppose h is the homomorphism from {0,1,2} to {a,b} defined by
h(0) = a; h(1) = ab; h(2) = ba.
Q217. What is h(21120)
(A) baababbaa (B) bababbaa
(C) bbaababbaa (D) abaababbaa

Q218. If L = 01*2, then what is h(L)?
(A)aab(ab)*ba (B) (ab)*ba
(C) a(ab)*ba (D) aa(ab)*ab
Q219. If L = a(ba)*, then what is h-1(L)?

(A) 02*1*0 (B) 02*
(C) 1*0 (D) 02*U 1*0

Q220. The pumping lemma for regular languages implies that
(A) Every regular language contains a string that can be pumped.
(B) All strings in a regular language can be written as uvw so that uviw is also in
the language when i ≥ 0.
(C) A regular language is infinite if and only if it contains a string that can be
pumped
(D) Regular languages are closed under the regular operations
Answer : B
Solution:
By the definition of pumping lemma, all string in a regular language can be written as
uvw so that uviw is also in the language when i0.

Q221. Let L = {anbm | n > m ≥ 0} is
(A) not regular because ap+1bp cannot be pumped
(B) regular because it is a subset of a*b*
(C) regular because it is described by a regular expression
(D) not regular because apbp cannot be pumped.
Answer : A
Solution:
(a) It is regular ap+1 bp aaabb.
aa(ab)nb
aaababbso it is not pumped for this type of string so this is not regular .
(b) False because apbp is not part of anbm, n>m≥ 0
Q222. [MSQ]
Consider the language L = {aibj | j < i}. Which of the following string can be used in
a pumping lemma proof that L is not regular? [Assume n is pumping length]
(A) anbn (B) a2nbn (C) a2n+1b2n (D) (ab)na
Answer: B, C
Solution: Pumping lemma: For any regular language L, there exists an integer n, such
that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L
Options (A) and (D) are not correct because both strings don‟t belong to L.
Option (B): Given string x= a2nbn
Case I: If u = 𝜆, v = an, w = anbn then uviw  L for i =0.
Case II: If 𝑢 = 𝑎𝑛−𝑘 , 𝑣 = 𝑎𝑘 𝑘 ≥ 1 , 𝑤 = 𝑎𝑛 𝑏𝑛 𝑡ℎ𝑒𝑛 𝑢𝑣 𝑖 𝑤  𝐿; 𝑓𝑜𝑟 𝑖 = 0, 𝑛 = 1, 𝑘 = 1
So, this is correct string to proof L is non-regular.
Option C: Given string 𝑥 = 𝑎2𝑛+1 𝑏𝑛
Case I: If 𝑢 = 𝜆, 𝑣 = 𝑎𝑛 , 𝑤 = 𝑎𝑛+1 𝑏𝑛 𝑡ℎ𝑒𝑛 𝑢𝑣 𝑖 𝑤  𝐿 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖 = 0
Case II: If 𝑢 = 𝑎𝑛−𝑘 , 𝑣 = 𝑎𝑘 (𝑘 ≥ 1), 𝑤 = 𝑎𝑛+1 𝑏𝑛 , 𝑡ℎ𝑒𝑛 𝑢𝑣 𝑖 𝑤  𝐿 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖 = 0
So, this is incorrect string to proof L is non-regular.
So, option (B)& (C)are correct.

Q223. The pumping lemma for regular languages can be proved by
(A) showing that an NFA can be converted to an equivalent DFA.
(B) showing that the regular languages are closed under the regular operations.
(C) showing that an NFA computation must repeat a state.
(D) showing that a DFA computation must repeat a state.
Answer : D
Solution: The pumping lemma for regular languages can be proved by showing that a
DFA computation must repeat a state. Because pumping lemma is defined for infinite
regular language.
Q224. Consider the language L= {w : Σ* w is a palindrome } is not regular.

Which of the following are good choices of a string to pick to show that L is not regular
with the help of pumping lemma?
(A) apbbap
(B) ap
(C) bapb
(D) All of the above are good choices of strings
Answer : A
Solution:
Q225. {anbm : n > m > 0} is

(A) not regular because ap+1bp cannot be pumped
(B) regular because it is a subset of a*b*
(C) not regular because apbp cannot be pumped
(D) regular because it is described by a regular expression
Answer : A
Solution:
Q226. Let L be the regular language (11)*0*1* and L' = {(11)n10m1m | n, m>= 0}. Then L  L' is
(A) regular by closure under union
(B) not regular because it contains 0m1m
(C) regular because you can always pump by setting v to be the leading 1 or 11
(D) not regular because L' is not regular, because 10p1p cannot be pumped in L'
Answer : D

Q227. How many of the following statement is/are false? _________
1. The pumping lemma for regular languages is about proving a language to be regular.
2. The language {ww : w * with |w| ≥2 } is not regular.
3. The language {w  {a +b)* and the number of occurrences of a in w is the same as that
of b in w} is not regular.
4. The language {w {a +b)* : the number of occurrences of ab in w is the same as that of
ba in w} is not regular.
5. Every non-regular language is infinite.
Answer: 2
Solution: 1 & 4 are false.

Basic TOC Regular - Sloution

Uploaded by

Copyright:

Available Formats

Basic TOC Regular - Sloution

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Basic TOC Regular - Sloution

Uploaded by

Copyright:

Available Formats

GATE Computer Science & IT

ctice Questions Booklet

S. No. CHAPTERS P. No.

Q1. Consider the follwing grammar G:

The grammar G belongs to which type of Chomsky classification?

Q2. Consider the following grammar G with start symbol S

BASIC THEORY OF COMPUTATION Page 1

Q3. Consider the following grammar G with start symbol S

BASIC THEORY OF COMPUTATION Page 2

Q5. Consider the following grammar G with starting symbol S:

BASIC THEORY OF COMPUTATION Page 3

BASIC THEORY OF COMPUTATION Page 4

Q8. A grammar has the following productions:

BASIC THEORY OF COMPUTATION Page 5

BASIC THEORY OF COMPUTATION Page 6

BASIC THEORY OF COMPUTATION Page 7

Q12. Consider the grammar G:

BASIC THEORY OF COMPUTATION Page 8

BASIC THEORY OF COMPUTATION Page 9

Q15. A grammar is described as follow:

BASIC THEORY OF COMPUTATION Page 10

BASIC THEORY OF COMPUTATION Page 11

BASIC THEORY OF COMPUTATION Page 12

BASIC THEORY OF COMPUTATION Page 14

What is the language generated by this grammar?

BASIC THEORY OF COMPUTATION Page 17

BASIC THEORY OF COMPUTATION Page 18

Q23. Which language generates the grammar G given by the productions?

Q24. Consider the following grammar G:

BASIC THEORY OF COMPUTATION Page 19

BASIC THEORY OF COMPUTATION Page 20

BASIC THEORY OF COMPUTATION Page 21

BASIC THEORY OF COMPUTATION Page 22

BASIC THEORY OF COMPUTATION Page 23

BASIC THEORY OF COMPUTATION Page 24

BASIC THEORY OF COMPUTATION Page 25

BASIC THEORY OF COMPUTATION Page 26

BASIC THEORY OF COMPUTATION Page 27

BASIC THEORY OF COMPUTATION Page 28

(i) For 1001 : T, F, F, F, F (ii) For 110 : F, F, F, F, T

BASIC THEORY OF COMPUTATION Page 30

BASIC THEORY OF COMPUTATION Page 31

BASIC THEORY OF COMPUTATION Page 32

BASIC THEORY OF COMPUTATION Page 34

Q42. The regular expression b* + b*ab*+ b*ab*ab* represents the language

BASIC THEORY OF COMPUTATION Page 35

Q44. Regular expression r = (aa*b)* (aa* + ) is equivalent to:

BASIC THEORY OF COMPUTATION Page 36

BASIC THEORY OF COMPUTATION Page 37

BASIC THEORY OF COMPUTATION Page 38

Q47. How many of the following is/are true? __________

BASIC THEORY OF COMPUTATION Page 39

BASIC THEORY OF COMPUTATION Page 41

BASIC THEORY OF COMPUTATION Page 42

BASIC THEORY OF COMPUTATION Page 43

BASIC THEORY OF COMPUTATION Page 44

BASIC THEORY OF COMPUTATION Page 45

BASIC THEORY OF COMPUTATION Page 46

Q55. The regular expression (a + b)*a(a + b)* represents the language

Q42. The regular expression b* + bab+ babab* represents the language

Q44. Regular expression r = (aab) (aa* + ) is equivalent to:

Q55. The regular expression (a + b)a(a + b) represents the language

(A) (011)10(00 +1)