Automata & Complexity Theory – Chapter 1: Introduction
Assessment Items
Part 1: Multiple Choice Questions (50 items)
Each question has four options; choose the best answer.
1. Which of the following is not a branch of the theory of computation?
a) Automata theory
b) Complexity theory
c) Computability theory
d) Cryptography theory
2. A set is:
a) A structured collection of elements
b) A collection of elements with no structure other than membership
c) Always infinite
d) Ordered and indexed
3. The notation m \in S means:
a) m is a subset of S
b) m is not in S
c) m is an element of S
d) m equals S
4. The union of sets A and B is defined as:
a) A \cup B = \{ x : x \in A \text{ and } x \in B \}
b) A \cup B = \{ x : x \in A \text{ or } x \in B \}
c) A \cup B = \{ (x, y) : x \in A, y \in B \}
d) A \cup B = A \cdot B
5. The concatenation of sets A and B produces:
a) A set of ordered pairs
b) A set of union elements
c) A set of strings
d) A set of intersections
6. The Kleene star \Sigma^* includes:
a) All strings over Σ except λ
b) Only strings of length ≥ 1
c) All strings over Σ including λ
d) Only finite strings
7. \Sigma^+ is defined as:
a) \Sigma^* \cup \{ \lambda \}
b) \Sigma^* - \{ \lambda \}
c) \Sigma^0 \cup \Sigma^1
d) \Sigma^1 \cup \Sigma^2
8. A formal language is:
a) A natural language like English
b) A set of symbols with strict formation rules
c) Always ambiguous
d) Only used in linguistics
9. An alphabet is:
a) An infinite set of symbols
b) A set of words
c) A finite set of symbols
d) A language
10. The length of string "automata" is:
a) 7
b) 8
c) 9
d) 10
11. The empty string is denoted by:
a) ∅
b) λ or ε
c) Σ
d) ∞
12. \Sigma^k represents:
a) Strings of length ≤ k
b) Strings of length exactly k
c) Strings of length ≥ k
d) The Kleene star
13. A language is:
a) Always finite
b) A subset of \Sigma^*
c) A grammar
d) An alphabet
14. A grammar G is defined as:
a) (V, T, P)
b) (V, T, S, P)
c) (V, Σ, S, P)
d) (Q, Σ, δ, q0, F)
15. In grammar notation, V stands for:
a) Variables
b) Terminals
c) Valid symbols
d) Verbs
16. The start symbol in a grammar is:
a) Always a terminal
b) An element of V
c) An element of T
d) Always ε
17. The production S → aSb generates:
a) Strings like ab, aabb, aaabbb
b) Only ab
c) Only aabb
d) Strings of only a's
18. Finite automata are:
a) Infinite state machines
b) Abstract computing devices with finite states
c) Used only in hardware design
d) Always non-deterministic
19. DFA stands for:
a) Deterministic Finite Automaton
b) Dynamic Finite Automaton
c) Digital Finite Automaton
d) Directed Finite Automaton
20. In a DFA, the transition function δ maps:
a) Q × Σ → 2^Q
b) Q × Σ → Q
c) Q × Σ → Σ
d) Q → Σ
21. In an NFA, δ maps:
a) Q × Σ → Q
b) Q × Σ → 2^Q
c) Q × Σ → Σ
d) Q → 2^Σ
22. The initial state in a state diagram is shown with:
a) Double circle
b) A single incoming arrow
c) A labeled arc
d) A square
23. A final/accepting state is represented by:
a) A single circle
b) A double circle
c) A triangle
d) A square
24. A string is accepted by a DFA if processing ends in:
a) Any state
b) A non-final state
c) A final state
d) The initial state
25. The language accepted by a DFA M is:
a) \{ w \mid \delta(q_0, w) \in F \}
b) \{ w \mid w \in \Sigma^+ \}
c) \{ w \mid w \in \Sigma^* \}
d) \{ w \mid \delta(q_0, w) = q_0 \}
26. In an NFA, a string is accepted if:
a) All paths lead to a final state
b) At least one path leads to a final state
c) No path leads to a final state
d) It reaches the initial state
27. The main difference between DFA and NFA is:
a) Number of states
b) Determinism vs. non-determinism in transitions
c) Use of final states
d) Alphabet size
28. An ε-transition is allowed in:
a) DFA only
b) NFA only
c) Both DFA and NFA
d) Neither
29. Every DFA is:
a) An NFA
b) Not an NFA
c) More compact than an equivalent NFA
d) Unable to recognize regular languages
30. The term "automaton" comes from a Greek word meaning:
a) Machine
b) Self-acting
c) Computer
d) Logic
31. Which of the following is an application of finite automata?
a) Sorting numbers
b) Lexical analysis in compilers
c) Solving differential equations
d) Database indexing
32. In lexical analysis, finite automata help:
a) Optimize code
b) Tokenize source code
c) Generate object code
d) Parse grammar
33. Kleene closure of Σ = {0} is:
a) {λ, 0, 00, 000, ...}
b) {0, 00, 000, ...}
c) {λ}
d) {0}
34. If Σ = {a, b}, then Σ² = ?
a) {aa, ab, ba, bb}
b) {a, b, aa, bb}
c) {ab, ba}
d) {aa, bb}
35. The set { x : x ∉ S } given universal set U is:
a) S
b) U
c) Complement of S
d) ∅
36. Which is a deterministic automaton?
a) NFA
b) DFA
c) Both
d) Neither
37. If δ(a,0) = b and δ(a,0) = c in an automaton, it must be:
a) DFA
b) NFA
c) Neither
d) Both
38. A grammar’s productions define:
a) The alphabet
b) How strings are transformed
c) The finite automaton
d) The complexity class
39. The empty set is denoted by:
a) λ
b) ε
c) ∅
d) U
40. A string of length 0 is:
a) λ
b) a
c) ∅
d) Σ
41. Which of the following is a terminal symbol?
a) S
b) A
c) a
d) V
42. In the grammar S → aS | b, which string is generated?
a) abab
b) aabb
c) aaaab
d) bb
43. A finite automaton’s state diagram is a:
a) Graph
b) Table
c) Tree
d) Matrix
44. If Q = {q0, q1}, Σ = {0,1}, F = {q1}, and δ(q0,0)=q1, δ(q1,1)=q1, what is L(M)?
a) Strings ending with 0
b) Strings ending with 1
c) Strings starting with 0
d) Strings with at least one 0
45. NFA can have:
a) Multiple transitions for same input from a state
b) Only one transition per input
c) No transitions
d) Only ε-transitions
46. Which is true for both DFA and NFA?
a) They recognize regular languages
b) They have ε-transitions
c) They are always deterministic
d) They have infinite states
47. The transition table for a DFA shows:
a) One next state per (state, input) pair
b) Multiple next states
c) Only final states
d) Only initial states
48. In automata theory, “finite” refers to:
a) Input length
b) Number of states
c) Alphabet size
d) Language size
49. Which branch studies what problems are solvable by computers?
a) Automata theory
b) Complexity theory
c) Computability theory
d) Information theory
50. The theory of computation is primarily concerned with:
a) Building computers
b) Algorithms and their limits
c) Programming languages only
d) Data structures
---
Part 2: Fill in the Blanks (12 items)
Fill in the missing word(s).
1. The three main branches of the theory of computation are __________, complexity theory, and
computability theory.
2. A __________ is a collection of elements with no structure other than membership.
3. The __________ of sets A and B is {x : x ∈ A or x ∈ B}.
4. \Sigma^* is called the __________ of Σ.
5. \Sigma^+ = \Sigma^* - \{ \_\_\_ \} .
6. A __________ language has strict syntax and semantics.
7. The __________ of a string is the number of symbols it contains.
8. A grammar is defined as a 4-tuple (V, T, S, ____).
9. In a DFA, the transition function δ: Q × Σ → __________.
10. In an NFA, δ: Q × (Σ ∪ {ε}) → __________.
11. A string is accepted by an NFA if at least one path ends in a __________ state.
12. Finite automata are used in compilers for __________ analysis.
---
Part 3: Workout Problems (25 items)
Solve each problem step-by-step.
1. Given Σ = {x, y}, list all strings in Σ³.
2. If A = {1, 2} and B = {a, b}, find A ∪ B.
3. If A = {0, 1} and B = {a, b}, find A · B (concatenation).
4. For Σ = {a, b, c}, write three strings in Σ⁴.
5. Compute |"computation"|.
6. Write the Kleene closure for Σ = {0}.
7. Write Σ⁺ for Σ = {a}.
8. Identify V, T, S, and P in grammar:
G = ({S, A}, {a, b}, S, {S → aA, A → bS, A → ε})
9. Derive a string from the grammar in Q8.
10. Draw the state diagram for a DFA that accepts strings over {0,1} ending with 0.
11. Given DFA M = ({q0, q1}, {0,1}, δ, q0, {q1}) with δ(q0,0)=q1, δ(q1,1)=q1, δ(q1,0)=q0, δ(q0,1)=q0.
Is "010" accepted? Show steps.
12. Design an NFA over {a, b} that accepts strings ending with "ab".
13. Convert the NFA from Q12 to an equivalent DFA (outline steps).
14. Write the formal 5-tuple for a DFA that accepts even-length strings over {a}.
15. Write the formal 5-tuple for an NFA that accepts strings over {0,1} containing "01".
16. Given Σ = {p, q}, find |Σ*| (cardinality).
17. If L = {aⁿbⁿ | n ≥ 0}, is L finite or infinite?
18. Write a grammar for L = {aⁿbⁿ | n ≥ 0}.
19. Show derivation of "aaabbb" using your grammar from Q18.
20. Given δ table for DFA:
State 0 1
q0 q1 q0
q1 q1 q2
q2 q2 q1
F = {q2}. Process string "01001".
21. Define δ* for DFA (extended transition function).
22. For NFA with δ(q0,a)={q0,q1}, δ(q1,b)={q2}, find all states reachable from q0 on "ab".
23. Write the language accepted by a DFA that accepts strings over {0,1} with an odd number of 1's.
24. Draw DFA for strings over {a,b} that contain substring "aba".
25. Explain one real-world application of finite automata in detail.
Answer Key with Steps
Part 1: Multiple Choice Questions – Answers & Explanations
1. d) Cryptography theory – The three main branches are automata, complexity, and computability
theory.
2. b) A collection of elements with no structure other than membership – This is the definition of a set in
this context.
3. c) m is an element of S – \in denotes membership.
4. b) A \cup B = \{ x : x \in A \text{ or } x \in B \} – Union includes elements from either set.
5. a) A set of ordered pairs – Concatenation of sets A and B yields A \cdot B = \{(x,y) : x \in A, y \in B\} .
6. c) All strings over Σ including λ – Kleene star includes the empty string.
7. b) \Sigma^* - \{ \lambda \} – Kleene plus excludes the empty string.
8. b) A set of symbols with strict formation rules – Formal languages have precise syntax.
9. c) A finite set of symbols – Definition of an alphabet.
10. b) 8 – "automata" has 8 letters.
11. b) λ or ε – Standard notation.
12. b) Strings of length exactly k – \Sigma^k means strings of length k.
13. b) A subset of \Sigma^* – Formal definition of a language.
14. b) (V, T, S, P) – Grammar quadruple: Variables, Terminals, Start symbol, Productions.
15. a) Variables – V is the set of variables/non-terminals.
16. b) An element of V – Start symbol is a variable.
17. a) Strings like ab, aabb, aaabbb – The rule generates equal numbers of a's and b's.
18. b) Abstract computing devices with finite states – Definition of finite automata.
19. a) Deterministic Finite Automaton – Standard acronym.
20. b) Q × Σ → Q – In DFA, each transition leads to exactly one state.
21. b) Q × Σ → 2^Q – In NFA, transitions lead to a set of possible states.
22. b) A single incoming arrow – Standard notation.
23. b) A double circle – Standard notation for final states.
24. c) A final state – Acceptance condition.
25. a) \{ w \mid \delta(q_0, w) \in F \} – Definition of language accepted by DFA.
26. b) At least one path leads to a final state – NFA acceptance condition.
27. b) Determinism vs. non-determinism in transitions – Key distinction.
28. b) NFA only – ε-transitions are not allowed in standard DFA.
29. a) An NFA – Every DFA is a special case of NFA.
30. b) Self-acting – Etymology of "automaton".
31. b) Lexical analysis in compilers – Common application.
32. b) Tokenize source code – Lexical analysis function.
33. a) {λ, 0, 00, 000, ...} – Kleene closure includes empty string.
34. a) {aa, ab, ba, bb} – All possible strings of length 2.
35. c) Complement of S – Definition of set complement.
36. b) DFA – DFA is deterministic.
37. b) NFA – Multiple transitions for same input indicate non-determinism.
38. b) How strings are transformed – Productions define rewriting rules.
39. c) ∅ – Standard notation for empty set.
40. a) λ – Empty string has length 0.
41. c) a – Lowercase letters typically denote terminals.
42. c) aaaab – The grammar generates aⁿb where n ≥ 0.
43. a) Graph – Specifically a directed graph (digraph).
44. b) Strings ending with 1 – Only strings ending in 1 reach q1.
45. a) Multiple transitions for same input from a state – Non-deterministic property.
46. a) They recognize regular languages – Both accept regular languages.
47. a) One next state per (state, input) pair – Deterministic property.
48. b) Number of states – Finite automata have finite states.
49. c) Computability theory – Studies solvability.
50. b) Algorithms and their limits – Core focus of the field.
---
Part 2: Fill in the Blanks – Answers
1. automata theory
2. set
3. union
4. Kleene star
5. λ or ε
6. formal
7. length
8. P
9. Q
10. 2^Q
11. final or accepting
12. lexical
---
Part 3: Workout Problems – Solutions with Steps
1. Given Σ = {x, y}, list all strings in Σ³.
Answer: {xxx, xxy, xyx, xyy, yxx, yxy, yyx, yyy}
Steps: All combinations of length 3 using x and y.
2. If A = {1, 2} and B = {a, b}, find A ∪ B.
Answer: {1, 2, a, b}
Steps: Union includes all distinct elements.
3. If A = {0, 1} and B = {a, b}, find A · B (concatenation).
Answer: {(0,a), (0,b), (1,a), (1,b)}
Steps: Ordered pairs with first from A, second from B.
4. For Σ = {a, b, c}, write three strings in Σ⁴.
Answer: e.g., "aaaa", "abcb", "cccc"
Steps: Any strings of length 4 using a,b,c.
5. Compute |"computation"|.
Answer: 11
Steps: Count letters: c(1) o(2) m(3) p(4) u(5) t(6) a(7) t(8) i(9) o(10) n(11)
6. Write the Kleene closure for Σ = {0}.
Answer: {λ, 0, 00, 000, ...}
Steps: All possible strings of 0's including empty.
7. Write Σ⁺ for Σ = {a}.
Answer: {a, aa, aaa, ...}
Steps: Kleene plus excludes empty string.
8. Identify V, T, S, and P in grammar:
G = ({S, A}, {a, b}, S, {S → aA, A → bS, A → ε})
Answer:
V = {S, A}
T = {a, b}
S=S
P = {S → aA, A → bS, A → ε}
Steps: Compare to G = (V, T, S, P).
9. Derive a string from the grammar in Q8.
Answer: e.g., "ab"
Steps: S ⇒ aA ⇒ abS ⇒ ab (if A → ε after bS? Let's derive carefully)
Better: S ⇒ aA ⇒ aε = a (using A → ε)
Or: S ⇒ aA ⇒ abS ⇒ abaA ⇒ aba (using A → ε)
Actually: For "ab": S ⇒ aA ⇒ abS ⇒ ab (S must terminate? Need S → ε? Our grammar doesn't have S →
ε, so let's derive differently)
S ⇒ aA ⇒ abS ⇒ abaA ⇒ ababS ⇒ ... infinite unless we use A → ε
Let's do finite: S ⇒ aA ⇒ aε = a
Or: S ⇒ aA ⇒ abS ⇒ abaA ⇒ abaε = aba
So valid strings: "a", "aba", "ababa", etc.
Pick "aba".
10. Draw the state diagram for a DFA that accepts strings over {0,1} ending with 0.
Answer:
States: q0 (start), q1 (final)
Transitions:
· On 0: q0→q1, q1→q1
· On 1: q0→q0, q1→q0
Steps: q1 remembers last input was 0.
11. Given DFA M = ({q0, q1}, {0,1}, δ, q0, {q1}) with δ(q0,0)=q1, δ(q1,1)=q1, δ(q1,0)=q0, δ(q0,1)=q0. Is
"010" accepted? Show steps.
Answer: Yes
Steps:
δ(q0, 0) = q1
δ(q1, 1) = q1
δ(q1, 0) = q0 (not final) Wait, final state is q1, we end at q0 → NOT accepted
Let's recompute carefully:
δ*(q0, 010) = δ(δ(δ(q0,0),1),0)
= δ(δ(q1,1),0)
= δ(q1,0)
= q0
q0 ∉ F → Rejected.
So answer is No.
12. Design an NFA over {a, b} that accepts strings ending with "ab".
Answer:
States: q0(start), q1, q2(final)
Transitions:
· q0 on a: {q0, q1}
· q0 on b: {q0}
· q1 on b: {q2}
Steps: Allows any prefix, then 'a' followed by 'b' at end.
13. Convert the NFA from Q12 to an equivalent DFA (outline steps).
Answer:
Step 1: Start with ε-closure of q0: {q0}
Step 2: Compute transitions:
From {q0}:
· On a: {q0, q1}
· On b: {q0}
From {q0, q1}:
· On a: {q0, q1}
· On b: {q0, q2}
From {q0, q2}:
· On a: {q0, q1}
· On b: {q0}
Step 3: Mark final states containing q2: {q0,q2}
Steps: Subset construction method.
14. Write the formal 5-tuple for a DFA that accepts even-length strings over {a}.
Answer:
Q = {q0(even), q1(odd)}
Σ = {a}
δ: δ(q0,a)=q1, δ(q1,a)=q0
q0 = q0 (start)
F = {q0}
Steps: Even length means return to q0.
15. Write the formal 5-tuple for an NFA that accepts strings over {0,1} containing "01".
Answer:
Q = {q0, q1, q2}
Σ = {0,1}
δ:
· q0 on 0: {q0, q1}
· q0 on 1: {q0}
· q1 on 1: {q2}
· q2 on 0,1: {q2}
q0 = q0
F = {q2}
Steps: q1 remembers seeing 0, then needs 1 to reach final.
16. Given Σ = {p, q}, find |Σ| (cardinality).
Answer: Countably infinite
Steps: Σ contains infinitely many strings.
17. If L = {aⁿbⁿ | n ≥ 0}, is L finite or infinite?
Answer: Infinite
Steps: For each n, there's a string aⁿbⁿ.
18. Write a grammar for L = {aⁿbⁿ | n ≥ 0}.
Answer:
G = ({S}, {a,b}, S, {S → aSb, S → ε})
Steps: Context-free grammar.
19. Show derivation of "aaabbb" using your grammar from Q18.
Answer:
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb
Steps: Apply S → aSb three times, then S → ε.
20. Given δ table for DFA:
State 0 1
q0 q1 q0
q1 q1 q2
q2 q2 q1
F = {q2}. Process string "01001".
Answer: End at q1 → Rejected
Steps:
δ(q0,0)=q1
δ(q1,1)=q2
δ(q2,0)=q2
δ(q2,0)=q2
δ(q2,1)=q1
Final state q1 ∉ F.
21. Define δ* for DFA (extended transition function).
Answer:
δ: Q × Σ → Q
Base: δ(q, ε) = q
Inductive: δ(q, wa) = δ(δ(q, w), a) for w ∈ Σ, a ∈ Σ
Steps: Recursive definition for strings.
22. For NFA with δ(q0,a)={q0,q1}, δ(q1,b)={q2}, find all states reachable from q0 on "ab".
Answer: {q2}
Steps:
From q0 on "a": {q0,q1}
From {q0,q1} on "b":
· From q0 on b: ∅ (no transition)
· From q1 on b: {q2}
Union: {q2}
23. Write the language accepted by a DFA that accepts strings over {0,1} with an odd number of 1's.
Answer: L = {w ∈ {0,1}* | number of 1's in w is odd}
Steps: Description of language.
24. Draw DFA for strings over {a,b} that contain substring "aba".
Answer:
States: q0(no), q1(a), q2(ab), q3(aba-final)
Transitions:
· q0 on a→q1, on b→q0
· q1 on a→q1, on b→q2
· q2 on a→q3, on b→q0
· q3 on a→q3, on b→q3
Steps: Remember progress toward "aba".
25. Explain one real-world application of finite automata in detail.
Answer: Lexical Analysis in Compilers
Steps:
1. Source code is input as character stream
2. Finite automaton scans characters to recognize tokens
3. States correspond to token types (identifier, number, operator)
4. Transitions on characters move between states
5. Final states indicate complete token recognized
6. Example: Recognizing integers: digits transition to integer state
7. Efficiency: O(n) time, minimal memory
8. Forms first phase of compilation pipeline
---
Note: For diagrammatic answers (Q10, Q24), sketches would be needed but are described textually
here.
---
Answer keChapter 2: Regular Expressions & Regular Languages
Assessment Items
---
Part 1: Multiple Choice Questions (50 items)
1. A language is regular if:
a) It can be described by a regular expression
b) There exists a finite automaton that accepts it
c) Both a and b
d) It can be pumped
2. The primitive regular expressions are:
a) φ, λ, and a ∈ Σ
b) (r1 + r2), (r1.r2)
c) r* only
d) ε and Σ*
3. If r1 and r2 are regular expressions, which of these is not necessarily regular?
a) r1 + r2
b) r1*
c) r1 ∩ r2
d) r1.r2
4. The regular expression φ represents:
a) {ε}
b) { }
c) Σ*
d) Σ
5. L(ε) =
a) { }
b) {ε}
c) {0}
d) Σ*
6. For Σ = {a,b}, the expression (a+b)* denotes:
a) Only a's
b) Only b's
c) All strings over {a,b}
d) Only strings of length 1
7. The identity for concatenation is:
a) φ
b) ε
c) Σ
d) λ*
8. Ø* equals:
a) Ø
b) ε
c) Σ*
d) λ
9. R⁺ can be expressed as:
a) RR*
b) R*R
c) Both a and b
d) R + ε
10. (R) equals:
a) R
b) R*
c) R⁺
d) ε
11. The annihilator for concatenation is:
a) ε
b) φ
c) λ
d) Σ
12. The idempotent law for union states:
a) R + R = R
b) R.R = R
c) R* = R
d) R + ε = R
13. Arden's theorem is used to:
a) Prove a language is not regular
b) Solve equations of the form R = Q + RP
c) Convert NFA to DFA
d) Construct regular expressions from grammars
14. Which is a regular set property?
a) Complement of a regular set is regular
b) Intersection of two regular sets is regular
c) Both a and b
d) Neither a nor b
15. The reversal of a regular set is:
a) Always regular
b) Never regular
c) Regular only if finite
d) Regular only if infinite
16. Which identity is correct?
a) ε* = ε
b) ε* = φ
c) ε* = Σ*
d) ε* = λ
17. The left distributive law states:
a) L(M+N) = LM + LN
b) (M+N)L = ML + NL
c) L.(M+N) = L.M + L.N
d) Both a and b
18. For regular expressions, (a+b)* equals:
a) ab
b) (ab)*
c) a* + b*
d) ba
19. To construct an FA from an RE, we can use:
a) Thompson's Construction
b) Arden's theorem
c) Pumping lemma
d) Kleene's theorem
20. The first step in Thompson's construction is to:
a) Convert NFA to DFA
b) Build NFA with ε-moves from RE
c) Remove ε-transitions
d) Minimize the DFA
21. For RE 'a', the corresponding NFA has:
a) One state
b) Two states
c) Three states
d) One state with ε-loop
22. For RE 'ab', the NFA has:
a) 2 states
b) 3 states
c) 4 states
d) 1 state
23. For RE (a+b)*, the NFA contains:
a) ε-transitions
b) Only a-transitions
c) Only b-transitions
d) No final states
24. After constructing NFA with ε-moves, the next step is:
a) Apply pumping lemma
b) Remove ε-transitions
c) Convert to regular grammar
d) Check for regularity
25. A grammar is right-linear if productions are of form:
a) A → xB or A → x
b) A → Bx or A → x
c) A → xyz
d) A → BC
26. In left-linear grammar, productions are of form:
a) A → Bx or A → x
b) A → xB or A → x
c) A → x
d) A → ε
27. A grammar that is either right-linear or left-linear is called:
a) Context-free
b) Regular
c) Context-sensitive
d) Unrestricted
28. Example of right-linear grammar: S → abS | a. The language is:
a) (ab)a
b) a(ba)
c) (ab)*
d) ab
29. If a grammar has both right-linear and left-linear productions, it is:
a) Always regular
b) Never regular
c) Regular only if balanced
d) Not necessarily regular
30. Pumping lemma is used to:
a) Prove a language is regular
b) Prove a language is not regular
c) Construct FA from RE
d) Convert NFA to DFA
31. For pumping lemma, we choose string w such that:
a) |w| ≥ c
b) |w| < c
c) |w| = c
d) |w| = 0
32. In w = xyz, we require:
a) |y| = 0
b) |y| > 0
c) |xy| > c
d) |z| > 0
33. The condition |xy| ≤ c ensures:
a) y is in the first c symbols
b) x is long
c) z is short
d) y is at the end
34. To prove L is not regular using pumping lemma, we show:
a) For some k, xy^kz ∈ L
b) For some k, xy^kz ∉ L
c) For all k, xy^kz ∈ L
d) For all k, xy^kz ∉ L
35. For L = {a^i b^i | i ≥ 0}, we choose w =
a) a^p b^p
b) a^n b^n
c) (ab)^n
d) ab
36. In pumping lemma proof for a^n b^n, if x = a^p, y = a^q, z = a^r b^n, then pumping (k=2) gives:
a) a^{p+q+r} b^n
b) a^{p+2q+r} b^n
c) a^{p+q} b^{n+q}
d) a^n b^{n+q}
37. Which is not a regular language?
a) ab
b) (a+b)*
c) {a^n b^n | n ≥ 0}
d) All strings ending with 'a'
38. Regular languages are closed under:
a) Union
b) Intersection
c) Complement
d) All of these
39. The regular expression 010 represents:
a) Strings with exactly one 1
b) Strings with at least one 1
c) Strings with only 1's
d) Strings starting and ending with 1
40. To construct RE from FA, we use:
a) State elimination method
b) Pumping lemma
c) Thompson's construction
d) Arden's theorem on equations
41. For FA with states q1, q2, if q1 = q10 + ε, then q1 =
a) 0*
b) 0⁺
c) 1*
d) ε
42. Arden's theorem solution for R = Q + RP is:
a) R = QP*
b) R = QP
c) R = PQ
d) R = QP⁺
43. The regular set for (0+1)*0 is:
a) All strings ending with 0
b) All strings starting with 0
c) Strings with at least one 0
d) Strings with exactly one 0
44. Which is a regular grammar?
a) S → aSb | ε
b) S → aS | b
c) S → SS | a
d) S → aB, B → Sb
45. The language of regular grammar S → aS | b is:
a) ab
b) ab
c) ba*
d) a⁺b
46. Pumping lemma constant 'c' refers to:
a) Number of states in FA
b) Length of the string
c) Number of variables in grammar
d) Alphabet size
47. If L is regular, then:
a) L must be finite
b) L must be infinite
c) L can be finite or infinite
d) L must be countable
48. The expression (a+b) is equivalent to:
a) (a+b)*
b) ab
c) ba
d) (ab)*
49. For RE to FA conversion, after removing ε-transitions, we get:
a) NFA
b) DFA
c) ε-NFA
d) Regular grammar
50. A non-regular language:
a) Cannot be accepted by any FA
b) Can be accepted by NFA only
c) Can be accepted by PDA
d) Both a and c
---
Part 2: Fill in the Blanks (23 items)
1. A language is regular if there exists a(n) __________ for it.
2. The three basic operations in regular expressions are __________, concatenation, and Kleene star.
3. The regular expression φ represents the __________ language.
4. L(ε) = { __________ }.
5. If r1 and r2 are regular expressions, then r1 + r2 represents __________.
6. The Kleene star of regular expression r is written as __________.
7. The identity element for union is __________.
8. The identity element for concatenation is __________.
9. Ø* = __________.
10. The pumping lemma is used to prove that a language is __________ regular.
11. In w = xyz, we must have |y| __________ 0.
12. In pumping lemma, |xy| must be ≤ __________.
13. For L = {a^n b^n}, the pumping lemma shows it is __________ regular.
14. Regular languages are closed under intersection and __________.
15. Thompson's construction builds a(n) __________ from a regular expression.
16. After building ε-NFA, we remove __________ transitions.
17. A grammar is __________ if all productions are of form A → xB or A → x.
18. In left-linear grammar, productions have form A → __________ or A → x.
19. Regular grammars generate __________ languages.
20. Arden's theorem solves equations of form R = __________.
21. The solution to R = Q + RP is R = __________.
22. The regular expression (0+1)*0 denotes all strings ending with __________.
23. To convert FA to RE, we write __________ for each state.
---
Part 3: Workout Problems (25 items)
1. Write regular expression for all strings over {a,b} ending with 'aa'.
2. Write regular expression for all strings over {0,1} containing substring '101'.
3. Write regular expression for all strings over {a,b} with odd length.
4. Convert regular expression (a+b)*ab to English description.
5. Convert regular expression 01(0+1) to English description.
6. For Σ = {0,1}, give L(01).
7. For Σ = {a,b}, give L((ab)*).
8. Simplify: (a+b)*
9. Simplify: aa
10. Verify identity: R + R = R
11. Use Arden's theorem: Solve R = aR + b for R.
12. Construct ε-NFA for regular expression 'a'.
13. Construct ε-NFA for regular expression 'ab'.
14. Construct ε-NFA for regular expression 'a+b'.
15. Construct ε-NFA for regular expression 'a*'.
16. Convert ε-NFA from Q15 to NFA (remove ε-transitions).
17. Write right-linear grammar for language a*b.
18. Write left-linear grammar for language ab*.
19. Determine if grammar S → aS | Sb | ab is regular.
20. Apply pumping lemma to show L = {ww | w ∈ {a,b}*} is not regular.
21. Apply pumping lemma to show L = {a^p | p is prime} is not regular.
22. Given FA with transition: δ(q0,0)=q1, δ(q0,1)=q0, δ(q1,0)=q1, δ(q1,1)=q0, F={q1}. Write regular
expression.
23. Convert RE (a+b)aa(a+b) to equivalent NFA using Thompson's construction.
24. Prove regular languages are closed under intersection using construction.
25. Give example of a non-regular language and justify using pumping [Link] and solutions available
uAnswer Key with Steps for Chapter 2
---
Part 1: Multiple Choice Questions – Answers & Explanations
1. c) Both a and b – A language is regular iff it can be described by a regular expression or accepted by an
FA.
2. a) φ, λ, and a ∈ Σ – These are the primitive (base) regular expressions.
3. c) r1 ∩ r2 – Intersection is not a basic regular expression operator (but regular languages are closed
under intersection).
4. b) { } – φ denotes the empty language.
5. b) {ε} – ε represents the string of length 0.
6. c) All strings over {a,b} – (a+b)* means any combination of a’s and b’s, including λ.
7. b) ε – εR = Rε = R.
8. b) ε – Ø* = {λ} = ε.
9. c) Both a and b – R⁺ = RR* = R*R.
10. b) R* – (R) = R*.
11. b) φ – φR = Rφ = φ.
12. a) R + R = R – Idempotent law for union.
13. b) Solve equations of the form R = Q + RP – Arden’s theorem solves R = Q + RP to R = QP*.
14. c) Both a and b – Regular sets are closed under complement and intersection.
15. a) Always regular – Regular languages are closed under reversal.
16. a) ε = ε* – ε* = {λ} = ε.
17. d) Both a and b – Both distributive laws hold: L(M+N)=LM+LN and (M+N)L=ML+NL.
18. b) (ab) – (a+b)* = (ab), not equal to ab*.
19. a) Thompson's Construction – Standard method to build ε-NFA from RE.
20. b) Build NFA with ε-moves from RE – Step 1 of Thompson’s construction.
21. b) Two states – Start state and final state connected by ‘a’.
22. b) 3 states – Start → a → state → b → final.
23. a) ε-transitions – (a+b)* is built with ε-transitions for looping.
24. b) Remove ε-transitions – Step 2 after building ε-NFA.
25. a) A → xB or A → x – Definition of right-linear grammar.
26. a) A → Bx or A → x – Definition of left-linear grammar.
27. b) Regular – A grammar is regular if it is right-linear or left-linear.
28. a) (ab)*a – S → abS gives (ab)*, then S → a gives final a.
29. d) Not necessarily regular – If a grammar mixes both types, it may not be regular.
30. b) Prove a language is not regular – Pumping lemma is a necessary condition for regularity; used to
show non-regularity.
31. a) |w| ≥ c – We choose w long enough to exceed the pumping length c.
32. b) |y| > 0 – y must be non-empty to pump.
33. a) y is in the first c symbols – Ensures y is within the first c characters of w.
34. b) For some k, xy^kz ∉ L – We find a k such that pumped string leaves the language.
35. b) a^n b^n – We choose w such that it is in L and |w| ≥ n.
36. b) a^{p+2q+r} b^n – For k=2, xy²z = a^p a^{2q} a^r b^n = a^{p+2q+r} b^n.
37. c) {a^n b^n | n ≥ 0} – This is context-free, not regular.
38. d) All of these – Regular languages are closed under union, intersection, complement, etc.
39. a) Strings with exactly one 1 – 010: any number of 0’s, one 1, any number of 0’s.
40. d) Arden's theorem on equations – State equations solved using Arden’s theorem give the RE.
41. a) 0* – By Arden’s theorem: q1 = q10 + ε ⇒ q1 = ε0* = 0*.
42. a) R = QP* – Arden’s theorem solution.
43. a) All strings ending with 0 – (0+1)*0: any binary string ending with 0.
44. b) S → aS | b – Right-linear grammar (regular).
45. a) a*b – S → aS gives a*, then S → b gives final b.
46. a) Number of states in FA – c is the pumping length = number of states in a minimal DFA.
47. c) L can be finite or infinite – Regular languages may be finite or infinite.
48. d) (ab) – (a+b) = (ab)*.
49. a) NFA – After ε-removal, we get an NFA without ε-transitions.
50. d) Both a and c – Non-regular languages cannot be accepted by FA; may be accepted by PDA.
---
Part 2: Fill in the Blanks – Answers
1. finite automaton (FA)
2. **union (+) **
3. empty
4. ε
5. union of L(r1) and L(r2)
6. r*
7. Ø
8. ε
9. ε
10. not
11. >
12. c
13. not
14. complement
15. ε-NFA
16. ε
17. right-linear
18. Bx
19. regular
20. Q + RP
21. QP*
22. 0
23. equations
---
Part 3: Workout Problems – Solutions with Steps
1. RE for strings over {a,b} ending with 'aa'.
Answer: (a+b)*aa
Steps: Any string over {a,b}, then 'aa' at the end.
2. RE for strings over {0,1} containing substring '101'.
Answer: (0+1)101(0+1)
Steps: Any binary string, then substring 101, then any binary string.
3. RE for strings over {a,b} with odd length.
Answer: (a+b)((a+b)(a+b))*
Steps: One symbol, then pairs of symbols repeated.
4. Convert (a+b)*ab to English.
Answer: All strings over {a,b} that end with "ab".
Steps: Any string, then 'ab'.
5. Convert 01(0+1) to English.
Answer: All binary strings that start with zero or more 0’s, then at least one 1, then any binary string.
Steps: Actually simpler: strings with at least one 1, possibly preceded by 0’s.
6. L(01) for Σ={0,1}.
Answer: {0ᵐ1ⁿ | m,n ≥ 0}
Steps: Any number of 0’s followed by any number of 1’s.
7. L((ab)*) for Σ={a,b}.
Answer: {λ, ab, abab, ababab, …}
Steps: Even-length strings of alternating ab.
8. Simplify (a+b)*.
Answer: (a+b)*
Steps: (a+b)* = (ab)* = (a+b)*.
9. Simplify aa.
Answer: a*
Steps: a* a* = a* (since a* contains all strings of a’s, concatenating two gives same set).
10. Verify R + R = R.
Answer: L(R) ∪ L(R) = L(R) by set idempotence.
Steps: Union of a set with itself is itself.
11. Solve R = aR + b using Arden’s theorem.
Answer: R = ab
Steps: R = aR + b ⇒ R = b + aR ⇒ R = ab.
12. ε-NFA for 'a'.
Answer: Two states: q0 (start) →a→ q1 (final).
Steps: No ε-transitions needed.
13. ε-NFA for 'ab'.
Answer: Three states: q0 →a→ q1 →b→ q2 (final).
Steps: Linear chain.
14. ε-NFA for 'a+b'.
Answer:
q0 (start) → ε → q1 →a→ q2 (final)
q0 → ε → q3 →b→ q4 (final)
Merge q2 and q4 into one final state.
Steps: Parallel branches for a and b.
15. ε-NFA for 'a*'.
Answer:
q0 (start, final) → ε → q1 →a→ q2 → ε → q1.
Also q0 → ε → q2 to skip loop.
Steps: Loop for repetition, ε to skip.
16. Convert ε-NFA from Q15 to NFA.
Answer: Remove ε:
q0 on a goes to q2, q2 on a goes to q2.
q0 and q2 are final.
Steps: ε-closure and transition computation.
17. Right-linear grammar for a*b.
Answer: S → aS | b
Steps: a* from S → aS, then b to end.
18. Left-linear grammar for ab*.
Answer: S → Sb | a
Steps: b* from S → Sb, start with a.
19. Is S → aS | Sb | ab regular?
Answer: No.
Steps: Mixes right-linear (aS) and left-linear (Sb) → not regular.
20. Show L = {ww | w ∈ {a,b}*} is not regular.
Answer: Choose w = aⁿb aⁿb. Then y must be in first aⁿ part, pumping breaks symmetry.
Steps: Use pumping lemma; pumped string will not be of form ww.
21. Show L = {a^p | p is prime} is not regular.
Answer: Choose w = a^p where p is prime > c. Pumping y of length k gives length p + (k-1)|y|, which may
not be prime.
Steps: For some k, length becomes composite ⇒ not in L.
22. FA to RE.
Answer: RE = (0+1)0
Steps:
q0 = q00 + q11 + ε
q1 = q01 + q10
Solve: q0 = 0 (from Arden), q1 = 01(0+1)? Actually simpler: FA accepts strings ending with 0 ⇒ RE =
(0+1)*0.
23. RE (a+b)aa(a+b) to NFA using Thompson.
Answer:
Build (a+b): ε-NFA with loop for a,b.
Concatenate with aa: chain a→a.
Concatenate with (a+b): another loop.
Steps: Connect components with ε-transitions.
24. Prove closure under intersection.
Answer: Given DFAs M1, M2 for L1, L2, construct product DFA M with states Q1×Q2, δ((q1,q2),a) =
(δ1(q1,a),δ2(q2,a)), F = F1×F2. Then L(M) = L1 ∩ L2.
Steps: Cross-product construction.
25. Example of non-regular language.
Answer: L = {0ⁿ1ⁿ | n ≥ 0}.
Justification: Choose w = 0ᶜ1ᶜ. y must be within first c symbols (all 0’s). Pumping y changes number of 0’s
but not 1’s ⇒ string leaves L.
Steps: Standard pumping lemma [Link] request.