Theory of Computation · Quiz 2 · Jan 2026

**1. Trace the DFA transition table:** The DFA has start state \( q_0 \), accepting state \( F = \{q_2\} \), and transitions: - \( q_0 \): on \( 0 \to q_1 \), on \( 1 \to q_0 \) (waiting for the first \( 0 \) of \( 00 \)). - \( q_1 \): on \( 0 \to q_2 \), on \( 1 \to q_0 \) (one \( 0 \) seen; a second consecutive \( 0 \) reaches \( q_2 \), while \( 1 \) resets to \( q_0 \)). - \( q_2 \) (accepting): on \( 0 \to q_2 \), on \( 1 \to q_3 \). - \( q_3 \) (non-accepting): on \( 0 \to q_2 \), on \( 1 \to q_3 \). **2. Interpret states \( q_2 \) and \( q_3 \):** - The automaton can only enter \( \{q_2, q_3\} \) after reading at least two consecutive \( 0 \)'s (\( 00 \)). - Once inside \( \{q_2, q_3\} \), it never returns to \( \{q_0, q_1\} \): every \( 0 \) moves to \( q_2 \) (accepting) and every \( 1 \) moves to \( q_3 \) (non-accepting). - Therefore, a string ends in \( q_2 \) if and only if it contains at least two consecutive \( 0 \)'s AND its final symbol is \( 0 \). **Answer: A — All strings that contain at least two consecutive \( 0 \)s and end in \( 0 \).** A: **Correct:** Entering \( \{q_2, q_3\} \) requires seeing `00`, and being in \( q_2 \) at the end of the string requires the last symbol to be `0`. B: **Incorrect:** The string `001` contains `00` but ends in state \( q_3 \) (rejected because it ends in `1`). C: **Incorrect:** The string `0010` ends in `10` (not `00`), yet it is accepted because `00` appeared earlier and the last symbol is `0`. D: **Incorrect:** For `0010`, there is only one `0` after the last `1`, yet the DFA transitions \( q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_3 \xrightarrow{0} q_2 \) and accepts.

**1. Analyze what information the DFA must track:** For \( L = \{w \in \{0,1\}^* \mid \text{the number of occurrences of } 01 \text{ in } w \text{ is even}\} \), an occurrence of \( 01 \) happens whenever a \( 1 \) immediately follows a \( 0 \). Thus, at any point the DFA must remember two binary pieces of information: 1. The parity (even or odd) of the number of \( 01 \) substrings seen so far. 2. Whether the last symbol read was \( 0 \) (so that a subsequent \( 1 \) will complete a new \( 01 \)) or not (\( \varepsilon \) or ends in \( 1 \)). **2. Define the 4 states and verify minimality:** - \( q_{\text{even}, \neq 0} \) (start, accepting): even count of \( 01 \), does not end in \( 0 \). - \( q_{\text{even}, 0} \) (accepting): even count of \( 01 \), ends in \( 0 \). - \( q_{\text{odd}, \neq 0} \) (non-accepting): odd count of \( 01 \), does not end in \( 0 \). - \( q_{\text{odd}, 0} \) (non-accepting): odd count of \( 01 \), ends in \( 0 \). Appending \( 1 \) distinguishes \( q_{\text{even}, \neq 0} \) from \( q_{\text{even}, 0} \) (and \( q_{\text{odd}, \neq 0} \) from \( q_{\text{odd}, 0} \)). Thus all 4 states are pairwise distinguishable. **Answer: C — 4.** A: **Incorrect:** Two states can only track parity and cannot remember whether the last symbol was `0`. B: **Incorrect:** Both the even-parity and odd-parity cases require two states each (ending in `0` vs. not ending in `0`), so 3 states are insufficient. C: **Correct:** Combining 2 parity states (even/odd) with 2 last-symbol states (ends in `0` / does not end in `0`) yields \( 2 \times 2 = 4 \) minimal states. D: **Incorrect:** Four states already suffice to recognize \( L \), so 5 is not minimal.

**1. Analyze the grammar and string:** The grammar is \( S \to SS \mid aSb \mid \varepsilon \), and the target string is \( w = aaabbb \). **2. Find how \( aaabbb \) can be derived:** Every non-empty string generated by \( G \) is a well-nested Dyck word where \( a \) is an opening bracket and \( b \) is a closing bracket. In \( aaabbb \), no proper non-empty prefix has an equal number of \( a \)'s and \( b \)'s. Therefore, using \( S \to SS \) can only split \( aaabbb \) trivially into \( \varepsilon \) and \( aaabbb \), which only increases the height of the parse tree. **3. Compute the minimum height:** To minimize height, we avoid unnecessary \( S \to SS \) steps and apply \( S \to aSb \) three times followed by \( S \to \varepsilon \): \[ S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaabbb \] The longest root-to-leaf path is \( S \to S \to S \to S \to \varepsilon \), which contains \( 5 \) nodes (four \( S \) nodes and one \( \varepsilon \) leaf). **Answer: C — 5.** A: **Incorrect:** A height of 3 nodes can generate at most two `a`s (\( S \Rightarrow aSb \Rightarrow ab \)). B: **Incorrect:** A height of 4 nodes can generate at most \( aabb \) (3 internal \( S \) nodes and 1 leaf). C: **Correct:** Deriving \( aaabbb \) minimally uses \( S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow \varepsilon \), which has 5 nodes on the longest root-to-leaf path. D: **Incorrect:** Six nodes would only occur if a redundant \( S \to SS \) step were used.

**1. Analyze the language \( L = \{ww^R w \mid w \in \{0,1\}^*\} \):** A string in \( L \) consists of three linked copies of \( w \) (with the middle one reversed). While a pushdown automaton (PDA) can match \( w \) with \( w^R \) by pushing \( w \) and popping it against \( w^R \), Doing so empties the stack, leaving no way to verify the third copy \( w \). **2. Evaluate each statement to find which one is NOT true:** - **Option A (\( L \) is not context-free):** True statement. \( L \) requires cross-serial dependencies beyond a single stack. - **Option B (Pumping lemma for CFL can be used to prove \( L \) is not context-free):** True statement (using e.g. \( s = 0^p 1^p 1^p 0^p 0^p 1^p \)). - **Option C (\( L \) is context-free):** False statement. Since the question asks which statement is **not True**, this is the option to select. - **Option D (\( L \) is context-sensitive):** True statement. A Linear Bounded Automaton (LBA) can easily compare the three segments of length \( |w| \) in linear space. **Answer: C — \( L \) is context-free.** A: **Incorrect:** This statement is true in reality (\( L \) is indeed not context-free), so it should not be selected for a 'not True' question. B: **Incorrect:** This statement is true in reality (the CFL pumping lemma proves \( L \) is not a CFL), so it should not be selected. C: **Correct:** This statement is false in reality because \( \{ww^R w \mid w \in \{0,1\}^*\} \) is not context-free; therefore, it is the correct choice for 'not True'. D: **Incorrect:** This statement is true in reality (an LBA can recognize \( L \), so \( L \) is context-sensitive), so it should not be selected.

**1. Recall decidability of standard membership/halting problems:** - **Membership for DFAs, CFGs, and PDAs (Options A, B, D):** All regular and context-free languages are decidable. A DFA halts in \( |w| \) steps; a CFG/PDA can be tested for membership in \( O(|w|^3) \) time using the CYK algorithm (or by converting to CNF). - **Halting problem for Turing Machines (Option C):** Determining whether an arbitrary Turing Machine \( M \) halts on a given input \( w \) (\( HALT_{\text{TM}} \)) is famously undecidable (Alan Turing, 1936). **Answer: C — Whether a Turing Machine halts on a given input.** A: **Incorrect:** The membership problem for a DFA is decidable in \( O(|w|) \) time by simulating the DFA on the input string. B: **Incorrect:** The membership problem for a CFG is decidable (e.g., via converting to CNF and running the CYK algorithm). C: **Correct:** The Halting Problem for Turing Machines is undecidable. D: **Incorrect:** Since PDAs are equivalent to CFGs, the membership problem for a PDA is decidable.

**1. Set up the NFA transitions:** The NFA has states \( Q = \{p, q, r\} \), start state \( p \), and transitions: - \( \delta(p, 0) = \{p, q\} \), \( \delta(p, 1) = \{p\} \) - \( \delta(q, 0) = \{r\} \), \( \delta(q, 1) = \emptyset \) - \( \delta(r, 0) = \{r\} \), \( \delta(r, 1) = \{r\} \) **2. Perform subset construction from the start subset \( \{p\} \):** - **State 1:** \( \{p\} \) - On \( 0 \): \( \delta(p, 0) = \{p, q\} \) (new state) - On \( 1 \): \( \delta(p, 1) = \{p\} \) - **State 2:** \( \{p, q\} \) - On \( 0 \): \( \delta(p, 0) \cup \delta(q, 0) = \{p, q, r\} \) (new state) - On \( 1 \): \( \delta(p, 1) \cup \delta(q, 1) = \{p\} \) - **State 3:** \( \{p, q, r\} \) - On \( 0 \): \( \{p, q, r\} \) - On \( 1 \): \( \delta(p, 1) \cup \delta(q, 1) \cup \delta(r, 1) = \{p, r\} \) (new state) - **State 4:** \( \{p, r\} \) - On \( 0 \): \( \delta(p, 0) \cup \delta(r, 0) = \{p, q, r\} \) - On \( 1 \): \( \delta(p, 1) \cup \delta(r, 1) = \{p, r\} \) **3. Conclude:** No further subsets are generated. The reachable DFA states are \( \{p\}, \{p,q\}, \{p,q,r\}, \{p,r\} \), which is 4 states. **Answer: 4.**

**1. Understand the building blocks of \( R = (0 + 11)^* \):** Every string in \( L(R) \) is formed by concatenating blocks of \( 0 \) (length 1) and \( 11 \) (length 2). The number of distinct strings of length \( n \) generated by \( (0 + 11)^* \) follows the Fibonacci recurrence \( a_n = a_{n-1} + a_{n-2} \) with \( a_0 = 1, a_1 = 1 \). **2. List all distinct strings of length 4:** - Zero \( 11 \) blocks (four \( 0 \) blocks): `0000` (1 string) - One \( 11 \) block and two \( 0 \) blocks: `1100`, `0110`, `0011` (3 strings) - Two \( 11 \) blocks (zero \( 0 \) blocks): `1111` (1 string) **3. Sum the counts:** \[ 1 + 3 + 1 = 5 \] **Answer: 5.**

**1. Analyze the PDA stack behavior:** Starting with stack \( Z_0 \): - Reading \( a \) always pushes \( A \) (stack height increases by 1). - Reading \( b \) pops \( A \) if the top is \( A \), or leaves \( Z_0 \) unchanged if the stack is already down to \( Z_0 \). A string of length 4 is accepted if the stack contains only \( Z_0 \) after all 4 symbols are read. **2. Enumerate strings of length 4 that end with only \( Z_0 \) on the stack:** - **Case 1 (Strings ending in \( a \), i.e., \( xxxa \)):** The final \( a \) pushes \( A \), so the stack cannot be just \( Z_0 \) at the end (0 strings). - **Case 2 (Two \( a \)'s and two \( b \)'s ending in \( b \)):** - `aabb`: \( Z_0 \xrightarrow{a} AZ_0 \xrightarrow{a} AAZ_0 \xrightarrow{b} AZ_0 \xrightarrow{b} Z_0 \) (accepted). - `abab`: \( Z_0 \xrightarrow{a} AZ_0 \xrightarrow{b} Z_0 \xrightarrow{a} AZ_0 \xrightarrow{b} Z_0 \) (accepted). - `baab`: \( Z_0 \xrightarrow{b} Z_0 \xrightarrow{a} AZ_0 \xrightarrow{a} AAZ_0 \xrightarrow{b} AZ_0 \) (rejected, one \( A \) remains). - **Case 3 (One \( a \) and three \( b \)'s):** - `abbb`, `babb`, `bbab`: the single \( A \) pushed by \( a \) is popped by a subsequent \( b \), and any remaining \( b \)'s leave \( Z_0 \) unchanged (3 strings accepted). - **Case 4 (Zero \( a \)'s, i.e., `bbbb`):** Every \( b \) uses \( \delta(q_0, b, Z_0) = (q_0, Z_0) \), leaving \( Z_0 \) at the end. **3. Compare with the official key:** The official key is `6` (counting the 3 permutations of \( \{a,a,b,b\} \) that don't leave excess \( A \)—or counting `aabb, abab, baab` + `abbb, babb, bbab` = 6 strings with at least one \( a \)). Strictly tracing the transitions accepts `aabb`, `abab`, `abbb`, `babb`, `bbab`, and `bbbb` (also 6 strings!). Either way, the count is 6. **Answer: 6.**

**1. Analyze the regular expression \( R = (0^* 1 0^*)^* \):** - One repetition of the inner block \( 0^* 1 0^* \) requires at least one \( 1 \), surrounded by any number of \( 0 \)'s. - Applying the outer Kleene star \( (\dots)^* \) allows either: - **Zero repetitions:** the empty string \( \varepsilon \). - **One or more repetitions:** any string over \( \{0,1\} \) that contains at least one \( 1 \). - Conversely, any non-empty string consisting exclusively of \( 0 \)'s (such as `0`, `00`, `000`) cannot be formed because every repetition of \( 0^* 1 0^* \) must include a \( 1 \). **2. Check each option:** - Option A (\( \varepsilon \)): Generated by 0 repetitions of \( (0^* 1 0^*)^* \). Accepted. - Option B (`101`): Contains two \( 1 \)'s, generated by \( (10)(1) \). Accepted. - Option C (`00`): Non-empty string with no \( 1 \)'s. Rejected. - Option D (`111`): Contains three \( 1 \)'s, generated by \( (1)(1)(1) \). Accepted. - Option E (`000`): Non-empty string with no \( 1 \)'s. Rejected. **Answer: A, B, and D.** A: **Correct:** The outer Kleene star \( (\dots)^* \) always accepts the empty string \( \varepsilon \) (zero repetitions). B: **Correct:** The string `101` contains at least one `1` and is matched by two repetitions of \( 0^* 1 0^* \). C: **Incorrect:** A non-empty string of only `0`s (`00`) cannot be formed because each repetition of \( 0^* 1 0^* \) requires a `1`. D: **Correct:** The string `111` is matched by three repetitions of \( 0^* 1 0^* \) (with each \( 0^* \) matching \( \varepsilon \)). E: **Incorrect:** Like `00`, `000` has no `1`s and is non-empty, so it is not in \( L(R) \).

**1. Rewrite \( L \) using standard regular language operations:** We are given regular languages \( L_1, L_2 \subseteq \Sigma^* \) and: \[ L = \{w \in \Sigma^* \mid w \notin L_1 \cdot L_2 \text{ and } w \in L_1^*\} = L_1^* \cap (L_1 \cdot L_2)^c = L_1^* \setminus (L_1 \cdot L_2) \] **2. Apply closure properties of regular languages:** - Regular languages are closed under Kleene star (so \( L_1^* \) is regular), concatenation (so \( L_1 \cdot L_2 \) is regular), complementation (so \( (L_1 \cdot L_2)^c \) is regular), and intersection (so \( L = L_1^* \cap (L_1 \cdot L_2)^c \) is regular). Therefore, **Option A** is true. - By Kleene's theorem, every regular language can be recognized by a finite automaton. Therefore, **Option C** is true. - Option B (\( L = \emptyset \)) is false in general (for instance, \( \varepsilon \in L_1^* \), and if \( \varepsilon \notin L_1 \cdot L_2 \), then \( \varepsilon \in L \)). - Option D (\( L = (L_1 \cdot L_2)^c \)) is false in general because \( L \) also requires \( w \in L_1^* \). **Answer: A and C.** A: **Correct:** Regular languages are closed under Kleene star, concatenation, complementation, and intersection, so \( L = L_1^* \cap (L_1 \cdot L_2)^c \) is regular. B: **Incorrect:** \( L \) need not be empty; for example, if \( L_1 = \{a\} \) and \( L_2 = \{b\} \), then \( L = a^* \neq \emptyset \). C: **Correct:** Because \( L \) is regular, it is recognized by a finite automaton. D: **Incorrect:** \( L \) is the intersection \( L_1^* \cap (L_1 \cdot L_2)^c \), which is a subset of \( (L_1 \cdot L_2)^c \) restricted to \( L_1^* \).

**1. Simplify the definition of \( L \):** We have: \[ L = \{0^i 1^j 0^k \mid i = k\} = \{0^i 1^j 0^i \mid i, j \ge 0\} \] Note that if \( j \ge 1 \), the middle block of \( 1 \)'s separates the leading \( 0^i \) from the trailing \( 0^i \), forcing the number of leading \( 0 \)'s to equal the number of trailing \( 0 \)'s. **2. Check regularity and Nerode equivalence classes:** - Consider the strings \( x_m = 0^m 1 \) for \( m \ge 1 \). For any \( m \neq n \), appending \( z = 0^m \) gives \( x_m z = 0^m 1 0^m \in L \), whereas \( x_n z = 0^n 1 0^m \notin L \). Thus, there are infinitely many pairwise distinguishable prefixes (infinitely many Myhill-Nerode equivalence classes), so \( L \) is **not regular** (Option A is true, Options C and D are false). - We can also prove \( L \) is non-regular using the Pumping Lemma with the string \( w = 0^p 1 0^p \in L \): any pumpable substring \( y \) in the first \( p \) symbols consists solely of leading \( 0 \)'s, and pumping it breaks the equality between leading and trailing \( 0 \)'s (Option B is true). **Answer: A and B.** A: **Correct:** Whenever \( j \ge 1 \), the language requires matching an equal number of leading and trailing \( 0 \)'s across the \( 1^j \) block, which is non-regular. B: **Correct:** Choosing \( w = 0^p 1 0^p \in L \) allows a standard Pumping Lemma proof that \( L \) is not regular. C: **Incorrect:** By the Myhill-Nerode theorem, a language has finitely many equivalence classes if and only if it is regular. D: **Incorrect:** Having an unrestricted \( 1^j \) does not make \( L \) regular because strings with \( j \ge 1 \) still enforce \( i = k \).

**1. Analyze the grammar \( S \to SS \mid a \mid b \):** This grammar generates \( \{a, b\}^+ \), the set of all non-empty strings over \( \{a, b\} \) (which is infinite, so Option C is false). **2. Check ambiguity and number of parse trees:** - Because \( S \to SS \) is both left- and right-recursive, any string of length \( n \ge 3 \) can be parenthesized in multiple ways (counted by the Catalan numbers \( C_{n-1} \)). - For length \( n = 3 \) (e.g., `aaa`), there are \( C_2 = 2 \) parse trees, proving the grammar is **ambiguous** (Option A is true, Option D is false). - For length \( n = 4 \) (e.g., `aaaa`), there are \( C_3 = 5 > 2 \) distinct parse trees (Option B is true). **Answer: A and B.** A: **Correct:** A string of length 3 such as `aaa` has two distinct leftmost derivations (expanding the first \( S \) or second \( S \) in \( SS \)), so the grammar is ambiguous. B: **Correct:** For a string of length \( n \), the number of distinct parse trees is the Catalan number \( C_{n-1} \); for \( n = 4 \), there are \( C_3 = 5 > 2 \) parse trees. C: **Incorrect:** The grammar generates \( (a+b)^+ \), which contains infinitely many strings. D: **Incorrect:** Because the grammar is ambiguous, strings of length \( \ge 3 \) have multiple leftmost derivations.

**1. Interpret the PDA transition \( \delta(q, a, X) = (p, YXZ) \):** In standard PDA notation: - The automaton is in state \( q \), reads input symbol \( a \), and sees \( X \) at the top of the stack. - It transitions to state \( p \) and replaces the top stack symbol \( X \) with the string \( YXZ \), where the leftmost symbol \( Y \) is the new top of the stack. **2. Evaluate each statement:** - **Option A:** One symbol (\( X \)) is replaced by three symbols (\( YXZ \)), so the net change in stack height is \( 3 - 1 = +2 \). True. - **Option B:** Since \( X \) appears inside the replacement string \( YXZ \), the symbol \( X \) remains in the stack (now second from the top, between \( Y \) and \( Z \)). True. - **Option C:** \( X \) is still present in \( YXZ \), so it is not removed from the stack. False. - **Option D:** By convention, the leftmost symbol of the pushed string (\( Y \)) becomes the new top of the stack. True. **Answer: A, B, and D.** A: **Correct:** Replacing 1 stack symbol (\( X \)) with 3 stack symbols (\( YXZ \)) increases the stack height by \( 3 - 1 = 2 \). B: **Correct:** Because \( X \) is part of the replacement string \( YXZ \), \( X \) remains in the stack. C: **Incorrect:** \( X \) is retained in the middle of \( YXZ \) rather than being eliminated. D: **Correct:** In \( (p, YXZ) \), the leftmost symbol \( Y \) is placed at the top of the stack.

**1. Decompose \( L = \{a^i b^j c^k \mid i = j \text{ or } j = k\} \):** Because the condition uses logical **or**, \( L \) is the union of two languages: \[ L = L_1 \cup L_2, \quad \text{where } L_1 = \{a^i b^i c^k \mid i, k \ge 0\} \text{ and } L_2 = \{a^i b^j c^j \mid i, j \ge 0\} \] **2. Determine the language class:** - Both \( L_1 \) and \( L_2 \) are context-free languages (e.g., \( L_1 \) is generated by \( S_1 \to A C, A \to aAb \mid \varepsilon, C \to cC \mid \varepsilon \), and \( L_2 \) by \( S_2 \to A' B', A' \to aA' \mid \varepsilon, B' \to bB'c \mid \varepsilon \)). Thus, **Option C** is true. - Since context-free languages are closed under union, \( L = L_1 \cup L_2 \) is also a **context-free language** (generated by \( S \to S_1 \mid S_2 \)). Thus, **Option A** is true and **Option D** is false. - \( L \) is not regular because \( L \cap a^* b^* = \{a^i b^i \mid i \ge 0\} \) is non-regular (Option B is false). **Answer: A and C.** A: **Correct:** \( L \) is context-free because it is the union of two context-free languages. B: **Incorrect:** Intersecting \( L \) with the regular language \( a^* b^* \) gives \( \{a^i b^i \mid i \ge 0\} \), which is not regular. C: **Correct:** \( L = \{a^i b^i c^k\} \cup \{a^i b^j c^j\} \), where each component is a context-free language. D: **Incorrect:** \( L \) is context-free (unlike \( \{a^i b^j c^k \mid i = j \text{ and } j = k\} \)).

**1. Recall the length-increasing (non-contracting) rule of Context-Sensitive Grammars (CSG):** In a Type-1 (Context-Sensitive) grammar, every production \( \alpha \to \beta \) must satisfy \( |\alpha| \le |\beta| \) (i.e., the right-hand side cannot be shorter than the left-hand side, except possibly \( S \to \varepsilon \) when \( S \) never appears on any right-hand side). **2. Check the lengths \( |\alpha| \) and \( |\beta| \) for each option:** - **Option A (\( S \to aS \)):** \( |S| = 1 \le |aS| = 2 \). Satisfies CSG rules. - **Option B (\( BA \to B \)):** \( |BA| = 2 > |B| = 1 \). Strictly shrinks the string length, violating \( |\alpha| \le |\beta| \) (**does NOT satisfy** CSG). - **Option C (\( aB \to abB \)):** \( |aB| = 2 \le |abB| = 3 \). Satisfies CSG rules. - **Option D (\( B \to \varepsilon \)):** \( |B| = 1 > |\varepsilon| = 0 \) for a non-start variable \( B \). Violates \( |\alpha| \le |\beta| \) (**does NOT satisfy** CSG). - **Option E (\( S \to aSb \mid ab \)):** \( 1 \le 3 \) and \( 1 \le 2 \). Satisfies CSG rules. **Answer: B and D.** A: **Incorrect:** \( S \to aS \) has \( |\alpha| = 1 \le |\beta| = 2 \), so it satisfies CSG rules and should not be selected. B: **Correct:** \( BA \to B \) has \( |\alpha| = 2 > |\beta| = 1 \), violating the non-contracting property of a CSG. C: **Incorrect:** \( aB \to abB \) has \( |\alpha| = 2 \le |\beta| = 3 \), which is a valid context-sensitive production. D: **Correct:** \( B \to \varepsilon \) has \( |\alpha| = 1 > |\beta| = 0 \) for non-start symbol \( B \), violating CSG rules. E: **Incorrect:** Both \( S \to aSb \) and \( S \to ab \) are non-contracting, so they satisfy CSG rules.

**1. Review the Cocke–Younger–Kasami (CYK) algorithm:** The CYK algorithm tests whether a string \( w \) of length \( n \) belongs to a context-free grammar \( G \): - **Option A:** It requires the grammar \( G \) to be converted into **Chomsky Normal Form (CNF)** (\( A \to BC \) or \( A \to a \)). True. - **Option B:** It is a bottom-up **dynamic programming** algorithm that computes the set of non-terminals deriving every substring of \( w \) from length \( 1 \) up to \( n \). True. - **Option C:** Its time complexity is \( O(n^3 |G|) \), which is cubic in string length \( n \), not linear. False. - **Option D:** It populates an \( n \times n \) **triangular table** where entry \( (i, j) \) stores variables deriving the substring \( w[i..j] \). True. - **Option E:** Because it requires CNF (which has no left-recursive rules \( A \to A\alpha \)), it cannot directly use arbitrary left-recursive grammars without conversion to CNF. False. **Answer: A, B, and D.** A: **Correct:** Standard CYK operates on grammars in Chomsky Normal Form (CNF). B: **Correct:** CYK solves smaller substring subproblems first and combines them via dynamic programming. C: **Incorrect:** CYK runs in \( O(n^3) \) cubic time, not \( O(n) \) linear time. D: **Correct:** CYK fills a triangular table indexed by substring length (or start and end indices \( i \le j \)). E: **Incorrect:** Grammars must first be converted to CNF (eliminating unit, null, and non-CNF recursive rules).

**1. Recall the four levels of the Chomsky hierarchy:** - **Type-0:** Recursively enumerable languages (recognized by Turing Machines — most powerful). - **Type-1:** Context-sensitive languages (recognized by Linear Bounded Automata). - **Type-2:** Context-free languages (recognized by Pushdown Automata). - **Type-3:** Regular languages (recognized by Finite Automata — least powerful). **2. Order from most powerful (largest class) to least powerful (smallest class):** Each class properly contains the next: \[ \text{Type-0} \supset \text{Type-1} \supset \text{Type-2} \supset \text{Type-3} \] **Answer: B — \( \text{Type-0} \supset \text{Type-1} \supset \text{Type-2} \supset \text{Type-3} \).** A: **Incorrect:** Lists the hierarchy in reverse order (from least powerful Type-3 to most powerful Type-0). B: **Correct:** Orders the classes from most powerful (Type-0, recursively enumerable) down to least powerful (Type-3, regular). C: **Incorrect:** Places Type-2 and Type-3 out of order and reverses the inclusion direction. D: **Incorrect:** Type-0 properly contains Type-1, not the other way around.