COS3701 Theoretical Computer Science III Exam
2026 | Practice Questions with Answers & Detailed
Explanations | UNISA | Latest Update | Guaranteed
Pass
📚 Section 1: Regular Languages & Finite Automata (Questions 1–40)
1. A deterministic finite automaton (DFA) is defined as a 5-tuple (Q, Σ, δ, q₀, F). What
does δ represent?
A) The set of accepting states
B) The transition function
C) The start state
D) The input alphabet
Answer: B
Explanation: In the formal definition of a DFA, δ: Q × Σ → Q is the transition function. It
maps a state and an input symbol to the next state. Q is the set of states, Σ is the input
alphabet, q₀ is the start state, and F is the set of accepting states.
, 2. Which of the following languages is accepted by a DFA with a single accepting
state that loops on all inputs?
A) The empty language
B) The language of all strings over the alphabet
C) The language containing only the empty string
D) A language that accepts no strings
Answer: B
Explanation: If a DFA has a single accepting state that loops on all inputs, it accepts all
strings over the alphabet. The language L = Σ is regular and is accepted by such a DFA.
The empty language would require no accepting states or unreachable accepting states.*
3. The language {aⁿbⁿ | n ≥ 0} is:
A) Regular
B) Context-free but not regular
C) Context-sensitive but not context-free
D) Recursively enumerable
Answer: B
Explanation: The language {aⁿbⁿ | n ≥ 0} is context-free but not regular. It can be generated
by the grammar S → aSb | ε and accepted by a pushdown automaton. However, it cannot
be recognized by any finite automaton because it requires counting and matching the
number of a's and b's, which a finite automaton cannot do.
, 4. The pumping lemma for regular languages states that for every regular language L,
there exists a constant n such that for every string w in L with |w| ≥ n, w can be
divided into xyz such that:
A) |y| = 0 and xy^iz ∈ L for all i ≥ 0
B) |y| > 0, |xy| ≤ n, and xy^iz ∈ L for all i ≥ 0
C) |x| > 0, |y| > 0, and xyz ∈ L
D) |xy| ≥ n and |y| = 0
Answer: B
Explanation: The pumping lemma states that if L is regular, there exists a pumping length p
such that any string w ∈ L with |w| ≥ p can be written as w = xyz where |y| > 0, |xy| ≤ p, and
for all i ≥ 0, xy^iz ∈ L. This lemma is used to prove that certain languages are not regular.
5. A non-deterministic finite automaton (NFA) differs from a DFA in that:
A) An NFA has multiple accepting states
B) An NFA can have ε-transitions
C) An NFA can have multiple possible transitions from a state on the same input symbol
D) An NFA cannot have more states than a DFA
Answer: C
Explanation: The key difference is that in an NFA, δ: Q × (Σ ∪ {ε}) → 2^Q, meaning from a
state on a given input symbol, there can be multiple possible next states (a set of states).
This non-determinism is the defining characteristic of NFAs. While NFAs may have ε-
transitions, this is not always required.
, 6. Which of the following statements is true regarding the equivalence of DFAs and
NFAs?
A) Every NFA can be converted to an equivalent DFA, but the DFA may have exponentially
more states
B) NFAs are more powerful than DFAs in terms of the languages they can recognize
C) DFAs cannot accept languages that NFAs accept
D) NFAs and DFAs recognize different classes of languages
Answer: A
Explanation: NFAs and DFAs are equivalent in expressive power; they recognize exactly
the same class of languages (regular languages). However, converting an NFA to a DFA
may result in an exponential increase in the number of states (subset construction). This
demonstrates that NFAs can be more concise representations of regular languages.
7. A regular expression for the language of strings over {0,1} that contain at least one
1 is:
A) 0*1*0*
B) (0 ∪ 1)1(0 ∪ 1)
C) 01(0 ∪ 1)
D) (0 ∪ 1)*
2026 | Practice Questions with Answers & Detailed
Explanations | UNISA | Latest Update | Guaranteed
Pass
📚 Section 1: Regular Languages & Finite Automata (Questions 1–40)
1. A deterministic finite automaton (DFA) is defined as a 5-tuple (Q, Σ, δ, q₀, F). What
does δ represent?
A) The set of accepting states
B) The transition function
C) The start state
D) The input alphabet
Answer: B
Explanation: In the formal definition of a DFA, δ: Q × Σ → Q is the transition function. It
maps a state and an input symbol to the next state. Q is the set of states, Σ is the input
alphabet, q₀ is the start state, and F is the set of accepting states.
, 2. Which of the following languages is accepted by a DFA with a single accepting
state that loops on all inputs?
A) The empty language
B) The language of all strings over the alphabet
C) The language containing only the empty string
D) A language that accepts no strings
Answer: B
Explanation: If a DFA has a single accepting state that loops on all inputs, it accepts all
strings over the alphabet. The language L = Σ is regular and is accepted by such a DFA.
The empty language would require no accepting states or unreachable accepting states.*
3. The language {aⁿbⁿ | n ≥ 0} is:
A) Regular
B) Context-free but not regular
C) Context-sensitive but not context-free
D) Recursively enumerable
Answer: B
Explanation: The language {aⁿbⁿ | n ≥ 0} is context-free but not regular. It can be generated
by the grammar S → aSb | ε and accepted by a pushdown automaton. However, it cannot
be recognized by any finite automaton because it requires counting and matching the
number of a's and b's, which a finite automaton cannot do.
, 4. The pumping lemma for regular languages states that for every regular language L,
there exists a constant n such that for every string w in L with |w| ≥ n, w can be
divided into xyz such that:
A) |y| = 0 and xy^iz ∈ L for all i ≥ 0
B) |y| > 0, |xy| ≤ n, and xy^iz ∈ L for all i ≥ 0
C) |x| > 0, |y| > 0, and xyz ∈ L
D) |xy| ≥ n and |y| = 0
Answer: B
Explanation: The pumping lemma states that if L is regular, there exists a pumping length p
such that any string w ∈ L with |w| ≥ p can be written as w = xyz where |y| > 0, |xy| ≤ p, and
for all i ≥ 0, xy^iz ∈ L. This lemma is used to prove that certain languages are not regular.
5. A non-deterministic finite automaton (NFA) differs from a DFA in that:
A) An NFA has multiple accepting states
B) An NFA can have ε-transitions
C) An NFA can have multiple possible transitions from a state on the same input symbol
D) An NFA cannot have more states than a DFA
Answer: C
Explanation: The key difference is that in an NFA, δ: Q × (Σ ∪ {ε}) → 2^Q, meaning from a
state on a given input symbol, there can be multiple possible next states (a set of states).
This non-determinism is the defining characteristic of NFAs. While NFAs may have ε-
transitions, this is not always required.
, 6. Which of the following statements is true regarding the equivalence of DFAs and
NFAs?
A) Every NFA can be converted to an equivalent DFA, but the DFA may have exponentially
more states
B) NFAs are more powerful than DFAs in terms of the languages they can recognize
C) DFAs cannot accept languages that NFAs accept
D) NFAs and DFAs recognize different classes of languages
Answer: A
Explanation: NFAs and DFAs are equivalent in expressive power; they recognize exactly
the same class of languages (regular languages). However, converting an NFA to a DFA
may result in an exponential increase in the number of states (subset construction). This
demonstrates that NFAs can be more concise representations of regular languages.
7. A regular expression for the language of strings over {0,1} that contain at least one
1 is:
A) 0*1*0*
B) (0 ∪ 1)1(0 ∪ 1)
C) 01(0 ∪ 1)
D) (0 ∪ 1)*
