Automata Theory Multiple Choice Questions on “Regular Expression-Introduction”.
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
Answer: a
Clarification: According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
Answer: b
Clarification: A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
Answer: d
Clarification: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.
4. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
Answer: d
Clarification: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Answer: a
Clarification: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
6. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
Answer: b
Clarification: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.
7. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
Answer: b
Clarification: By distributive property (Regular expression identities), we can prove the given identity to be Ф.
8. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
Answer: a
Clarification: RR*=R+ as R+ means the occurrence to be at least once.