Q.1 Which of the following is a regular expression over the alphabet {a, b}?
a*b*
a+b*
a**b
ab^
Explanation - A regular expression can use *, +, and concatenation operators. a*b* is valid, representing zero or more 'a's followed by zero or more 'b's.
Correct answer is: a*b*
Q.2 What is the language denoted by the regular expression (a|b)*?
All strings containing at least one a or b
All strings over the alphabet {a, b}
Strings with exactly one a or b
Empty string only
Explanation - The Kleene star (*) allows for any number of repetitions, including zero, and (a|b) denotes either 'a' or 'b'. Thus, (a|b)* represents all strings over {a, b}.
Correct answer is: All strings over the alphabet {a, b}
Q.3 Which of the following languages is NOT regular?
{a^n b^n | n ≥ 0}
{a, b}*
Strings ending with 'ab'
Empty string language
Explanation - The language {a^n b^n | n ≥ 0} requires matching numbers of a's and b's, which cannot be represented by a regular expression. It is context-free but not regular.
Correct answer is: {a^n b^n | n ≥ 0}
Q.4 Which operation is NOT allowed in regular expressions?
Union
Concatenation
Kleene star
Intersection
Explanation - Standard regular expressions allow union (|), concatenation, and Kleene star (*). Intersection is not directly supported in classical regular expressions.
Correct answer is: Intersection
Q.5 The regular expression a(b|c)* represents:
Strings starting with a followed by zero or more b's or c's
Strings containing exactly one a
Strings ending with a
Strings containing only b's or c's
Explanation - The expression a(b|c)* starts with 'a' and then allows any number (including zero) of b's or c's.
Correct answer is: Strings starting with a followed by zero or more b's or c's
Q.6 Which of the following regular expressions matches the empty string?
ε
a*
a?
All of the above
Explanation - ε explicitly represents the empty string. a* allows zero occurrences of 'a', and a? allows zero or one occurrence, so all match the empty string.
Correct answer is: All of the above
Q.7 The regular expression (0|1)*1 represents which type of strings over {0,1}?
Strings ending with 1
Strings starting with 1
Strings with at least one 0
Strings with equal numbers of 0 and 1
Explanation - (0|1)* represents any sequence of 0s and 1s, and the trailing 1 ensures the string ends with 1.
Correct answer is: Strings ending with 1
Q.8 Which of these is equivalent to the regular expression (ab)*?
a*b*
(a*b*)*
ababab...
ε, ab, abab, ababab...
Explanation - The Kleene star allows zero or more repetitions of 'ab'. So the language includes the empty string, 'ab', 'abab', etc.
Correct answer is: ε, ab, abab, ababab...
Q.9 Which statement is TRUE about regular languages?
All finite languages are regular
All regular languages are finite
All context-free languages are regular
No finite language is regular
Explanation - Finite languages can always be represented using a finite union of strings, making them regular.
Correct answer is: All finite languages are regular
Q.10 The regular expression a+b+ matches:
Strings with at least one 'a' followed by at least one 'b'
Strings with zero or more 'a's followed by zero or more 'b's
Strings containing only 'a's or 'b's
Strings starting and ending with 'a'
Explanation - + denotes one or more occurrences. So a+ requires at least one 'a', b+ requires at least one 'b'.
Correct answer is: Strings with at least one 'a' followed by at least one 'b'
Q.11 Which regular expression denotes strings over {0,1} with an even number of 0s?
(1*01*0)*1*
0*1*
(01)*
0+1+
Explanation - Each 0 must appear in pairs possibly separated by any number of 1s. This expression captures all strings with an even number of 0s.
Correct answer is: (1*01*0)*1*
Q.12 Which of the following is NOT a property of regular languages?
Closed under union
Closed under concatenation
Closed under intersection
Closed under reversal
Explanation - Regular languages are closed under union, concatenation, and reversal, but not always trivially under intersection (although two regular languages' intersection is regular, intersection is not a primitive operation in regex).
Correct answer is: Closed under intersection
Q.13 The regular expression (a|b)(a|b) represents strings of:
Length 2 over {a,b}
All strings over {a,b}
Length 1 strings
Length 3 strings
Explanation - Each (a|b) chooses one symbol. Two such concatenated expressions generate all strings of length 2.
Correct answer is: Length 2 over {a,b}
Q.14 The language generated by (ab|ba)* contains:
Strings with even length
Strings with odd length
Strings starting with a
Strings with exactly one 'a'
Explanation - Each repetition produces two symbols (ab or ba), so any string generated has even length.
Correct answer is: Strings with even length
Q.15 Which of the following languages can be represented by a regular expression?
{a^n b^n c^n | n ≥ 0}
{w | w contains 'abc'}
{a^n b^m c^n | n,m ≥ 0}
{a^n b^n | n ≥ 0}
Explanation - The language of strings containing 'abc' can be expressed as .*abc.* in regex, which is regular.
Correct answer is: {w | w contains 'abc'}
Q.16 Which regular expression denotes the empty language?
∅
ε*
a*
(a|b)*
Explanation - The empty set ∅ represents a language with no strings. Other expressions denote non-empty languages.
Correct answer is: ∅
Q.17 What is the significance of the Kleene star (*) in regular expressions?
It denotes zero or more repetitions
It denotes exactly one repetition
It denotes one or more repetitions
It denotes optional repetition
Explanation - The Kleene star allows the preceding element to repeat zero or more times.
Correct answer is: It denotes zero or more repetitions
Q.18 Which of the following expressions matches strings containing only 'a's of length divisible by 3?
(aaa)*
a*
a{3}
(a|a)*
Explanation - The group 'aaa' repeated zero or more times ensures string length is a multiple of 3.
Correct answer is: (aaa)*
Q.19 The regular expression (a|b|c)* over {a,b,c} generates:
All strings over {a,b,c}
All strings of length 3
Strings containing exactly one a
Only empty string
Explanation - The Kleene star allows zero or more repetitions of a, b, or c, generating all strings over the alphabet.
Correct answer is: All strings over {a,b,c}
Q.20 Which of the following is true about concatenation in regular expressions?
It joins two expressions sequentially
It represents alternation
It denotes zero occurrences
It denotes one or more repetitions
Explanation - Concatenation simply sequences two regular expressions one after another.
Correct answer is: It joins two expressions sequentially
Q.21 The language denoted by (0|1)*0(0|1)* contains:
Strings containing at least one 0
Strings containing at least one 1
Strings ending with 1
Strings of even length
Explanation - The expression ensures there is at least one 0 somewhere in the string, surrounded by any sequence of 0s or 1s.
Correct answer is: Strings containing at least one 0
Q.22 Which regular expression represents all strings over {a,b} except the empty string?
(a|b)+
(a|b)*
ε
∅
Explanation - + ensures at least one occurrence of a or b, excluding the empty string.
Correct answer is: (a|b)+
Q.23 Which of the following is an example of a finite regular language?
{a, aa, aaa}
{a^n | n ≥ 0}
{w | w contains an equal number of a's and b's}
{0^n1^n | n ≥ 0}
Explanation - Finite languages with a limited number of strings are always regular.
Correct answer is: {a, aa, aaa}
Q.24 The regular expression (ab|a)* represents:
Strings composed of any number of 'a' or 'ab' sequences
Strings with equal number of a's and b's
Strings containing exactly one 'b'
Empty string only
Explanation - The Kleene star allows repetition of either 'a' or 'ab' any number of times, including zero.
Correct answer is: Strings composed of any number of 'a' or 'ab' sequences