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:
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}
