AMCAT Automata and Formal Languages 2

Question 1

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

Accepted Answer

(0|1)*1(0|1)*

Answer

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:

Accepted Answer

Equivalent in power to a standard NFA and DFA

Answer

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

Accepted Answer

Grammar C

Answer

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?

Accepted Answer

Non-deterministic Pushdown Automaton

Answer

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:

Accepted Answer

Minimize a DFA by finding the minimum number of states

Answer

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.

AMCAT Practice Test

AMCAT Practice Test

AMCAT Automata and Formal Languages 2