AMCAT Automata and Formal Languages 1 — Questions and Answers
Question 1: Which of the following languages can be recognized by a Deterministic Finite Automaton (DFA)?
- The set of all strings over {a, b} with an equal number of a's and b's
- The set of all strings over {a, b} that end with 'ab' (Correct answer)
- The set of all palindromes over {a, b}
- The set of all strings of the form a^n b^n where n >= 0
Correct answer: The set of all strings over {a, b} that end with 'ab'
A DFA can recognize regular languages. 'Strings ending with ab' is a regular language because a DFA only needs to track the last two characters seen. The other options require memory of unbounded counts or positions, making them non-regular (context-free or beyond).
Question 2: What is the minimum number of states required in a DFA that accepts all binary strings divisible by 3?
- 2
- 3 (Correct answer)
- 4
- 5
Correct answer: 3
A number can have remainder 0, 1, or 2 when divided by 3. A DFA with 3 states (one for each possible remainder) can track the remainder as it reads each binary digit. The state representing remainder 0 is the accepting state.
Question 3: Which of the following is NOT a property of regular languages?
- Closure under union
- Closure under intersection
- Closure under complementation
- Ability to express a^n b^n for arbitrary n (Correct answer)
Correct answer: Ability to express a^n b^n for arbitrary n
Regular languages are closed under union, intersection, and complementation (options A, B, C). However, the language {a^n b^n | n >= 0} is a classic context-free language that is NOT regular, as proven by the Pumping Lemma for regular languages.
Question 4: In the Chomsky hierarchy, which type of grammar generates context-free languages?
- Type 0
- Type 1
- Type 2 (Correct answer)
- Type 3
Correct answer: Type 2
The Chomsky hierarchy classifies grammars into four types: Type 0 (unrestricted/recursively enumerable), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). Context-free grammars (Type 2) have rules of the form A → α where A is a single non-terminal.
Question 5: A non-deterministic finite automaton (NFA) has 5 states. What is the maximum number of states in an equivalent DFA obtained by the subset construction method?
- 5
- 10
- 25
- 32 (Correct answer)
Correct answer: 32
The subset construction converts an NFA to a DFA where each DFA state represents a subset of NFA states. With 5 NFA states, the power set has 2^5 = 32 possible subsets, so the equivalent DFA can have at most 32 states.
Question 6: Which of the following is true about the Pumping Lemma for regular languages?
- It can be used to prove that a language IS regular
- It can be used to prove that a language is NOT regular (Correct answer)
- It applies only to context-free languages
- It states that all strings in a regular language can be pumped
Correct answer: It can be used to prove that a language is NOT regular
The Pumping Lemma for regular languages provides a necessary condition for regularity. If a language fails to satisfy the Pumping Lemma, it is provably NOT regular. However, satisfying the lemma does not guarantee regularity, so it cannot prove a language IS regular.
AMCAT Automata and Formal Languages 1
Which of the following languages can be recognized by a Deterministic Finite Automaton (DFA)?