WorksheetsTAFL Unit 2 Quiz: Regular Expressions
Total questions: 20
Worksheet time: 10mins
Which of the following is a valid regular expression?
a(b|c)*
a(b+c
a|b)*
ab(**
Kleene's Theorem states the equivalence between:
Regular expressions and context-free grammars
DFA and Turing machines
Regular expressions and finite automata
Context-free grammars and pushdown automata
Which of the following is not a closure property of regular languages?
Union
Intersection
Complement
Infinite Reversal
What does the Pumping Lemma prove?
A language is regular
A language is not regular
A language is context-free
A language is finite
Arden's Theorem is used to:
Convert a DFA to a regular expression
Eliminate null transitions
Minimize a DFA
Prove non-regularity
Which of the following languages is not regular?
L = {a^n | n ≥ 0}
L = {a^n b^n | n ≥ 0}
L = {a, aa, aaa, …}
L = {a^n b^m | n, m ≥ 0}
The Pigeonhole Principle is used in the Pumping Lemma to:
Minimize states
Ensure repetition
Prove context-free grammars
Remove dead states
What is the minimum number of states in a DFA to accept all strings over {0,1} with an even number of 0s?
1
2
3
4
A language is regular if it can be accepted by:
PDA
Turing Machine
DFA
Context-Free Grammar
Which of the following is decidable?
Membership problem for DFA
Ambiguity in CFG
Halting problem
Equivalence of two Turing Machines
In a finite automaton, what does a transition graph represent?
Language hierarchy
Parsing rules
State transitions
Context-free derivations
Regular expressions can be used to describe:
Context-free languages
Recursive languages
Regular languages
Undecidable languages
Which of the following is true for DFA and NFA?
Every DFA is an NFA
Every NFA is a DFA
NFAs and DFAs accept different languages
NFA has more computational power
Which method is used to derive a regular expression from finite automata?
Pumping Lemma
Kleene's Algorithm
Arden's Theorem
Turing Reduction
The language L = {a^n b^m | n ≠ m} is:
Regular
Context-Free
Non-regular
Recursive
Which of the following operations do regular languages support under closure properties?
Union
Concatenation
Kleene Star
All of the above
Which of the following languages can be proven non-regular using the Pumping Lemma?
L = {a^n b^n | n ≥ 0}
L = {a^n b^m | n, m ≥ 0}
L = {a^n | n ≥ 0}
L = {a, aa, aaa}
The decision problem "Is a given DFA empty?" is:
Undecidable
NP-Hard
Decidable
Recursive Enumerable
What does Arden's theorem state about the equation X = rX + s?
X = r* s
X = s r*
X = r + s
X = r* + s
If a DFA has n states, and the input string is of length > n, then:
The DFA halts
A state must repeat (Pigeonhole Principle)
It accepts
It is non-deterministic
