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, |