Regular Expressions Questions-Answers – Theory of Computation

Regular Expressions Questions-Answers – Theory of Computation

Q1➡ |Regular Expressions
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
i ➥ 10*(0*10*10*)*
ii ➥ ((0 + 1)*1(0 + 1)*1)*10*
iii ➥ (0*10*10*)*10*
iv ➥ (0*10*10*)*0*1

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q2➡ |Regular Expressions
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 :
i ➥ Only (i) is correct
ii ➥ Only (ii) is correct
iii ➥ Neither (i) nor (ii) is correct
iv ➥ Both (i) and (ii) are correct

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q3➡ |Regular Expressions
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 ?
i ➥ 0*1+0*1*
ii ➥ 0*1*0+1*
iii ➥ 0*1*0*1+
iv ➥ 0+1*0*1*

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q4➡ |Regular Expressions
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
i ➥ I, III and VI only
ii ➥ IV, V and VI only
iii ➥ II, IV and V only
iv ➥ I, IV and V only

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q5➡ |Regular Expressions
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:
i ➥ 12
ii ➥ 11
iii ➥ 10
iv ➥ 15

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q6➡ |Regular Expressions
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 :
i ➥ 5
ii ➥ 10
iii ➥ 8
iv ➥ 12

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q7➡ |Regular Expressions
Which of the regular expressions corresponds to this grammar ?
S →AB/AS, A→a/aA, B→b
i ➥ aa*b +
ii ➥ aa*b
iii ➥ (ab)*
iv ➥ a(ab)*

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q8➡ |Regular Expressions
Regular expression a+b denotes the set :
i ➥ {a}
ii ➥ {ε, a, b}
iii ➥ {a, b}
iv ➥ None of these

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q9➡ |Regular Expressions
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)
i ➥ Only (i) is correct
ii ➥ Only (ii) is correct
iii ➥ Neither (i) nor (ii) is correct
iv ➥ Both (i) and (ii) are correct

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q10➡ |Regular Expressions
Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is
i ➥ (1 + 010)*
ii ➥ (01 + 10)*
iii ➥ (1 + 010)* (0 + λ)
iv ➥ (1 + 01)* (0 + λ)

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q11➡ |Regular Expressions
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by:
i ➥ a*b
ii ➥ a*baa*
iii ➥ a*ba*
iv ➥ None of the above

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q12➡ |Regular Expressions
“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
i ➥ (ii) and (iii) are same, (i) is different.
ii ➥ (ii) and (iii) are not same.
iii ➥ (i), (ii) and (iii) are different.
iv ➥ (i), (ii) and (iii) are same.

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q13➡ |Regular Expressions
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
i ➥ Either (i) or (ii) but not both of these are valid words.
ii ➥ Both (i) and (ii) are valid words and they take identical number of transformations for the production.
iii ➥ Both (i) and (ii) are valid words but they involve different number of transformations in the production.
iv ➥ None of these

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q14➡ |Regular Expressions
The regular expression given below describes : r=(1+01)* (0+λ)
i ➥ Set of all string not containing ‘11’
ii ➥ Set of all string not containing ‘00’
iii ➥ Set of all string containing ‘01’
iv ➥ Set of all string ending in ‘0’

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q15➡ |Regular Expressions
The regular expression for the complement of the language L = {anbm|n ≥ 4, m ≤ 3} is:
i ➥ (λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)*
ii ➥ (λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)*
iii ➥ (λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)*
iv ➥ (λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)*

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q16➡ |Regular Expressions
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?
i ➥ (a) and (b) only
ii ➥ (b) and (c) only
iii ➥ (c) and (a) only
iv ➥ (a), (b) and (c)

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q17➡ |Regular Expressions
How many states are there in a minimum state automata equivalent to regular expression given below?
regular expression is a*b(a+b)
i ➥ 1
ii ➥ 2
iii ➥ 3
iv ➥ 4

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q18➡ |Regular Expressions
The regular expression corresponding to the language L where L = { x ε {0, 1}*|x ends with 1 and does not contain substring 00 } is:
i ➥ (1 + 01) * (10 + 01)
ii ➥ (1 + 01) * 01
iii ➥ (1 + 01) * (1 + 01)
iv ➥ (10 + 01) * 01

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q19➡ |Regular Expressions
(00+01+10)(0+1)* represents:
i ➥ Strings not starting with 11
ii ➥ Strings of odd length
iii ➥ Strings starting with 00
iv ➥ Strings of even length

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q20➡ |Regular Expressions
The CFG S → aS|bS|a|b is equivalent to regular expression
i ➥ (a+b)
ii ➥ (a+b)(a+b)*
iii ➥ (a+b)(a+b)
iv ➥ all of these

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q21➡ |Regular Expressions
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?
i ➥ a*b*
ii ➥ (a|b)*
iii ➥ (ab)*
iv ➥ (a|b*)

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q22➡ |Regular Expressions
Regular expression (a|b)(a|b) denotes the set
i ➥ {a,b,ab,aa}
ii ➥ {a,b,ba,bb}
iii ➥ {a,b}
iv ➥ {aa,ab,ba,bb}

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q23➡ |Regular Expressions
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 ?
i ➥ (0*10*1)*
ii ➥ 0*(10*10*)*
iii ➥ 0*(10*1*)*0*
iv ➥ 0*1(10*1)10*

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon


Q24➡ |Regular Expressions
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
i ➥ Set of strings with 2 a’s and 2 b’s
ii ➥ Set of strings with 2 a’s 2 b’s followed by b
iii ➥ Set of strings with 2 a’s followed by b’s which is a multiple of 3
iv ➥ Set of strings with even number of a’s followed by odd number of b’s

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q25➡ |Regular Expressions
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?
i ➥ A (L + D)*
ii ➥ (L.D)*
iii ➥ L(L + D)*
iv ➥ L(L.D)*

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q26➡ |Regular Expressions
The minimum number of states required to automate the following Regular Expression:
(1) *(01+10) (1) *
i ➥ 4
ii ➥ 5
iii ➥ 3
iv ➥ 2

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q27➡ |Regular Expressions
Regular Expression denote precisely the __ of Regular Language.
i ➥ Class
ii ➥ Power Set
iii ➥ Super Set
iv ➥ None of the mentioned

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q28➡ |Regular Expressions
(0+ε) (1+ε) represents
i ➥ {0, 1, 01, ε}
ii ➥ {0, 1, ε}
iii ➥ {0, 1, 01 ,11, 00, 10, ε}
iv ➥ {0, 1}

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q29➡ |Regular Expressions
In order to represent a regular expression, the first step to create the transition diagram is:
i ➥ Predict the number of states to be used in order to construct the Regular expression
ii ➥ Null moves are not acceptable, thus should not be used
iii ➥ Create the NFA using Null moves
iv ➥ None

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q30➡ |Regular Expressions
The difference between number of states with regular expression (a + b) and (a + b) * is:
i ➥ 3
ii ➥ 2
iii ➥ 1
iv ➥ 0

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q31➡ |Regular Expressions
Simplify the following regular expression:
ε+1*(011) *(1*(011) *) *
i ➥ (1+011) *
ii ➥ (1*(011) *)
iii ➥ (1+(011) *) *
iv ➥ (1011) *

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q32➡ |Regular Expressions
Which among the following are incorrect regular identities?
i ➥ εR=R
ii ➥ ε*=ε
iii ➥ Ф*=ε
iv ➥ RФ=R

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q33➡ |Regular Expressions
A finite automaton accepts which type of language:
i ➥ Type 3
ii ➥ Type 2
iii ➥ Type 1
iv ➥ Type 0

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q34➡ |Regular Expressions
The appropriate precedence order of operations over a Regular Language is
i ➥ Kleene, Dot, Union
ii ➥ Star, Union, Dot
iii ➥ Kleene, Union, Concatenate
iv ➥ Kleene, Star, Union

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q35➡ |Regular Expressions
Regular Expression R and the language it describes can be represented as:
i ➥ R, R(L)
ii ➥ L(R), R(L)
iii ➥ R, L(R)
iv ➥ All

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q36➡ |Regular Expressions
Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
i ➥ {w | w is a string of length multiple of 3}
ii ➥ {w | w is a string of length 3}
iii ➥ {w | w is a string of odd length}
iv ➥ All

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q37➡ |Regular Expressions
If ∑= {0,1}, then Ф* will result to:
i ➥ ε
ii ➥ Ф
iii ➥
iv ➥ None of the mentioned

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q38➡ |Regular Expressions
The finite automata accept the following languages:
i ➥ Context Free Languages
ii ➥ Context Sensitive Languages
iii ➥ Regular Languages
iv ➥ All the mentioned

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q39➡ |Regular Expressions
(a + b*c) most correctly represents:
i ➥ (a +b) *c
ii ➥ (a)+((b)*.c)
iii ➥ (a + (b*)).c
iv ➥ a+ ((b*).c)

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q40➡ |Regular Expressions
Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ∑= {r, t}
i ➥ (rt)*
ii ➥ (tr)*
iii ➥ (r*t*)
iv ➥ (t*r*)

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon


Q41➡ |Regular Expressions
Which among the following is equivalent to the given regular expression?
01*+1
i ➥ (0(1)*)+1
ii ➥ ((0*1)1*)*
iii ➥ (01)*+1
iv ➥ 0((1)*+1)

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon


Q42➡ |Regular Expressions
Which among the following looks similar to the given expression?
((0+1). (0+1)) *
i ➥ {xϵ {0,1} *|x is all binary number with even length}
ii ➥ {xϵ {0,1} |x is all binary number with even length}
iii ➥ {xϵ {0,1} *|x is all binary number with odd length}
iv ➥ {xϵ {0,1} |x is all binary number with odd length}

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


Q43➡ |Regular Expressions
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon


You should also practice on below topics
Regular Language Mode
Deterministic Finite Automaton (DFA),
Non-Deterministic Finite Automaton (NDFA),
Equivalence of DFA and NDFA,
Regular Languages,
Regular Grammars,
Regular Expressions,
error: Content is protected !!
Open chat
1
Hi,how Can We Help You ?