Self-Assessment Quiz: Automata and Formal Languages

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Throughout, $\Sigma = \{0,1\}$ unless stated otherwise, and $\varepsilon$ is the empty string.

Question 1

A language over an alphabet $\Sigma$ is:

A) a single string over $\Sigma$ B) any subset of $\Sigma^{*}$ C) the set $\Sigma$ itself D) a finite set of symbols

Question 2

Which of these is true about $\Sigma^{*}$ for $\Sigma = \{0,1\}$?

A) it is finite, with $2^{n}$ elements for inputs of length $n$ B) it contains every finite binary string, including $\varepsilon$, and is infinite C) it excludes the empty string D) it equals the language $L_{\text{even}}$

Question 3

In the DFA 5-tuple $(Q, \Sigma, \delta, q_0, F)$, the requirement that makes it deterministic is that $\delta$:

A) returns a set of states B) is defined only on accepting states C) maps each (state, symbol) pair to exactly one next state D) may use $\varepsilon$-transitions

Question 4

A DFA accepts a string $w$ exactly when:

A) some path on $w$ ends in an accepting state B) every path on $w$ ends in an accepting state C) the unique run on $w$ ends in a state of $F$ D) $w$ is the empty string

Question 5

The transition function of an NFA has the type:

A) $\delta\colon Q \times \Sigma \to Q$ B) $\delta\colon Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$ C) $\delta\colon \mathcal{P}(Q) \times \Sigma \to Q$ D) $\delta\colon Q \to \Sigma$

Question 6

An NFA accepts a string $w$ if:

A) every branch of computation ends in an accepting state B) there exists at least one branch ending in an accepting state C) the empty set of states is reached D) it has no $\varepsilon$-transitions

Question 7

The subset construction proves that:

A) every DFA can be made smaller B) NFAs recognize strictly more languages than DFAs C) every NFA has an equivalent DFA, so NFAs and DFAs recognize the same class of languages D) regular expressions are more powerful than NFAs

Question 8

An NFA has $6$ states. The largest number of states its subset-construction DFA could have is:

A) $6$ B) $12$ C) $36$ D) $64$

Question 9 (True/False, justify)

True or false: If an NFA has both an accepting path and a rejecting path on the same string $w$, then the NFA rejects $w$. Justify in one sentence.

Question 10

By Kleene's theorem, a language is regular if and only if it is:

A) finite B) recognized by some finite automaton C) recognized by a pushdown automaton D) context-sensitive

Question 11

In Thompson's construction, the $\varepsilon$-transitions are used primarily to implement:

A) the base symbol $a$ B) union and Kleene star (choice and looping), plus gluing for concatenation C) the dead state D) determinization

Question 12

Which regular expression denotes "binary strings that start with 1 and end with 0"?

A) $0(0\mid 1)^{*}1$ B) $1(0\mid 1)^{*}0$ C) $(0\mid 1)^{*}10$ D) $1^{*}0^{*}$

Question 13 (True/False, justify)

True or false: $L(\emptyset^{*}) = \emptyset$. Justify in one sentence using the definition of Kleene star.

Question 14

The pumping lemma states that if $L$ is regular with pumping length $p$, then every $s \in L$ with $\lvert s\rvert \ge p$ can be written $s = xyz$ where:

A) $\lvert x\rvert > 0$, $\lvert yz\rvert \le p$, and $x^{i}yz \in L$ for all $i$ B) $\lvert y\rvert > 0$, $\lvert xy\rvert \le p$, and $xy^{i}z \in L$ for all $i \ge 0$ C) $\lvert z\rvert > 0$, $\lvert xyz\rvert \le p$, and $xyz^{i} \in L$ for all $i$ D) $y = \varepsilon$ and $xz \in L$

Question 15

In a pumping-lemma proof of non-regularity, you (the prover) get to choose:

A) the pumping length $p$ and the split $x, y, z$ B) the string $s$ (depending on $p$) and the pumping exponent $i$ C) only the pumping length $p$ D) nothing — the adversary chooses everything

Question 16

Why is the condition $\lvert xy\rvert \le p$ the "workhorse" when proving $\{0^{n}1^{n} \mid n \ge 0\}$ is not regular?

A) it forces $y$ to be the empty string B) combined with "$s$ starts with $p$ zeros," it forces $y$ to lie entirely in the block of $0$s C) it lets the prover pick the split D) it makes $s$ shorter than $p$

Question 17

Which language is not regular?

A) strings with an even number of $1$s B) strings ending in 01 C) $\{0^{n}1^{n} \mid n \ge 0\}$ D) $0^{*}1^{*}$

Question 18

In the Chomsky hierarchy, the machine that recognizes the context-free languages is the:

A) finite automaton B) pushdown automaton (a finite automaton plus a stack) C) linear-bounded automaton D) Turing machine

Question 19 (Short answer)

Name the machine that recognizes each class: (a) regular, (b) context-free, (c) recursively enumerable.

Question 20 (Short answer)

In a compiler, which phase is "regular" and which is "context-free," and in one clause say why the regular phase cannot do the context-free phase's job.

Answer Key

Topics to review by question