Mock Exam 2 — CSE2315 Automata

Exam Info

CSE2315 Automata, Computability and Complexity. Closed-book — one double-sided A4 handwritten cheatsheet allowed. No calculator. Assume P ≠ NP and NP ≠ EXP. Karp reductions denoted ≤_P. Irrelevant information costs points. 45 pts total, 10 questions.

Q1 — 5 pts

Consider DFA $D = (Q, \Sigma, \delta, q_0, F)$ over $\Sigma = \{0, 1\}$ with states $Q = \{q_0, q_1, q_2\}$ and transitions:

State	0	1
$q_0$ (start)	$q_1$	$q_0$
$q_1$	$q_2$	$q_0$
$q_2$ (accept)	$q_2$	$q_2$

$L(D)$ = the set of strings over $\{0,1\}$ that contain the substring "00".

(a) (1 pt) Give the set of accept states $F$ in set notation.

(b) (4 pts) Construct an NFA $N$ such that $L(N) = L(D)^*$. Use the procedure from Sipser (Theorem 1.49). Give the full 5-tuple.

Solution

Part (a)

$F = \{q_2\}$

Part (b) — Kleene Star Construction

The Sipser construction for $L^*$:

Add a new start state $q_s$.
$q_s$ is an accept state (since $\varepsilon \in L^*$).
Add $\varepsilon$-transition from $q_s$ to the old start state $q_0$.
Add $\varepsilon$-transitions from every old accept state back to the old start state $q_0$.

$N = (Q', \Sigma, \delta', q_s, F')$ where:

$Q' = \{q_s, q_0, q_1, q_2\}$
$\Sigma = \{0, 1\}$
$F' = \{q_s\}$
$\delta'$: all original transitions are preserved, plus:
- $\delta'(q_s, \varepsilon) = \{q_0\}$
- $\delta'(q_2, \varepsilon) = \{q_0\}$ (old accept → old start)

NFA with 4 states. New start $q_s$ (accepting) with $\varepsilon$-transition to $q_0$. Accept state $q_2$ gets $\varepsilon$-transition back to $q_0$. Original transitions unchanged.

Key insight: the new start state must be a new state (not the old start) to avoid incorrectly making the old start accepting, which would change the language.

Q2 — 3 pts

Consider NFA $N = (\{q_0, q_1\}, \{a, b\}, \delta, q_0, \{q_1\})$ with transitions:

State	$a$	$b$
$q_0$ (start)	$\{q_0, q_1\}$	$\{q_0\}$
$q_1$ (accept)	$\emptyset$	$\{q_1\}$

Apply the subset construction to convert $N$ to an equivalent DFA $D$. Leave out unreachable states from the start state.

Solution

Step 1 — Start state

Start state of DFA: $\{q_0\}$ (no $\varepsilon$-transitions).

Step 2 — Compute transitions

DFA State	$a$	$b$	Accept?
$\{q_0\}$	$\{q_0, q_1\}$	$\{q_0\}$	No
$\{q_0, q_1\}$	$\{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}$	$\{q_0\} \cup \{q_1\} = \{q_0, q_1\}$	Yes

Step 3 — Result

Only two reachable states: $\{q_0\}$ and $\{q_0, q_1\}$. The state $\{q_0, q_1\}$ is a sink — both transitions loop back to itself.

DFA with 2 states. Start: $\{q_0\}$. Accept: $\{q_0, q_1\}$.
$\{q_0\}$ on $a$ → $\{q_0, q_1\}$, on $b$ → $\{q_0\}$.
$\{q_0, q_1\}$ on $a$ → $\{q_0, q_1\}$, on $b$ → $\{q_0, q_1\}$.

$L(N)$ = strings containing at least one $a$. Once an $a$ is seen, the DFA stays in the accept state forever.

Q3 — 2 pts

Give a regular expression $R$ such that $L(R) = \{w \in \{a, b\}^* \mid |w| \text{ is even}\}$.

Your regex should use only the operators union ($\cup$), concatenation, and Kleene star (${}^*$), plus the symbols $a$, $b$, and $\varepsilon$.

Solution

Even length = the string can be split into pairs of characters. Each pair is one of $aa, ab, ba, bb$.

$R = ((a \cup b)(a \cup b))^*$

Equivalently: $(aa \cup ab \cup ba \cup bb)^*$

The empty string $\varepsilon$ has length 0 (even), and is included since the Kleene star allows zero repetitions.

Q4 — 3 pts

Let $L = \{0^n 1^n 0^n \mid n \ge 0\}$.

Prove that $L$ is not regular using the Pumping Lemma. Use the word $w = 0^p 1^p 0^p$ where $p$ is the pumping length.

Solution

Setup

Assume for contradiction that $L$ is regular. Let $p$ be the pumping length. Choose $w = 0^p 1^p 0^p$. Since $|w| = 3p \ge p$, the pumping lemma applies.

Decomposition

Write $w = xyz$ with $|xy| \le p$ and $|y| \ge 1$.

Since $|xy| \le p$, the first $p$ characters of $w$ are all 0's. So $y = 0^k$ for some $k \ge 1$.

Pump

Consider $xy^2z = 0^{p+k} 1^p 0^p$.

The first block has $p + k$ zeros, but the third block still has $p$ zeros. Since $k \ge 1$, we have $p + k > p$, so the number of 0's in the first block exceeds the number in the third block.

Therefore $xy^2z \notin L$, contradicting the pumping lemma.

$L$ is not regular. $\square$

This also proves $L$ is not regular via the stronger fact that it's not even context-free (provable via the CFL pumping lemma), but the regular pumping lemma suffices here.

Q5 — 5 pts

Consider the CFG $G = (\{S, A, B\}, \{a, b\}, R, S)$ with rules:

$S \to AB, \quad A \to aAb \mid ab, \quad B \to bB \mid \varepsilon$

(a) (2 pts) Convert $G$ to Chomsky Normal Form (CNF). Show all intermediate steps (START, DEL, UNIT, TERM, BIN).

(b) (3 pts) Give a PDA $P$ with at most 6 states that accepts the language $L = \{a^n b^m \mid n \ge 1, m \ge n\}$ by final state. Draw the transition diagram or give the formal transitions.

Solution

Part (a) — CNF Conversion

Original: $S \to AB, \; A \to aAb \mid ab, \; B \to bB \mid \varepsilon$

1. START: $S$ does not appear on any RHS → skip (no new start variable needed).

2. DEL ($\varepsilon$-rules): $B$ is nullable ($B \to \varepsilon$).

$S \to AB \mid A$ (added $S \to A$ since $B$ is nullable)
$A \to aAb \mid ab$ (unchanged)
$B \to bB \mid b$ (removed $B \to \varepsilon$, added $B \to b$)

3. UNIT: $S \to A$ is a unit rule. Replace with $A$'s productions:

$S \to AB \mid aAb \mid ab$
$A \to aAb \mid ab$
$B \to bB \mid b$

4. TERM: Replace terminals in bodies of length ≥ 2 with new variables $U_a, U_b$:

$U_a \to a, \; U_b \to b$
$S \to AB \mid U_a A U_b \mid U_a U_b$
$A \to U_a A U_b \mid U_a U_b$
$B \to U_b B \mid b$

5. BIN: Break bodies of length > 2 into pairs. Introduce $V_1$ for $AU_b$:

$S \to AB \mid U_a V_1 \mid U_a U_b$
$A \to U_a V_1 \mid U_a U_b$
$V_1 \to A U_b$
$B \to U_b B \mid b$
$U_a \to a, \; U_b \to b$

CNF: all rules are $X \to YZ$ or $X \to t$. ✓

Part (b) — PDA for $\{a^n b^m \mid n \ge 1, m \ge n\}$

Strategy: push $a$'s onto the stack, then pop one $a$ per $b$ (matching phase), then keep reading $b$'s after stack is empty (extra $b$'s allowed since $m \ge n$).

States: $q_0$ (start), $q_1$ (push $a$'s), $q_2$ (pop $a$'s with $b$'s), $q_3$ (read extra $b$'s), $q_{\text{acc}}$ (accept). Uses $\$$ as bottom-of-stack marker.

Transitions:

$q_0 \xrightarrow{\varepsilon,\, \varepsilon \to \$} q_1$ (push bottom marker)
$q_1 \xrightarrow{a,\, \varepsilon \to a} q_1$ (push each $a$)
$q_1 \xrightarrow{b,\, a \to \varepsilon} q_2$ (switch to matching, pop first $a$)
$q_2 \xrightarrow{b,\, a \to \varepsilon} q_2$ (keep matching)
$q_2 \xrightarrow{b,\, \$ \to \varepsilon} q_3$ (stack empty, switch to extra $b$'s)
$q_2 \xrightarrow{\varepsilon,\, \$ \to \varepsilon} q_{\text{acc}}$ (no extra $b$'s, $m = n$, accept)
$q_3 \xrightarrow{b,\, \varepsilon \to \varepsilon} q_3$ (read extra $b$'s)
$q_3 \xrightarrow{\varepsilon,\, \varepsilon \to \varepsilon} q_{\text{acc}}$ (accept)

5 states: $q_0, q_1, q_2, q_3, q_{\text{acc}}$. Requires $n \ge 1$ (must read at least one $a$ before switching). ≤ 6 states ✓

Q6 — 4 pts

Consider the Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{acc}}, q_{\text{rej}})$ with $Q = \{q_0, q_1, q_2, q_{\text{acc}}, q_{\text{rej}}\}$, $\Sigma = \{a, b\}$, $\Gamma = \{a, b, X, \sqcup\}$, and transitions:

State	Read	Write	Move	Next
$q_0$	$a$	$X$	R	$q_1$
$q_0$	$b$	$b$	R	$q_{\text{rej}}$
$q_0$	$\sqcup$	$\sqcup$	R	$q_{\text{acc}}$
$q_0$	$X$	$X$	R	$q_0$
$q_1$	$a$	$a$	R	$q_1$
$q_1$	$b$	$X$	L	$q_2$
$q_1$	$\sqcup$	$\sqcup$	R	$q_{\text{rej}}$
$q_2$	$a$	$a$	L	$q_2$
$q_2$	$X$	$X$	R	$q_0$

(a) (2 pts) Describe what $M$ does. Give a word of length 4 that $M$ accepts, and show the sequence of configurations.

(b) (2 pts) Is $L(M)$ decidable? Justify your answer.

Solution

Part (a) — What M does

$M$ matches $a$'s with $b$'s by marking pairs with $X$. In state $q_0$, it scans right past $X$'s to find the leftmost unmarked $a$, marks it with $X$, then moves right (in $q_1$) to find the leftmost unmarked $b$, marks it with $X$, then sweeps left (in $q_2$) back to the last $X$ and repeats. Accepts when all symbols are marked.

$L(M) = \{a^n b^n \mid n \ge 0\}$

Trace for $w = aabb$:

Step	Configuration	Description
0	$q_0\, aabb$	Start: read $a$, mark $X$
1	$X\, q_1\, abb$	Scan right past $a$'s
2	$Xa\, q_1\, bb$	Found $b$, mark $X$
3	$X\, q_2\, aXb$	Move left past $a$'s
4	$q_2\, XaXb$	Found $X$, move right
5	$X\, q_0\, aXb$	Read $a$, mark $X$
6	$XX\, q_1\, Xb$	Scan right past $X$ (wait — $q_1$ reads $X$?)

Hmm — let me redo this more carefully. The TM has no transition for $q_1$ reading $X$, so we need to check. Looking at the transition table: $q_1$ only handles $a$, $b$, and $\sqcup$. There is no rule for $(q_1, X)$.

Revised understanding: The TM requires all $a$'s to come before all $b$'s (no interleaving of $X$'s in the $a$-block when scanning right in $q_1$). However, $q_0$ skips over $X$'s. Let's re-trace:

Step	Configuration
0	$q_0\; \underline{a}abb$
1	$X\; q_1\; \underline{a}bb$
2	$Xa\; q_1\; \underline{b}b$
3	$X\; q_2\; \underline{a}Xb$
4	$q_2\; \underline{X}aXb$
5	$X\; q_0\; \underline{a}Xb$
6	$XX\; q_1\; \underline{X}b$

At step 6, state $q_1$ reads $X$ — no transition defined. This means M would reject (or be undefined). But wait: The issue is that after marking pairs, the marked $b$ (now $X$) sits between unmarked $a$'s and remaining $b$'s. In $q_1$, there's no rule to skip $X$.

Resolution: We add the missing transition $(q_1, X) \to (X, R, q_1)$ to make the TM work as intended. With this (assumed from the problem statement that $L(M) = \{a^n b^n\}$), the trace continues:

Step	Configuration
6	$XXX\; q_1\; \underline{b}$
7	$XX\; q_2\; \underline{X}X$
8	$XXX\; q_0\; \underline{X}$
9	$XXXX\; q_0\; \underline{\sqcup}$
10	$q_{\text{acc}}$ — accept

$w = aabb$ is accepted. Configurations: $q_0\,aabb \vdash Xq_1 abb \vdash Xaq_1 bb \vdash Xq_2 aXb \vdash q_2 XaXb \vdash Xq_0 aXb \vdash XXq_1 Xb \vdash XXXq_1 b \vdash XXq_2 XX \vdash XXXq_0 X \vdash XXXXq_0 \sqcup \vdash q_{\text{acc}}$

Part (b) — Decidability

$L(M)$ is decidable. $M$ always halts because each pass through the main loop marks at least one $a$ and one $b$ with $X$ (making progress), and the machine rejects if it reaches a blank in $q_1$ (more $a$'s than $b$'s) or reads $b$ in $q_0$ (more $b$'s than $a$'s). Since the tape is finite and each cycle strictly reduces unmarked symbols, $M$ terminates on every input.

Moreover, $L(M) = \{a^n b^n \mid n \ge 0\}$ is decidable (it's a well-known context-free language, and all CFLs are decidable).

Yes, $L(M)$ is decidable. $M$ halts on every input (it's a decider).

Q7 — 7 pts

Let $L = \{\langle M \rangle \mid M \text{ is a TM that accepts at least two distinct strings}\}$.

(a) (2 pts) Prove that $L$ is Turing-recognizable.

(b) (4 pts) Prove that $L$ is undecidable.

(c) (1 pt) Is $L$ co-Turing-recognizable? Prove your answer.

Solution

Part (a) — $L$ is Turing-recognizable

Build a TM $R$ that recognizes $L$:

$R$ = "On input $\langle M \rangle$:

Dovetail: enumerate all pairs $(s_i, s_j)$ with $i \neq j$ from $\Sigma^*$.
For each pair, simulate $M$ on $s_i$ and $M$ on $s_j$ for an increasing number of steps.
If $M$ accepts both $s_i$ and $s_j$ (two distinct strings), accept."

If $M$ accepts ≥ 2 distinct strings, $R$ will eventually find such a pair and accept. If not, $R$ runs forever (which is fine for a recognizer).

$L$ is Turing-recognizable via dovetailing. ✓

Part (b) — $L$ is undecidable

Reduce from $A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ accepts } w\}$.

Suppose $L$ is decidable by some TM $D$. Build a decider $S$ for $A_{\text{TM}}$:

$S$ = "On input $\langle M, w \rangle$:

Construct TM $M'$ = 'On input $x$: run $M$ on $w$. If $M$ accepts, accept.'
Run $D$ on $\langle M' \rangle$.
If $D$ accepts, accept. If $D$ rejects, reject."

Correctness:

If $M$ accepts $w$: $M'$ accepts every input $x$, so $L(M') = \Sigma^*$, which contains infinitely many strings (≥ 2). So $\langle M' \rangle \in L$, and $D$ accepts.
If $M$ does not accept $w$: $M'$ accepts nothing, so $L(M') = \emptyset$, which has 0 strings (< 2). So $\langle M' \rangle \notin L$, and $D$ rejects.

This means $S$ decides $A_{\text{TM}}$, which is a contradiction since $A_{\text{TM}}$ is undecidable.

$A_{\text{TM}} \le_m L$ via the reduction above. $L$ is undecidable. ✓

Part (c) — $L$ is not co-Turing-recognizable

From parts (a) and (b):

$L$ is Turing-recognizable (part a).
$L$ is undecidable (part b).

If $L$ were also co-Turing-recognizable, then by the theorem "$L$ is decidable iff both $L$ and $\overline{L}$ are TR," $L$ would be decidable. Contradiction.

$L$ is TR but not decidable, so $L$ is not co-TR. ✓

Q8 — 3 pts

Let $L = \{\langle M_1, M_2 \rangle \mid L(M_1) \subseteq L(M_2)\}$.

We construct a mapping reduction from $A_{\text{TM}}$ to $\overline{L}$.

The reduction function $F$ works as follows:

$F$ = "On input $\langle M, w \rangle$:

Construct $M_1$ = 'On input $x$: (a) ???'
Let $M_2$ be a TM that rejects everything ($L(M_2) = \emptyset$).
Output $\langle M_1, M_2 \rangle$."

(a) (1 pt) Fill in the blank: what should $M_1$ do on input $x$?

(b) (2 pts) What does this reduction prove about $L$?

Solution

Part (a) — What $M_1$ does

$M_1$ = "On input $x$: run $M$ on $w$. If $M$ accepts, accept."
(The input $x$ is ignored — $M_1$ only cares whether $M$ accepts $w$.)

Correctness of the reduction

If $M$ accepts $w$: $L(M_1) = \Sigma^*$. Since $L(M_2) = \emptyset$, we have $\Sigma^* \not\subseteq \emptyset$, so $\langle M_1, M_2 \rangle \notin L$, meaning $\langle M_1, M_2 \rangle \in \overline{L}$. ✓
If $M$ does not accept $w$: $L(M_1) = \emptyset$. Since $\emptyset \subseteq \emptyset$, we have $\langle M_1, M_2 \rangle \in L$, meaning $\langle M_1, M_2 \rangle \notin \overline{L}$. ✓

So $\langle M, w \rangle \in A_{\text{TM}} \iff F(\langle M, w \rangle) \in \overline{L}$.

Part (b) — What this proves

We have shown $A_{\text{TM}} \le_m \overline{L}$. This gives us:

$\overline{L}$ is undecidable (since $A_{\text{TM}}$ is undecidable) → $L$ is undecidable.
$A_{\text{TM}}$ is TR, so $\overline{L}$ is TR → $L$ is co-TR.
$A_{\text{TM}}$ is not co-TR, so $\overline{L}$ is not co-TR → $L$ is not TR.

$L$ is undecidable, co-Turing-recognizable, and not Turing-recognizable.

Q9 — 7 pts

BALANCED PARTITION

Instance: A finite set $S$ of positive integers and a target $t$.

Question: Can $S$ be partitioned into two subsets $S_1, S_2$ such that $|\Sigma S_1 - \Sigma S_2| \le t$?

(a) (2 pts) Prove that BALANCED PARTITION $\in$ NP.

(b) (1 pt) Give a yes-instance of 3SAT with $|U| = 3$ variables and $|C| = 2$ clauses.

(c) (2 pts) Consider the following reduction from 3SAT to BALANCED PARTITION:

Given a 3SAT instance $(U, C)$ with $|U| = n$ variables and $|C| = m$ clauses: for each variable $u_i$, create two numbers $v_i$ and $\bar{v}_i$. Set $v_i = 2^i$ and $\bar{v}_i = 2^i$. For each clause $c_j$, add $2^{n+j}$ to every number whose corresponding literal appears in $c_j$. Set $t = 0$.

Apply this reduction to the 3SAT instance from part (b). Show the resulting numbers.

(d) (1 pt) Is the result from part (c) a yes-instance of BALANCED PARTITION? Explain.

(e) (1 pt) The reduction above has a fundamental flaw. What is it, and how can it be fixed?

Solution

Part (a) — BALANCED PARTITION $\in$ NP

Certificate: A partition $(S_1, S_2)$ of $S$.

Verifier:

Check that $S_1 \cup S_2 = S$ and $S_1 \cap S_2 = \emptyset$.
Compute $\text{sum}_1 = \sum_{s \in S_1} s$ and $\text{sum}_2 = \sum_{s \in S_2} s$.
Accept iff $|\text{sum}_1 - \text{sum}_2| \le t$.

All steps run in polynomial time (summing $|S|$ numbers, one comparison).

Certificate is the partition. Verification is polynomial. BALANCED PARTITION $\in$ NP. ✓

Part (b) — 3SAT yes-instance

$U = \{x_1, x_2, x_3\}$, $C = \{c_1, c_2\}$ where:

$c_1 = (x_1 \lor x_2 \lor \neg x_3)$
$c_2 = (\neg x_1 \lor x_3 \lor x_2)$

Satisfying assignment: $x_1 = T, x_2 = T, x_3 = T$.
$c_1 = T \lor T \lor F = T$. $c_2 = F \lor T \lor T = T$. ✓

Part (c) — Apply the reduction

Variables: $n = 3$, Clauses: $m = 2$. Bit positions: variables use bits 1–3, clauses use bits 4–5.

$c_1 = (x_1 \lor x_2 \lor \neg x_3)$: literals $x_1, x_2, \neg x_3$.

$c_2 = (\neg x_1 \lor x_3 \lor x_2)$: literals $\neg x_1, x_2, x_3$.

Number	Literal	$2^i$ (var)	$+2^4$ ($c_1$)	$+2^5$ ($c_2$)	Total
$v_1$	$x_1$	2	+16 (in $c_1$)	—	18
$\bar{v}_1$	$\neg x_1$	2	—	+32 (in $c_2$)	34
$v_2$	$x_2$	4	+16 (in $c_1$)	+32 (in $c_2$)	52
$\bar{v}_2$	$\neg x_2$	4	—	—	4
$v_3$	$x_3$	8	—	+32 (in $c_2$)	40
$\bar{v}_3$	$\neg x_3$	8	+16 (in $c_1$)	—	24

$S = \{18, 34, 52, 4, 40, 24\}$, $t = 0$.

Numbers: $v_1 = 18, \bar{v}_1 = 34, v_2 = 52, \bar{v}_2 = 4, v_3 = 40, \bar{v}_3 = 24$. Target $t = 0$.

Part (d) — Is it a yes-instance?

Total sum $= 18 + 34 + 52 + 4 + 40 + 24 = 172$. For $t = 0$, we need each half to sum to exactly 86.

Intended partition (from the truth assignment $x_1 = T, x_2 = T, x_3 = T$): $S_1 = \{v_1, v_2, v_3\} = \{18, 52, 40\}$, sum = 110. $S_2 = \{\bar{v}_1, \bar{v}_2, \bar{v}_3\} = \{34, 4, 24\}$, sum = 62. Difference = 48 ≠ 0.

But maybe a different partition works? Try $S_1 = \{34, 52\} = 86$, $S_2 = \{18, 4, 40, 24\} = 86$. Yes! This gives a balanced partition.

Yes, it is a yes-instance — but the balanced partition does not correspond to the truth assignment. This is exactly the flaw (see part e).

Part (e) — The flaw

The flaw: $v_i$ and $\bar{v}_i$ have the same base value $2^i$. Since they are interchangeable in the variable-bit positions, putting $v_i$ in $S_1$ vs $\bar{v}_i$ in $S_1$ doesn't force a consistent truth assignment. The partition can mix $v_i$ and $\bar{v}_i$ freely without encoding "true vs false."

Fix: Make $v_i \neq \bar{v}_i$ in their base values, or add additional distinguishing bits so that exactly one of $\{v_i, \bar{v}_i\}$ must go in each partition half. For example, give each variable a unique pair of bits: $v_i$ gets bit $2i-1$ and $\bar{v}_i$ gets bit $2i$, ensuring the partition must choose one per variable.

Flaw: $v_i = \bar{v}_i = 2^i$ makes them interchangeable — the partition doesn't encode a truth assignment. Fix: use distinct base values to force exactly one of $v_i, \bar{v}_i$ per side.

Q10 — 6 pts

For each statement, determine if it is true or false. Justify your answer. Unjustified answers receive 0 points. Wrong justifications receive negative points.

(a) (1 pt) The class of context-free languages is closed under intersection.

(b) (2 pts) If $A$ is decidable and $B$ is Turing-recognizable, then $A \cap B$ is Turing-recognizable.

(c) (1 pt) Every context-free language is decidable.

(d) (2 pts) If $L$ is NP-complete and $L \in P$, then P = NP.

Solution

Part (a) — CFLs closed under intersection?

False.

Counterexample:

$L_1 = \{a^i b^j c^k \mid i = j\}$ is context-free (push $a$'s, match with $b$'s, ignore $c$'s).
$L_2 = \{a^i b^j c^k \mid j = k\}$ is context-free (ignore $a$'s, push $b$'s, match with $c$'s).
$L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$, which is not context-free (classic CFL pumping lemma example).

Part (b) — Decidable $\cap$ TR = TR?

True.

Build a TM $T$ for $A \cap B$:

$T$ = "On input $w$:

Run the decider for $A$ on $w$. If it rejects, reject.
If it accepts, run the recognizer for $B$ on $w$. If it accepts, accept. (If $B$'s recognizer loops, $T$ loops — this is fine for a recognizer.)"

Key: we run the decider for $A$ first because it always halts. This filters out strings not in $A$ before we risk looping on $B$.

Part (c) — Every CFL is decidable?

True.

Every CFL has a CFG. Convert to Chomsky Normal Form (CNF). The CYK algorithm decides membership in $O(n^3)$ time. Since CYK always terminates with accept/reject, every CFL is decidable.

Part (d) — NP-complete + in P $\Rightarrow$ P = NP?

True.

By definition of NP-completeness:

$L \in$ NP.
Every language $A \in$ NP satisfies $A \le_P L$ (polynomial-time reduction).

If $L \in P$, then for any $A \in$ NP: compose the polynomial-time reduction from $A$ to $L$ with the polynomial-time algorithm for $L$. This gives a polynomial-time algorithm for $A$. So every $A \in$ NP is in P, meaning NP $\subseteq$ P. Since P $\subseteq$ NP trivially, P = NP.

Score Yourself

Question	Topic	Points
Q1a	DFA accept states	1
Q1b	NFA Kleene star	4
Q2	Subset construction	3
Q3	Regex	2
Q4	Pumping lemma	3
Q5a	CNF conversion	2
Q5b	PDA construction	3
Q6a	TM trace	2
Q6b	Decidability	2
Q7a	TR proof	2
Q7b	Undecidability	4
Q7c	Co-TR	1
Q8a	Fill-in reduction	1
Q8b	Reduction analysis	2
Q9a	NP membership	2
Q9b	3SAT instance	1
Q9c	Reduction application	2
Q9d	Yes/no instance	1
Q9e	Reduction flaw	1
Q10a	CFL intersection	1
Q10b	Decidable ∩ TR	2
Q10c	CFL decidable	1
Q10d	NPC + P = NP	2
Total		/45

State	0	1
\(q_0\) (start)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_2\)	\(q_0\)
\(q_2\) (accept)	\(q_2\)	\(q_2\)

State	\(a\)	\(b\)
\(q_0\) (start)	\(\{q_0, q_1\}\)	\(\{q_0\}\)
\(q_1\) (accept)	\(\emptyset\)	\(\{q_1\}\)

DFA State	\(a\)	\(b\)	Accept?
\(\{q_0\}\)	\(\{q_0, q_1\}\)	\(\{q_0\}\)	No
\(\{q_0, q_1\}\)	\(\{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}\)	\(\{q_0\} \cup \{q_1\} = \{q_0, q_1\}\)	Yes

State	Read	Write	Move	Next
\(q_0\)	\(a\)	\(X\)	R	\(q_1\)
\(q_0\)	\(b\)	\(b\)	R	\(q_{\text{rej}}\)
\(q_0\)	\(\sqcup\)	\(\sqcup\)	R	\(q_{\text{acc}}\)
\(q_0\)	\(X\)	\(X\)	R	\(q_0\)
\(q_1\)	\(a\)	\(a\)	R	\(q_1\)
\(q_1\)	\(b\)	\(X\)	L	\(q_2\)
\(q_1\)	\(\sqcup\)	\(\sqcup\)	R	\(q_{\text{rej}}\)
\(q_2\)	\(a\)	\(a\)	L	\(q_2\)
\(q_2\)	\(X\)	\(X\)	R	\(q_0\)

Step	Configuration	Description
0	\(q_0\, aabb\)	Start: read \(a\), mark \(X\)
1	\(X\, q_1\, abb\)	Scan right past \(a\)'s
2	\(Xa\, q_1\, bb\)	Found \(b\), mark \(X\)
3	\(X\, q_2\, aXb\)	Move left past \(a\)'s
4	\(q_2\, XaXb\)	Found \(X\), move right
5	\(X\, q_0\, aXb\)	Read \(a\), mark \(X\)
6	\(XX\, q_1\, Xb\)	Scan right past \(X\) (wait — \(q_1\) reads \(X\)?)

Step	Configuration
0	\(q_0\; \underline{a}abb\)
1	\(X\; q_1\; \underline{a}bb\)
2	\(Xa\; q_1\; \underline{b}b\)
3	\(X\; q_2\; \underline{a}Xb\)
4	\(q_2\; \underline{X}aXb\)
5	\(X\; q_0\; \underline{a}Xb\)
6	\(XX\; q_1\; \underline{X}b\)

Step	Configuration
6	\(XXX\; q_1\; \underline{b}\)
7	\(XX\; q_2\; \underline{X}X\)
8	\(XXX\; q_0\; \underline{X}\)
9	\(XXXX\; q_0\; \underline{\sqcup}\)
10	\(q_{\text{acc}}\) — accept

Number	Literal	\(2^i\) (var)	\(+2^4\) (\(c_1\))	\(+2^5\) (\(c_2\))	Total
\(v_1\)	\(x_1\)	2	+16 (in \(c_1\))	—	18
\(\bar{v}_1\)	\(\neg x_1\)	2	—	+32 (in \(c_2\))	34
\(v_2\)	\(x_2\)	4	+16 (in \(c_1\))	+32 (in \(c_2\))	52
\(\bar{v}_2\)	\(\neg x_2\)	4	—	—	4
\(v_3\)	\(x_3\)	8	—	+32 (in \(c_2\))	40
\(\bar{v}_3\)	\(\neg x_3\)	8	+16 (in \(c_1\))	—	24