AMCAT Automata and Formal Languages Flashcards

Which of the following is the correct regular expression for the language of all binary strings containing at least one '1'?

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.

An epsilon-NFA (NFA with epsilon transitions) is:

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.

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

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.

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?

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.

The Myhill-Nerode theorem is used to:

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.

Which of the following operations on context-free languages does NOT always produce a context-free language?

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.