1
Which regular expression represents all strings over {a, b} that end with 'b'?
Correct Answer
(a+b)*b
โ MCQ PRACTICE
Formal Languages and Automata Theory Unit 2
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Formal Languages and Automata Theory - Unit-2
2
The language denoted by the regular expression โ
* is:
Correct Answer
{ฮต}
3
Which of the following is NOT a basic operator of regular expressions?
Correct Answer
Complementation
4
Which of the following is an application of regular expressions?
Correct Answer
Lexical analysis in compilers
5
Regular expressions are widely used in which of the following?
Correct Answer
Pattern matching and text search
6
The equivalence of regular expressions and finite automata is established by:
Correct Answer
Kleene's theorem
7
Which law is represented by r + s = s + r?
Correct Answer
Commutative law for union
8
Which law is represented by r + r = r?
Correct Answer
Idempotent law
9
Which law is represented by r(s + t) = rs + rt?
Correct Answer
Left distributive law
10
For any regular expression r, ฮตr = rฮต = r. Hence ฮต is the ______ for concatenation.
Correct Answer
Identity
11
For any regular expression r, โ
r = rโ
equals:
Correct Answer
โ
12
(r*)* is equivalent to:
Correct Answer
r*
13
(ฮต + r)* is equivalent to:
Correct Answer
r*
14
Which regular expression represents all strings over {0, 1} containing at least one 0?
Correct Answer
(0+1)*0(0+1)*
15
The method used to convert a DFA into a regular expression is:
Correct Answer
State elimination method
16
Thompson's construction is used to convert:
Correct Answer
A regular expression into an ฮต-NFA
17
Arden's theorem states that if P does not contain ฮต, then the equation R = Q + RP has the unique solution:
Correct Answer
R = QP*
18
In Arden's theorem, the condition that P must not contain ฮต is required to ensure:
Correct Answer
The solution is unique
19
The pumping lemma for regular languages is used to prove that a language is:
Correct Answer
Not regular
20
The pumping lemma is a ______ condition for a language to be regular.
Correct Answer
Necessary but not sufficient
21
In the pumping lemma, a string w with |w| โฅ p is split as w = xyz. Which condition must hold?
Correct Answer
|xy| โค p
22
In the pumping lemma, the condition on the middle part y is:
Correct Answer
|y| > 0
23
According to the pumping lemma, for all i โฅ 0:
Correct Answer
xyโฑz โ L
24
In the pumping lemma, the constant p is called the:
Correct Answer
Pumping length
25
Which of the following languages is NOT regular?
Correct Answer
{aโฟbโฟ | n โฅ 0}
26
Which of the following languages is NOT regular?
Correct Answer
{aแต | p is a prime number}
27
Regular languages are closed under:
Correct Answer
All of the mentioned
28
Which of the following is NOT a closure property of regular languages?
Correct Answer
Closure under infinite union
29
To obtain a DFA for the complement of a regular language, we:
Correct Answer
Swap accepting and non-accepting states of a complete DFA
30
The automaton for the intersection of two regular languages is built using:
Correct Answer
Product construction
31
The set difference L โ M of two regular languages L and M equals:
Correct Answer
L โฉ Mฬ
32
The reversal of a regular language is:
Correct Answer
Always regular
33
Regular languages are closed under homomorphism.
Correct Answer
True
34
Which of the following problems is decidable for regular languages?
Correct Answer
All of the mentioned
35
A DFA accepts a non-empty language if and only if:
Correct Answer
An accepting state is reachable from the start state
36
A DFA accepts an infinite language if and only if:
Correct Answer
A cycle lies on some path from the start state to an accepting state
37
The time taken to test whether a string of length n is accepted by a DFA is:
Correct Answer
O(n)
38
Which algorithm is used to test the equivalence of two DFAs and to minimize a DFA?
Correct Answer
Table-filling algorithm
39
Two states p and q of a DFA are distinguishable if there exists a string w such that:
Correct Answer
Exactly one of ฮด(p,w) and ฮด(q,w) is an accepting state
40
In the table-filling algorithm, the pairs initially marked as distinguishable are:
Correct Answer
(accepting state, non-accepting state)
41
DFA minimization removes:
Correct Answer
Unreachable states and merges equivalent states
42
The Myhill-Nerode theorem states that a language L is regular if and only if:
Correct Answer
It has a finite number of equivalence classes
43
The minimal DFA for the language of all strings over {0, 1} ending with '01' has how many states?
Correct Answer
3
44
The minimal DFA of a regular language is:
Correct Answer
Unique up to renaming of states