Theory of Computation · Quiz 1 · Jan 2026

**1. Analyze the given DFA:** The DFA has start state \( q_0 \), intermediate states \( q_1, q_2 \), and a single accepting state \( q_3 \). Its transitions are: \[ \begin{array}{c|cc} \text{State} & a & b \\ \hline q_0 & q_1 & q_2 \\ q_1 & q_1 & q_3 \\ q_2 & q_3 & q_2 \\ *q_3 & q_1 & q_2 \end{array} \] **2. Determine the language recognized by each state:** - Any non-empty string ending in \( aa \) (or a single \( a \) after \( q_0 \) or \( q_3 \)) lands in \( q_1 \). - Any non-empty string ending in \( bb \) (or a single \( b \) after \( q_0 \) or \( q_3 \)) lands in \( q_2 \). - From \( q_1 \) (last symbol was \( a \)), reading \( b \) transitions to \( q_3 \) (last two symbols are \( ab \)). - From \( q_2 \) (last symbol was \( b \)), reading \( a \) transitions to \( q_3 \) (last two symbols are \( ba \)). - Thus, the DFA accepts a string of length at least 2 if and only if its last two symbols are different (i.e., the string ends with \( ab \) or \( ba \)). **3. Trace each option:** - Option A (\( \text{aaaabaa} \)): Ends with \( aa \), so it finishes in state \( q_1 \) (not accepted). - Option B (\( \text{babbbba} \)): Ends with \( ba \), so the transition on the final \( a \) goes from \( q_2 \) to \( q_3 \) (accepted). - Option C (\( \text{ababaab} \)): Ends with \( ab \), so the transition on the final \( b \) goes from \( q_1 \) to \( q_3 \) (accepted). - Option D (\( \text{baaabab} \)): Ends with \( ab \), so the transition on the final \( b \) goes from \( q_1 \) to \( q_3 \) (accepted). - Option E (\( \text{babaabb} \)): Ends with \( bb \), so it finishes in state \( q_2 \) (not accepted). **Answer: B, C, and D.** A: **Incorrect:** For `aaaabaa`, the last two symbols are `aa`, which leaves the DFA in non-accepting state \( q_1 \). B: **Correct:** For `babbbba`, reading `babbbb` leaves the DFA in \( q_2 \), and the final `a` transitions to the accepting state \( q_3 \). C: **Correct:** For `ababaab`, reading `ababaa` leaves the DFA in \( q_1 \), and the final `b` transitions to the accepting state \( q_3 \). D: **Correct:** For `baaabab`, reading `baaaba` leaves the DFA in \( q_1 \), and the final `b` transitions to the accepting state \( q_3 \). E: **Incorrect:** For `babaabb`, the last two symbols are `bb`, which leaves the DFA in non-accepting state \( q_2 \).

**1. Inspect the given expression grammar:** \[ \begin{aligned} E &\to E + T \mid T \\ T &\to T * P \mid P \\ P &\to F \text{ \^{} } P \mid F \\ F &\to \text{id} \end{aligned} \] **2. Analyze ambiguity, precedence, and associativity:** - Each operator is introduced at a distinct non-terminal level: \( + \) at \( E \) (lowest precedence, closest to the root), \( * \) at \( T \) (middle precedence), and \( \text{\^{}} \) at \( P \) (highest precedence, closest to \( F \to \text{id} \)). - At each level, recursion is strictly one-sided: \( E \to E + T \) and \( T \to T * P \) are left-recursive (making \( + \) and \( * \) left-associative), while \( P \to F \text{ \^{} } P \) is right-recursive (making \( \text{\^{}} \) right-associative). - Because precedence and associativity are uniquely fixed at every level, the grammar is completely unambiguous (Option A is true). - Since the grammar is unambiguous, every valid string—including \( \text{id} + \text{id} * \text{id} \text{ \^{} } \text{id} \)—has a unique parse tree (Option B is true). - Since \( P \to F \text{ \^{} } P \) expands recursively on the right, \( \text{\^{}} \) is right-associative (Option C is true). - Since \( P \) is lower in the hierarchy than \( T \), \( \text{\^{}} \) binds tighter (has higher precedence) than \( * \), so Option D is false. **Answer: A, B, and C.** A: **Correct:** Standard layered expression grammars with one-sided recursion at each precedence level are unambiguous. B: **Correct:** Because the grammar is unambiguous, the expression \( \text{id} + \text{id} * \text{id} \text{ \^{} } \text{id} \) has a unique parse tree. C: **Correct:** The production \( P \to F \text{ \^{} } P \) is right-recursive, which makes the exponentiation operator \( \text{\^{}} \) right-associative. D: **Incorrect:** Because \( T \to T * P \mid P \) derives \( P \), the operator \( \text{\^{}} \) (at level \( P \)) has higher precedence than \( * \) (at level \( T \)).

**1. Define Greibach Normal Form (GNF):** A context-free grammar (without \( \varepsilon \)) is in Greibach Normal Form if every production rule is of the form: \[ A \to a \alpha \] where \( A \) is a non-terminal, \( a \in \Sigma \) is a single terminal symbol, and \( \alpha \in V^* \) is a (possibly empty) string of non-terminal variables. **2. Check each grammar against the GNF rule:** - **Option A:** \( S \to aA \mid bB \mid c \). Every right-hand side starts with a single terminal (\( a, b, c \)) followed by zero or more non-terminals (\( A, B, \varepsilon \)). Valid GNF. - **Option B:** \( S \to aA \mid Ab \). The production \( S \to Ab \) starts with a non-terminal \( A \) and ends with a terminal \( b \). Not in GNF. - **Option C:** \( S \to AB \mid a \). The production \( S \to AB \) starts with a non-terminal \( A \) rather than a terminal. Not in GNF. - **Option D:** \( S \to aBC \mid bA \). Both right-hand sides start with a single terminal (\( a \) or \( b \)) followed exclusively by non-terminals (\( BC \) and \( A \)). Valid GNF. **Answer: A and D.** A: **Correct:** Each alternative \( aA \), \( bB \), and \( c \) begins with a single terminal followed by zero or more non-terminals. B: **Incorrect:** The rule \( S \to Ab \) starts with a non-terminal \( A \) and has a terminal \( b \) in the second position, violating GNF. C: **Incorrect:** The rule \( S \to AB \) does not start with a terminal symbol (it is in Chomsky Normal Form, not GNF). D: **Correct:** Both \( aBC \) and \( bA \) start with one terminal symbol followed by a string of non-terminals.

**1. Set up the total number of subsets:** The NFA has \( |Q| = 6 \) states, and all subsets of \( Q \) are reachable in the subset construction. Therefore, the total number of reachable DFA states is: \[ 2^{|Q|} = 2^6 = 64 \] **2. Count the non-accepting subsets:** A DFA state \( S \subseteq Q \) is accepting if and only if \( S \cap F \neq \emptyset \), where \( |F| = 2 \). Equivalently, \( S \) is non-accepting if and only if \( S \cap F = \emptyset \), meaning \( S \) is chosen entirely from the remaining \( |Q \setminus F| = 6 - 2 = 4 \) non-accepting NFA states. The number of such non-accepting subsets is: \[ 2^{6 - 2} = 2^4 = 16 \] **3. Conclude with the number of accepting DFA states:** Subtracting the non-accepting subsets from the total number of subsets gives: \[ \text{Accepting DFA states} = 64 - 16 = 48 \] **Answer: 48.**

**1. Analyze the NFA transition table:** With start state \( q_0 \) and accepting state \( q_3 \), the transitions are: - \( \delta(q_0, 0) = \{q_0, q_1\} \), \( \delta(q_0, 1) = \{q_0\} \) - \( \delta(q_1, 0) = \emptyset \), \( \delta(q_1, 1) = \{q_2\} \) - \( \delta(q_2, 0) = \{q_3\} \), \( \delta(q_2, 1) = \emptyset \) - \( \delta(q_3, 0) = \{q_3\} \), \( \delta(q_3, 1) = \emptyset \) **2. Identify the language accepted by the NFA:** To reach \( q_3 \) from \( q_0 \), the NFA must follow \( q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \), and once in \( q_3 \) it can only self-loop on \( 0 \) (since \( \delta(q_3, 1) = \emptyset \)). Thus, the regular expression is \( (0+1)^* 010 0^* \), meaning a string is accepted if and only if it contains \( 010 \) followed only by zero or more \( 0 \)'s. **3. Test each input string:** - Option A (\( 01011 \)): Ends with \( 1 \); since only \( q_0 \) and \( q_2 \) have incoming transitions on \( 1 \), the set of active states after reading a final \( 1 \) cannot contain \( q_3 \). Rejected. - Option B (\( 0010 \)): Ends with \( 010 \) (via \( q_0 \xrightarrow{0} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \)). Accepted. - Option C (\( 010 \)): Follows \( q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \). Accepted. - Option D (\( 01101 \)): Ends with \( 1 \), so it cannot end in \( q_3 \). Rejected. **Answer: B and C.** A: **Incorrect:** Reading `01011` leaves the NFA in \( \{q_0, q_2\} \); no transition on `1` ever enters or stays in \( q_3 \). B: **Correct:** Reading `0010` has the accepting path \( q_0 \xrightarrow{0} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \). C: **Correct:** Reading `010` has the accepting path \( q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \). D: **Incorrect:** Reading `01101` ends with `1`, and no state has a transition on `1` into \( q_3 \).

**1. Compute the intersection \( L = L_1 \cap L_2 \):** We are given: - \( L_1 = \{w \in \{a,b\}^* \mid w \text{ contains an even number of } a\text{'s}\} \) (a regular language). - \( L_2 = \{a^n b^n \mid n \ge 0\} \) (a context-free language). A string \( w \) belongs to \( L_1 \cap L_2 \) if and only if \( w = a^n b^n \) for some \( n \ge 0 \) AND the number of \( a \)'s (which is \( n \)) is even (i.e., \( n = 2k \) for \( k \ge 0 \)). Therefore: \[ L = L_1 \cap L_2 = \{a^{2k} b^{2k} \mid k \ge 0\} \] This confirms that Option C is true and Option D is false. **2. Determine the language class of \( L \):** - Context-free languages are closed under intersection with regular languages. Since \( L_2 \) is a CFL and \( L_1 \) is regular, \( L = L_1 \cap L_2 \) is guaranteed to be context-free (generated by \( S \to aaSbb \mid \varepsilon \)). Thus, Option B is true. - Just like \( \{a^n b^n \mid n \ge 0\} \), \( L = \{a^{2k} b^{2k} \mid k \ge 0\} \) requires unbounded matching between the count of \( a \)'s and \( b \)'s, so it is not regular. Thus, Option A is false. **Answer: B and C.** A: **Incorrect:** The language \( \{a^{2k} b^{2k} \mid k \ge 0\} \) requires counting and matching an arbitrary even number of \( a \)'s and \( b \)'s, so it is not regular. B: **Correct:** The intersection of a context-free language with a regular language is always context-free. C: **Correct:** Restricting \( a^n b^n \) to strings with an even number of \( a \)'s forces \( n = 2k \), giving \( \{a^{2k} b^{2k} \mid k \ge 0\} \). D: **Incorrect:** Strings in \( L_2 \) with odd \( n \) (such as \( ab \)) are excluded because they do not have an even number of \( a \)'s.

**1. Check each language for both infiniteness and regularity:** - **Option A (\( L = \{a^* b^*\} \)):** Defined directly by the regular expression \( a^* b^* \), so it is regular. Because \( a^n \in L \) for every \( n \ge 0 \), it contains infinitely many strings. - **Option B (\( L = \{a^n b^n : n \ge 0\} \)):** Although infinite, it is the classic non-regular context-free language because a finite automaton cannot match an arbitrary number of \( a \)'s with an equal number of \( b \)'s. - **Option C (\( L = \{w \in \{a,b\}^* : \#a(w) \equiv 0 \pmod 2\} \)):** A 2-state DFA that toggles state on \( a \) and stays put on \( b \) recognizes this language, so it is regular, and it is clearly infinite. - **Option D (\( L = \{ww : w \in \{a,b\}^*\} \)):** The copy language is not even context-free (and therefore not regular), though it is infinite. **Answer: A and C.** A: **Correct:** Generated by the regular expression \( a^* b^* \), which is both regular and infinite. B: **Incorrect:** While infinite, \( \{a^n b^n : n \ge 0\} \) is a non-regular context-free language. C: **Correct:** Recognized by a 2-state DFA tracking the parity of \( a \)'s, so it is both regular and infinite. D: **Incorrect:** The copy language \( \{ww : w \in \{a,b\}^*\} \) is context-sensitive and not regular.

**1. Set up the intersection condition:** We are given: \[ L_1 = \{0^n \mid n \equiv 1 \pmod 6\}, \quad L_2 = \{0^n \mid n \equiv 1 \pmod 8\} \] A string \( 0^n \) belongs to \( L_1 \cap L_2 \) if and only if \( n \) satisfies both congruences simultaneously: \[ n \equiv 1 \pmod 6 \quad \text{and} \quad n \equiv 1 \pmod 8 \] **2. Solve the system of congruences:** The condition \( n - 1 \) is divisible by both \( 6 \) and \( 8 \) holds if and only if \( n - 1 \) is divisible by their least common multiple: \[ \text{lcm}(6, 8) = 24 \] Therefore, \( n - 1 \equiv 0 \pmod{24} \), or equivalently: \[ n \equiv 1 \pmod{24} \] **3. Conclude:** Thus, \( L_1 \cap L_2 = \{0^n \mid n \equiv 1 \pmod{24}\} \). **Answer: A — \( \{0^n \mid n \equiv 1 \pmod{24}\} \).** A: **Correct:** Since \( \text{lcm}(6, 8) = 24 \), \( n \equiv 1 \pmod 6 \) and \( n \equiv 1 \pmod 8 \) hold together if and only if \( n \equiv 1 \pmod{24} \). B: **Incorrect:** If \( n \equiv 0 \pmod{24} \), then \( n \equiv 0 \pmod 6 \), which is not in \( L_1 \). C: **Incorrect:** Using \( 48 = 6 \times 8 \) instead of \( \text{lcm}(6,8) = 24 \) misses valid strings such as \( 0^{25} \). D: **Incorrect:** The intersection is non-empty; for example, \( n = 1, 25, 49, \dots \) belong to both languages.

**1. Decompose the regular expression:** Over \( \Sigma = \{0, 1\} \), the regular expression is: \[ r = 0 + 10^*1 \] Here, \( + \) denotes union, and \( 10^*1 \) denotes a \( 1 \), followed by \( k \ge 0 \) occurrences of \( 0 \), followed by a \( 1 \). **2. Write the language in set notation:** - The first branch \( 0 \) generates \( \{0\} \). - The second branch \( 10^*1 \) generates \( \{10^k 1 \mid k \ge 0\} = \{11, 101, 1001, 10001, \dots\} \). - Taking the union gives \( L(r) = \{0\} \cup \{10^k 1 \mid k \ge 0\} \). **Answer: B — \( \{0\} \cup \{10^k 1 \mid k \ge 0\} \).** A: **Incorrect:** The string `01` starts with `0` and ends with `1`, but it is not generated by \( 0 + 10^*1 \). B: **Correct:** The union \( + \) combines \( \{0\} \) with \( L(10^*1) = \{10^k 1 \mid k \ge 0\} \). C: **Incorrect:** Strings like `0` and `11` belong to \( L(r) \) without containing `101`, and `1101` contains `101` but is not in \( L(r) \). D: **Incorrect:** Many binary strings (such as \( \varepsilon \), `1`, `00`, `01`) are not generated by \( r \).

**1. Read the productions directly from the internal nodes of the parse tree:** - The root node \( S \) has three children from left to right: \( S \), \( a \), and \( b \). This corresponds to the production \( S \to Sab \). - The middle child \( S \) again has three children from left to right: \( S \), \( a \), and \( b \), using \( S \to Sab \) a second time. - The lowest \( S \) node has a single child \( \varepsilon \), corresponding to \( S \to \varepsilon \). **2. Match with the given options:** Combining both rules gives the grammar \( S \to Sab \mid \varepsilon \), which is Option B. **Answer: B — \( S \to Sab \mid \varepsilon \).** A: **Incorrect:** The rule \( S \to aSb \mid \varepsilon \) would place \( S \) between \( a \) and \( b \) and derive \( aabb \), not \( abab \). B: **Correct:** Every internal node \( S \) expands to either \( Sab \) or \( \varepsilon \), matching the given parse tree. C: **Incorrect:** The grammar \( S \to SS \mid ab \) has no \( \varepsilon \)-production and does not have \( S \to Sab \). D: **Incorrect:** The rules \( S \to aS \mid bS \mid \varepsilon \) are right-linear and only produce two children per step.

**1. Recall how the Pumping Lemma for regular languages works:** To prove that \( L = \{0^n 1^n 2^n \mid n \ge 0\} \) is not regular, we assume \( L \) is regular with pumping length \( p \) and choose a string \( w \in L \) with \( |w| \ge p \) such that every valid decomposition \( w = xyz \) with \( |xy| \le p \) and \( |y| \ge 1 \) fails when pumped. **2. Evaluate the candidate strings:** - Choosing \( w = 0^p 1^p 2^p \) (Option B) satisfies \( w \in L \) and \( |w| = 3p \ge p \). Moreover, because the first \( p \) symbols are all \( 0 \)'s, the condition \( |xy| \le p \) forces \( y \) to consist exclusively of \( 0 \)'s (\( y = 0^k \) with \( k \ge 1 \)). Pumping \( xy^2z = 0^{p+k} 1^p 2^p \notin L \) immediately gives a contradiction. - Options A (\( (012)^p \)), C (\( 0^p 1^p \)), and D (\( 0^p 2^p 1^p \)) are not even in \( L \) for \( p \ge 2 \) (or \( p \ge 1 \)), so they cannot be used. **Answer: B — \( 0^p 1^p 2^p \).** A: **Incorrect:** For \( p > 1 \), \( (012)^p \) is not in \( L = \{0^n 1^n 2^n \mid n \ge 0\} \). B: **Correct:** The string \( 0^p 1^p 2^p \) belongs to \( L \), has length \( 3p \ge p \), and forces \( xy \) to lie entirely within the leading \( 0^p \) block. C: **Incorrect:** For \( p \ge 1 \), \( 0^p 1^p \) has no \( 2 \)'s and therefore does not belong to \( L \). D: **Incorrect:** For \( p \ge 1 \), \( 0^p 2^p 1^p \) has \( 2 \)'s before \( 1 \)'s and is not in \( L \).

**1. Trace the path from start state \( q_0 \) to accepting state \( q_2 \):** - State \( q_0 \) has a self-loop on \( a, b \), representing \( (a + b)^* \). - Moving from \( q_0 \) to \( q_1 \) requires reading \( c \). - State \( q_1 \) has a self-loop on \( a, b \), representing \( (a + b)^* \). - Moving from \( q_1 \) to accepting state \( q_2 \) requires reading a second \( c \). - State \( q_2 \) has a self-loop on \( a, b, c \), representing \( (a + b + c)^* \). **2. Concatenate the regular expressions along the path:** Combining these steps in order yields: \[ (a + b)^* c (a + b)^* c (a + b + c)^* \] which is the language of all strings over \( \{a,b,c\} \) containing at least two \( c \)'s. **Answer: A — \( (a+b)^*c(a+b)^*c(a+b+c)^* \).** A: **Correct:** Directly matches the self-loop \( (a+b)^* \) on \( q_0 \), transition \( c \), self-loop \( (a+b)^* \) on \( q_1 \), transition \( c \), and self-loop \( (a+b+c)^* \) on \( q_2 \). B: **Incorrect:** Requires the two \( c \)'s to be adjacent (\( cc \)), rejecting valid strings like \( cac \). C: **Incorrect:** Also requires the first two \( c \)'s to be adjacent (\( cc \)), omitting the \( (a+b)^* \) loop at \( q_1 \). D: **Incorrect:** Requires only one \( c \) instead of at least two \( c \)'s, so it accepts strings that stop in \( q_1 \).

**1. Identify the nullable non-terminals:** The given grammar has productions: - \( S \to AB \) - \( A \to a \mid \varepsilon \) - \( B \to b \mid \varepsilon \) Since \( A \Rightarrow \varepsilon \) and \( B \Rightarrow \varepsilon \), both \( A \) and \( B \) are nullable. Because \( S \to AB \) consists solely of nullable variables, the start symbol \( S \) is also nullable. **2. Construct the productions after eliminating \( \varepsilon \)-rules:** - From \( S \to AB \), substituting subsets of nullable variables \( \{A, B\} \) yields \( S \to AB \), \( S \to A \) (dropping \( B \)), \( S \to B \) (dropping \( A \)), and \( S \to \varepsilon \) (kept because \( \varepsilon \in L(G) \) and the prompt specifies keeping \( S \to \varepsilon \) if needed). That gives 4 productions for \( S \). - Removing \( A \to \varepsilon \) leaves 1 production for \( A \): \( A \to a \). - Removing \( B \to \varepsilon \) leaves 1 production for \( B \): \( B \to b \). **3. Count the total number of productions:** \[ 4 + 1 + 1 = 6 \] **Answer: 6.**

**1. Analyze the language \( L = \{w \in \{0,1\}^* \mid w \text{ contains } 00 \text{ or ends with } 1\} \):** While reading a string left to right, we need to know: 1. Whether \( 00 \) has already appeared (if so, the string is permanently accepted regardless of future symbols). 2. If \( 00 \) has not yet appeared, what the last symbol read was (since ending in \( 1 \) makes the string currently accepting, ending in \( 0 \) means one more \( 0 \) will complete \( 00 \), and \( \varepsilon \) has neither). **2. Construct the minimal DFA states (Myhill-Nerode equivalence classes):** - \( q_{\varepsilon} \) (start, non-accepting): string is \( \varepsilon \) (no \( 00 \) seen, does not end in \( 0 \) or \( 1 \)). - \( q_1 \) (accepting): no \( 00 \) seen yet, and the string ends with \( 1 \). - \( q_0 \) (non-accepting): no \( 00 \) seen yet, and the string ends with a single \( 0 \). - \( q_{00} \) (accepting trap state): \( 00 \) has already occurred. **3. Verify that all 4 states are pairwise distinguishable:** - \( q_{\varepsilon}, q_0 \) are non-accepting whereas \( q_1, q_{00} \) are accepting. - \( q_{\varepsilon} \) and \( q_0 \) are distinguished by input \( 0 \): \( \delta(q_{\varepsilon}, 0) = q_0 \notin F \), while \( \delta(q_0, 0) = q_{00} \in F \). - \( q_1 \) and \( q_{00} \) are distinguished by input \( 0 \): \( \delta(q_1, 0) = q_0 \notin F \), while \( \delta(q_{00}, 0) = q_{00} \in F \). Hence, the minimal DFA has 4 states. **Answer: 4.**