AMCAT Automata and Formal Languages 2 — Questions and Answers
Question 1: Which of the following is the correct regular expression for the language of all binary strings containing at least one '1'?
- 0*10*
- 0*1(0|1)*
- (0|1)*1(0|1)* (Correct answer)
- 1(0|1)*
Correct answer: (0|1)*1(0|1)*
The expression (0|1)*1(0|1)* means: any number of 0s or 1s, followed by at least one 1, followed by any number of 0s or 1s. This correctly captures all binary strings with at least one 1. Option A restricts to exactly one 1; option B requires the first 1 to have only 0s before it at the start; option D requires the string to start with 1.
Question 2: An epsilon-NFA (NFA with epsilon transitions) is:
- More powerful than a standard NFA in terms of language recognition
- Equivalent in power to a standard NFA and DFA (Correct answer)
- More powerful than a DFA but less than a pushdown automaton
- Capable of recognizing context-free languages
Correct answer: Equivalent in power to a standard NFA and DFA
An epsilon-NFA, standard NFA, and DFA are all equivalent in computational power — they all recognize exactly the class of regular languages. Epsilon transitions provide convenience in design but do not add recognition capability. Any epsilon-NFA can be converted to an equivalent DFA.
Question 3: Which of the following grammars is ambiguous? A) S → aS | a B) S → aSb | ab C) S → SS | a D) S → aSa | bSb | a | b
- Grammar A
- Grammar B
- Grammar C (Correct answer)
- Grammar D
Correct answer: Grammar C
Grammar C (S → SS | a) is ambiguous because the string 'aaa' has two distinct parse trees: S → SS → aS → aSS → aaa (left derivation grouping) versus S → SS → SSS → aaa (different grouping). Grammars A and B produce unique parse trees for every string they generate.
Question 4: What type of automaton is needed to recognize the language L = {ww^R | w is in {a,b}*}, where w^R is the reverse of w?
- Deterministic Finite Automaton
- Non-deterministic Pushdown Automaton (Correct answer)
- Deterministic Pushdown Automaton
- Turing Machine
Correct answer: Non-deterministic Pushdown Automaton
L = {ww^R} is the language of even-length palindromes, which is a context-free language. It can be recognized by a non-deterministic pushdown automaton (NPDA) that pushes the first half onto the stack and matches with the second half. However, a DPDA cannot recognize it because there is no way to deterministically know when the middle of the string has been reached.
Question 5: The Myhill-Nerode theorem is used to:
- Convert an NFA to a DFA
- Minimize a DFA by finding the minimum number of states (Correct answer)
- Prove that a language is context-free
- Generate regular expressions from grammars
Correct answer: Minimize a DFA by finding the minimum number of states
The Myhill-Nerode theorem establishes a necessary and sufficient condition for a language to be regular, based on the number of equivalence classes of a right-invariant equivalence relation. It directly gives the minimum number of states needed in a DFA for that language.
Question 6: Which of the following operations on context-free languages does NOT always produce a context-free language?
- Union of two context-free languages
- Concatenation of two context-free languages
- Intersection of two context-free languages (Correct answer)
- Kleene star of a context-free language
Correct answer: Intersection of two context-free languages
Context-free languages are closed under union, concatenation, and Kleene star. However, they are NOT closed under intersection. A classic example: L1 = {a^n b^n c^m} and L2 = {a^m b^n c^n} are both context-free, but L1 ∩ L2 = {a^n b^n c^n} is not context-free.
AMCAT Automata and Formal Languages 2
Which of the following is the correct regular expression for the language of all binary strings containing at least one '1'?