Theory of Computation · Quiz 1 · May 2026

**1. Check the condition 'every string in \( L \) contains an odd number of `1`s':** - **Option A (\( 0^* \)):** Strings in \( 0^* \) contain zero `1`s (and 0 is even, not odd). - **Option B (\( 0^* 1 0^* 1 0^* 1 0^* \)):** Every string generated by this regular expression contains **exactly three `1`s**. Since 3 is an odd number and the language is regular, it is accepted by a DFA and every string in it has an odd number of `1`s. - **Option C (\( (0+1)^* \)):** Contains strings with an even number of `1`s (such as `11`). - **Option D (\( 0^* 1 0^* 1 0^* \)):** Every string contains exactly two `1`s (even). **Answer: B — \( 0^* 1 0^* 1 0^* 1 0^* \).** A: **Incorrect:** Strings in \( 0^* \) have 0 occurrences of `1`, which is even. B: **Correct:** Every string in \( 0^* 1 0^* 1 0^* 1 0^* \) contains exactly three `1`s (an odd number) and is regular. C: **Incorrect:** \( (0+1)^* \) includes strings with an even number of `1`s. D: **Incorrect:** Every string in \( 0^* 1 0^* 1 0^* \) has exactly two `1`s, which is even.

**1. Count total subsets vs. non-accepting subsets:** - An NFA with \( n \) states has \( 2^n \) total subsets in the subset construction. - Let the single accepting state be \( q_f \) (\( |F| = 1 \)). - A DFA state (subset \( S \subseteq Q \)) is **non-accepting** if and only if \( q_f \notin S \), meaning \( S \) is a subset of the remaining \( n - 1 \) non-accepting NFA states. **2. Conclude:** The number of subsets of \( n - 1 \) elements is: \[ 2^{n-1} \] **Answer: B — \( 2^{n-1} \).** A: **Incorrect:** \( 2^n \) is the total number of DFA states (accepting + non-accepting). B: **Correct:** Excluding the single accepting state from \( n \) states leaves \( 2^{n-1} \) non-accepting subsets. C: **Incorrect:** \( 2^n - 1 \) only excludes a single subset instead of all \( 2^{n-1} \) subsets containing the accepting state. D: **Incorrect:** \( n - 1 \) is the number of non-accepting NFA states, not DFA subsets.

**1. Check each language for regularity:** - **Option A (\( \{0^n 1^m \mid n, m \ge 0\} \)):** Regular (\( 0^* 1^* \)), since \( n \) and \( m \) are independent. - **Option B (\( \{w \in \{0,1\}^* \mid w \text{ ends with } 01\} \)):** Regular (\( (0+1)^* 01 \)). - **Option C (\( \{0^n 1^n 0^n \mid n \ge 0\} \)):** Requires matching the counts of three blocks of symbols to the same unbounded integer \( n \). It is **not regular** (in fact, not even context-free). - **Option D (\( \{w \in \{0,1\}^* \mid |w| \text{ is even}\} \)):** Regular (\( ((0+1)(0+1))^* \)). **Answer: C — \( \{0^n 1^n 0^n \mid n \ge 0\} \).** A: **Incorrect:** \( 0^* 1^* \) is regular because \( n \) and \( m \) are unconstrained. B: **Incorrect:** Recognized by a 3-state DFA for \( (0+1)^* 01 \). C: **Correct:** \( \{0^n 1^n 0^n \mid n \ge 0\} \) requires unbounded counting across three blocks and is not regular. D: **Incorrect:** Recognized by a 2-state DFA tracking length parity.

**1. Read the production rules from the parse tree:** - The root \( S \) has three children from left to right: \( a \), \( S \), and \( b \) (production \( S \to aSb \)). - The middle child \( S \) also expands to \( a \), \( S \), and \( b \) (\( S \to aSb \)). - The lowest \( S \) node expands to \( \varepsilon \) (\( S \to \varepsilon \)), deriving \( aabb \). Thus, the grammar is \( S \to aSb \mid \varepsilon \) (**Option A**). **Answer: A — \( S \to aSb \mid \varepsilon \).** A: **Correct:** Each internal \( S \) expands to \( aSb \) and the bottom \( S \) expands to \( \varepsilon \). B: **Incorrect:** \( S \to abS \mid \varepsilon \) would derive `abab` instead of `aabb`. C: **Incorrect:** \( S \to SS \mid ab \) has no \( S \to aSb \) or \( \varepsilon \) rule. D: **Incorrect:** \( S \to aS \mid bS \mid \varepsilon \) only branches into two children per node.

**1. Trace the DFA from start state \( q_0 \) to accepting state \( q_2 \):** - State \( q_0 \) loops on \( b \) (\( b^* \)) and transitions to \( q_1 \) on \( a \). - State \( q_1 \) loops on \( a \) (\( a^* \)) and transitions to accepting state \( q_2 \) on \( b \). - State \( q_2 \) loops on \( a, b \) (\( (a + b)^* \)). **2. Combine via state elimination:** \[ b^* a a^* b (a + b)^* \] (which represents all strings over \( \{a,b\} \) containing the substring \( ab \)). **Answer: B — \( b^* a a^* b (a+b)^* \).** A: **Incorrect:** Omits the self-loop \( a^* \) on state \( q_1 \). B: **Correct:** Directly captures \( q_0 \)'s \( b^* \) loop, the \( a \) transition, \( q_1 \)'s \( a^* \) loop, the \( b \) transition, and \( q_2 \)'s \( (a+b)^* \) loop. C: **Incorrect:** Swaps the loop symbols on \( q_0 \) and \( q_1 \). D: **Incorrect:** Omits the trailing \( (a+b)^* \) loop on the accepting state \( q_2 \).

**1. Check which regular expressions guarantee at least two \( 1 \)'s in every generated string:** - **Option A (\( (0+1)^* 1 (0+1)^* 1 (0+1)^* \)):** Explicitly requires two mandatory `1`s separated/surrounded by arbitrary binary strings. Every generated string has at least two `1`s. **True.** - **Option B (\( (0+1)^* 1 (0+1)^* \)):** Only requires one mandatory `1`, so it generates `1` (which has only one `1`). **False.** - **Option C (\( 0^* 1 0^* 1 (0+1)^* \)):** Explicitly requires a first `1` and a second `1`, followed by any suffix. Every generated string has at least two `1`s. **True.** - **Option D (\( 1^* 0^* 1^* \)):** Since both \( 1^* \) can choose zero repetitions, it generates \( \varepsilon \), `0`, `1` (fewer than two `1`s). **False.** **Answer: A and C.** A: **Correct:** Contains two explicit `1`s outside the Kleene stars, ensuring at least two `1`s in every string. B: **Incorrect:** Generates the string `1`, which has only a single `1`. C: **Correct:** Matches the first two `1`s explicitly via \( 0^* 1 0^* 1 \) and then allows any suffix \( (0+1)^* \). D: **Incorrect:** Because \( 1^* \) can match \( \varepsilon \), it generates strings with zero or one `1`.

**1. Test each grammar for ambiguity:** - **Option A (\( S \to S + S \mid a \)):** Ambiguous! The string `a + a + a` has two distinct parse trees: \( (a + a) + a \) and \( a + (a + a) \). - **Option B (\( S \to aSb \mid \varepsilon \)):** Unambiguous; each step adds one `a` and one `b`, so `a^n b^n` has a unique derivation of length \( n + 1 \). - **Option C (\( S \to SS \mid a \)):** Ambiguous! The string `aaa` has two distinct parse trees: \( (aa)a \) and \( a(aa) \). - **Option D (\( S \to aS \mid b \)):** Unambiguous right-linear grammar; every string \( a^n b \) has a unique derivation. **Answer: A and C.** A: **Correct:** \( S \to S + S \mid a \) is ambiguous (e.g., `a + a + a` has two parse trees). B: **Incorrect:** \( S \to aSb \mid \varepsilon \) is completely deterministic and unambiguous. C: **Correct:** \( S \to SS \mid a \) is ambiguous (e.g., `aaa` has two parse trees). D: **Incorrect:** \( S \to aS \mid b \) is a deterministic right-linear grammar.

**1. Analyze \( L_1 = \{a^n b^n \mid n \ge 0\} \) (CFL) and \( L_2 = \{a^n b^{2n} \mid n \ge 0\} \) (CFL):** - **Option A (\( L_1 \cup L_2 \) is context-free):** Context-free languages are closed under union, so \( L_1 \cup L_2 \) is a CFL. **True.** - **Option B (\( L_1 \cap L_2 \) is not context-free):** Let's compute \( L_1 \cap L_2 \) explicitly! A string \( a^n b^m \) is in \( L_1 \cap L_2 \) iff \( m = n \) AND \( m = 2n \), which implies \( n = 2n \implies n = 0 \). Thus, \( L_1 \cap L_2 = \{\varepsilon\} \)! - **Option C (\( L_1 \cap L_2 = \{\varepsilon\} \) / is regular):** Since \( L_1 \cap L_2 = \{\varepsilon\} \) is a finite set containing only the empty string, it is regular (and context-free). **True.** **Answer: A and C.** A: **Correct:** Context-free languages are closed under union. B: **Incorrect:** \( L_1 \cap L_2 = \{\varepsilon\} \) is finite, hence both regular and context-free. C: **Correct:** \( n = 2n \) holds only for \( n = 0 \), so \( L_1 \cap L_2 = \{\varepsilon\} \) (which is regular). D: **Incorrect:** Neither \( L_1 \) nor \( L_2 \) is regular.

**1. Trace the given DFA over \( \Sigma = \{0, 1\} \):** From the DFA diagram, a string is accepted if it reaches the accepting state after reading three consecutive `1`s (or ends with `111`). - **Option A (`111`):** Reaches the accepting state. **Accepted.** - **Option B (`101`):** Reset by the `0` in the middle; does not reach the accepting state. **Rejected.** - **Option C (`0111`):** After `0`, reads `111` to reach the accepting state. **Accepted.** - **Option D (`110`):** Reset by the final `0`. **Rejected.** **Answer: A and C.** A: **Correct:** Reading `111` transitions directly from the start state to the accepting state. B: **Incorrect:** `101` does not contain three consecutive `1`s. C: **Correct:** Reading `0111` stays in the start state on `0` and then transitions to the accepting state on `111`. D: **Incorrect:** `110` resets on the final `0` before reaching the accepting state.

**1. Interpret the regular expression \( r = (0 + 1)^* 01 (0 + 1)^* \):** - \( (0 + 1)^* \) matches any binary prefix. - \( 01 \) matches the contiguous substring `01`. - \( (0 + 1)^* \) matches any binary suffix. Therefore, \( L(r) \) is the set of **all binary strings containing the substring `01`**. **Answer: B — All binary strings containing substring 01.** A: **Incorrect:** Strings ending in `01` are represented by \( (0+1)^* 01 \) without the trailing \( (0+1)^* \). B: **Correct:** \( (0+1)^* 01 (0+1)^* \) matches any binary string that contains `01` anywhere within it. C: **Incorrect:** The prefix and suffix \( (0+1)^* \) can contain additional occurrences of `01`. D: **Incorrect:** Strings beginning with `01` are represented by \( 01(0+1)^* \).

**1. Recall Chomsky Normal Form (CNF):** A CFG is in **Chomsky Normal Form** if every production is of the form: \[ A \to BC \quad \text{or} \quad A \to a \] (i.e., either exactly two non-terminals or a single terminal on the right-hand side). **2. Check the options:** - **Option A (\( S \to AB,\ A \to a,\ B \to b \)):** Every rule is either two variables (`AB`) or one terminal (`a`, `b`). **Valid CNF.** - **Option B (\( S \to aB \)):** Mixes a terminal and a non-terminal on the RHS. - **Option C (\( S \to ABC \)):** Has three non-terminals on the RHS. - **Option D (\( S \to A \)):** Is a unit production. **Answer: A — \( S \to AB,\ A \to a,\ B \to b \).** A: **Correct:** All productions are of the form \( A \to BC \) (`S -> AB`) or \( A \to a \) (`A -> a`, `B -> b`). B: **Incorrect:** Mixing a terminal and a variable (`aB`) violates CNF. C: **Incorrect:** Three variables (`ABC`) on the RHS violates CNF. D: **Incorrect:** Unit productions (`S -> A`) are not allowed in CNF.

**1. Recall the definition of Greibach Normal Form (GNF):** In Greibach Normal Form, every production rule has the form: \[ A \to a \alpha \] where \( a \in \Sigma \) is a single terminal symbol and \( \alpha \in V^* \) is a string of **zero or more variables (non-terminals)**. **Answer: B — Every production begins with a terminal followed by zero or more variables.** A: **Incorrect:** Every production in GNF must begin with a *terminal*, not a variable. B: **Correct:** In GNF, every right-hand side is of the form \( a V_1 V_2 \dots V_k \) (\( k \ge 0 \)). C: **Incorrect:** \( \varepsilon \)-productions are forbidden in GNF (except possibly \( S \to \varepsilon \) if \( S \) does not appear on any RHS). D: **Incorrect:** GNF allows any number (zero or more) of variables after the initial terminal; two variables is a CNF rule.

**1. Recall the Infiniteness-Testing Theorem for DFAs:** For a DFA with \( n \) states, the language \( L(M) \) is infinite if and only if the DFA accepts at least one string \( w \) whose length satisfies: \[ n \le |w| < 2n \] **2. Apply to \( n = 8 \):** The minimum length in the range \( 8 \le |w| < 16 \) is **8**. **Answer: 8.**

**1. Write out the leftmost derivation of `aaabbb` using \( S \to aSb \mid \varepsilon \):** 1. \( S \Rightarrow aSb \) (1st application) 2. \( \Rightarrow aaSbb \) (2nd application) 3. \( \Rightarrow aaaSbbb \) (3rd application) 4. \( \Rightarrow aaabbb \) (4th application, using \( S \to \varepsilon \)) Thus, **4** production applications are required. **Answer: 4.**

**1. Set up the pumped string \( x y^i z \):** - Language: \( L = \{a^n b^n \mid n \ge 0\} \), pumping length \( p = 5 \). - Chosen string: \( w = a^5 b^5 \) (which initially has \( 5 \) occurrences of \( a \)). - Since \( |xy| \le 5 \), \( y \) consists entirely of \( a \)'s, and we are given \( |y| = 2 \) (i.e., \( y = aa \)) and \( x = aaa \). **2. Count the number of \( a \)'s in \( x y^i z \) for \( i = 3 \):** \[ \#a(x y^3 z) = |x| + 3|y| = (5 - 2) + 3(2) = 3 + 6 = 9 \] **Answer: 9.**

**1. Evaluate each statement on DFA minimization:** - **Option A:** By definition of Myhill–Nerode state equivalence, two states \( p \) and \( q \) are equivalent if and only if for every continuation string \( w \in \Sigma^* \), \( \hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F \) (they cannot be distinguished by any continuation string). **True.** - **Option B:** False! If one state is accepting (\( p \in F \)) and the other is non-accepting (\( q \notin F \)), they are immediately distinguished by the empty string \( w = \varepsilon \), even if their outgoing transitions on non-empty symbols are identical. - **Option C:** By the Myhill–Nerode theorem, the minimal DFA for any regular language is unique up to state renaming (isomorphism). **True.** - **Option D:** False; in an already minimal DFA, no two distinct states can be merged. **Answer: A and C.** A: **Correct:** Two states are equivalent iff no continuation string \( w \) leads one to an accepting state and the other to a non-accepting state. B: **Incorrect:** An accepting state and a non-accepting state with identical outgoing transitions are still distinguishable by \( \varepsilon \). C: **Correct:** The Myhill–Nerode theorem guarantees that the minimal DFA is unique up to isomorphism. D: **Incorrect:** States in a minimal DFA are pairwise distinguishable and cannot be merged.

**1. Recall the closure properties of Context-Free Languages (CFLs):** - **Union (A):** Closed! If \( G_1 \) and \( G_2 \) have start symbols \( S_1 \) and \( S_2 \), adding \( S \to S_1 \mid S_2 \) generates \( L(G_1) \cup L(G_2) \). - **Intersection (B):** NOT closed (e.g., \( \{a^n b^n c^m\} \cap \{a^m b^n c^n\} = \{a^n b^n c^n\} \), which is not context-free). - **Intersection with Regular Languages (C):** Closed! Taking the product construction of a PDA with a DFA yields a PDA. - **Complementation (D):** NOT closed (if CFLs were closed under complementation and union, they would be closed under intersection by De Morgan's laws). **Answer: A and C.** A: **Correct:** CFLs are closed under union. B: **Incorrect:** The intersection of two CFLs can be non-context-free (such as \( \{a^n b^n c^n\} \)). C: **Correct:** The intersection of a CFL with a regular language is always a CFL. D: **Incorrect:** CFLs are not closed under complementation.

**1. Analyze the given NFA:** From the NFA diagram: - State \( q_0 \) loops on \( a, b \) and transitions on \( b \) to \( q_1 \), which transitions on \( a \) to the accepting state \( q_2 \) (accepting all strings ending in `ba`). - **Option A (`bba`):** Ends with `ba` \( \implies \) **Accepted.** - **Option B (`aaaba`):** Ends with `ba` \( \implies \) **Accepted.** - **Option C (`aab`):** Ends with `ab`, not `ba` \( \implies \) **Rejected.** - **Option D (`abaab`):** Ends with `ab`, not `ba` \( \implies \) **Rejected.** **Answer: A and B.** A: **Correct:** `bba` ends with `ba` and has the accepting path \( q_0 \xrightarrow{b} q_0 \xrightarrow{b} q_1 \xrightarrow{a} q_2 \). B: **Correct:** `aaaba` ends with `ba` and reaches the accepting state \( q_2 \). C: **Incorrect:** `aab` ends in `b`, so it cannot take the final \( a \)-transition into \( q_2 \). D: **Incorrect:** `abaab` ends in `b` and does not reach \( q_2 \) at the end of the input.

**1. Trace only `0`-transitions in the given DFA:** Since the string cannot contain the symbol `1`, we only follow transitions labeled `0` starting from \( q_0 \): \[ q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \in F \] The shortest `0`-only path from the start state \( q_0 \) to the accepting state \( q_3 \) uses three `0`s (`000`), which has length **3**. **Answer: 3.**