L(D1) = “ends with 1”. L(D2) = “even number of 0’s”. Union: ends with 1 OR even number of 0’s.

Start: (p0, r0). F = (F1 × Q2) ∪ (Q1 × F2) = {(p1, r0), (p1, r1), (p0, r0), (p1, r0)} = {(p0, r0), (p1, r0), (p1, r1)}.

4 states, all reachable. Only (p0, r1) is non-accepting (ends with 0 AND odd number of 0’s).

N1: q0 ⟶a q1 (q1 accepting, self-loop on a). N2: r0 ⟶b r1 (r1 accepting, self-loop on b).

Concatenation: add ε from q1 to r0. Remove q1 as accept state. Accept state: r1 only.

Result: q0 ⟶a q1 ⟶ε r0 ⟶b r1, with self-loops a on q1 and b on r1.

(a) Reverse NFA:

Original transitions: q0 ⟶0 q0, q0 ⟶1 q1, q1 ⟶0 q1, q1 ⟶1 q0.

Reversed transitions: q0 ⟶0 q0, q0 ⟶1 q1, q1 ⟶0 q1, q1 ⟶1 q0. (Identical — this automaton is symmetric.)

Add new start q_s with ε to q1 (old accept). New accept state: q0 (old start).

(b) Subset construction:

Start: E({q_s}) = {q_s, q1}.

{q_s, q1} on 0: δ(q1, 0) = {q1}. → {q1}.

{q_s, q1} on 1: δ(q1, 1) = {q0}. → {q0}. ✓

{q1} on 0: {q1}. On 1: {q0}. ✓

{q0} on 0: {q0}. ✓ On 1: {q1}.

DFA: 3 states. Start: {q_s, q1}. Accept states: {q0} (contains old start q0).

L(D) = “odd number of 1’s” which equals its own reverse, so L(D)^R = L(D).

Start: E({q0}) = {q0, q1}  (q0 ⟶ε q1).

{q0, q1} on a: δ(q0, a) ∪ δ(q1, a) = {q0} ∪ ∅ = {q0}. E({q0}) = {q0, q1}.

{q0, q1} on b: δ(q0, b) ∪ δ(q1, b) = ∅ ∪ {q2} = {q2}. E({q2}) = {q2}. ✓

{q2} on a: {q2}. ✓   {q2} on b: ∅ = dead state.

∅ on a: ∅. ∅ on b: ∅. (Trap state.)

3 reachable DFA states: {q0, q1} (start), {q2} (accept), ∅ (trap).

Yes, SNFAs recognize exactly the regular languages.

Regular → SNFA: Given any regular language L, build a DFA D for L. Since D is deterministic, every word has exactly one computation path. Accepted words have exactly 1 accepting path; rejected words have 0. So D is a valid SNFA with L(D-as-SNFA) = L(D) = L.

SNFA → regular: Given SNFA S, we show L(S) is regular. The machine S is structurally an NFA. Let L_≥1 = {w : at least one path accepts} (the standard NFA language) and L_≥2 = {w : at least two paths accept}. Both are regular: L_≥1 by standard NFA-to-DFA conversion, and L_≥2 by a product construction that tracks two independent paths through S. Then L(S) = L_≥1 \ L_≥2, which is regular since regular languages are closed under set difference.

Exam shortcut (2-point answer): “Every DFA is an SNFA (one path per word). For the other direction, the SNFA language can be captured by a modified subset construction that tracks path counts, yielding a finite DFA. Therefore SNFAs recognize exactly the regular languages.”

Yes, MNFAs recognize exactly the regular languages.

DFA → MNFA: Every DFA is already an MNFA. A DFA has exactly one computation path per word. If the word is accepted, 1/1 = 100% of paths accept (majority). If rejected, 0/1 = 0% (not majority). So L(DFA-as-MNFA) = L(DFA).

MNFA → DFA: Given MNFA M, use subset construction but track the fraction of paths in each state. The DFA state is a distribution over M’s states. Accept if >50% of the distribution weight is in M’s accept states. Since this distribution is determined by the state set (with multiplicities bounded by the subset construction), the result is a finite DFA.

The key insight is the same as RNFA/SNFA: the DFA is the bridge. Any DFA is trivially a valid MNFA (one path = majority), and the subset construction can be adapted to capture majority semantics.

Removing q1. Self-loop on q1: b. Incoming to q1: q0 ⟶b q1. Outgoing from q1: q1 ⟶a q0, q1 ⟶ε q_a.

R(q0, q0): a | b · b* · a = a | bb*a

R(q0, q_a): ∅ | b · b* · ε = bb*

Resulting GNFA: q_s ⟶ε q0, q0 ⟶(a|bb*a) q0, q0 ⟶bb* q_a.

Full regex (removing q0 next): (a | bb*a)* bb* = (a | b⁺a)* b⁺.

No. Regular languages are closed under complement (flip accept/reject states of the DFA). So any RE-with-complement describes a regular language, which has a standard RE.

Proof: Given RE-with-complement expression E, convert to DFA (recursively handling complement by flipping accept states), then convert DFA back to RE via GNFA state elimination.

This grammar is NOT ambiguous. (Trick question.)

L(G) = {a} ∪ {a^mbⁿ | m ≥ 0, n ≥ 1}. From S → AB: A generates a* (zero or more a’s) and B generates b⁺ (one or more b’s). For any word a^mbⁿ, the split between A and B is unique (A produces all a’s, B produces all b’s). S → a only produces “a”, which cannot come from S → AB (since B → bB | b cannot derive ε, any word from AB contains at least one b).

Every word in L(G) has exactly one leftmost derivation. Not ambiguous.

START: S appears in aSb → Add S0 → S.

TERM: Replace terminals in mixed rules: S → U_aSU_b | AB, A → U_aA | a, B → U_bB | ε.

BIN: S → U_aT1 | AB, T1 → SU_b.

DEL: B is nullable. S → AB ⇒ add S → A. S0 → S (not nullable unless S is). Is S nullable? S → AB → Aε → A. A → aA | a ⇒ A not nullable. So S not nullable.

Remove B → ε. Add U_bB with B removed: nothing new (U_b alone would be a terminal rule, already have U_b → b).

Result: S0 → S, S → U_aT1 | AB | A, T1 → SU_b, A → U_aA | a, B → U_bB, U_a → a, U_b → b.

UNIT: S0 → S: replace with S’s rules → S0 → U_aT1 | AB | A. S → A: replace with A’s rules → S → U_aT1 | AB | U_aA | a. S0 → A: replace → S0 → U_aT1 | AB | U_aA | a.

Final CNF: S0 → U_aT1 | AB | U_aA | a  /  S → U_aT1 | AB | U_aA | a  /  T1 → SU_b  /  A → U_aA | a  /  B → U_bB  /  U_a → a  /  U_b → b

Union: S → S1 | S2.

S1: a^mbⁿcⁿ with m ≥ 1. The a’s are independent, the b’s and c’s match.

S1 → A1 B1, A1 → aA1 | a, B1 → bB1c | ε.

S2: aⁿbⁿc^m with m ≥ 1. The a’s and b’s match, the c’s are independent.

S2 → B2 C2, B2 → aB2b | ε, C2 → cC2 | c.

Idea: push TWO stack symbols per a, pop one per b. Then n a’s push 2n symbols, and 2n b’s pop them all.

States: q_start, q_push, q_pop, q_acc.

• q_start: push $, ε → q_push
• q_push: read a → push AA (two symbols). ε → q_pop
• q_pop: read b, pop A. If top is $ → pop $, go to q_acc
• q_acc: accept

Alternative: push one A per a, then for each b pop half an A (i.e., use nondeterminism). The double-push is cleaner.

Strategy: repeatedly cross off one a and one b.

1. Scan right from left end. Find the first unmarked a → mark it (write X). Move right.
2. Skip over remaining a’s and marked b’s (Y’s). Find first unmarked b → mark it (write Y). Move left.
3. Scan left back to the marked a (X). Move right to find next unmarked a.
4. Repeat until all a’s are marked. Then verify all b’s are also marked.
5. If blank/Y found instead of a → scan right to verify no unmarked b’s remain → accept.
6. If structure is wrong at any point (e.g., b before all a’s crossed) → reject.

States: q_start (find a), q_seekb (scan right for b), q_return (scan left), q_verify (check all matched), q_acc, q_rej.

(a) w = ε. Trace:

1. q0 ␣ → write a, move R, stay q0. Config: a q0 ␣
2. q0 ␣ → write a, move L, go q1. Config: q1 a a
3. q1 reads a → write a, move R, go q0. Config: a q0 a
4. q0 reads a → write a, move R, stay q0. Config: a a q0 ␣

The TM keeps extending the tape with a’s and bouncing — infinite loop.

In fact, for ANY input w, M eventually hits a blank, writes a, bounces, and loops. M never accepts or rejects.

(b) L(M) = ∅. M never reaches an accept state on any input. The empty language is decidable (a decider that always rejects decides it).

Track (a-parity, b-parity). 4 states: (even,even), (even,odd), (odd,even), (odd,odd).

Start: (even, even). Accept: (odd, even).

This is itself a product construction of “odd a’s” × “even b’s”.

No ε-transitions. Start: {q0}.

{q0} on a: {q0, q1}. {q0} on b: {q0}.

{q0, q1} on a: δ(q0,a) ∪ δ(q1,a) = {q0,q1} ∪ {q2} = {q0,q1,q2}. On b: {q0} ∪ ∅ = {q0}.

{q0,q1,q2} on a: {q0,q1} ∪ {q2} ∪ ∅ = {q0,q1,q2}. On b: {q0} ∪ ∅ ∪ {q2} = {q0,q2}.

{q0,q2} on a: {q0,q1} ∪ ∅ = {q0,q1}. On b: {q0} ∪ {q2} = {q0,q2}.

4 reachable states. L(N) = “contains aa as a substring, possibly followed by anything” — more precisely: contains “aa” somewhere, and once matched, stays accepting on b’s.

Strategy: Build a DFA for “does not contain aba,” then read off the regex.

DFA states track progress toward the forbidden pattern:

• s0 (start / last was b): s0 ⟶a s1, s0 ⟶b s0
• s1 (last was a): s1 ⟶a s1, s1 ⟶b s2
• s2 (saw “...ab”): s2 ⟶a s_dead, s2 ⟶b s0
• s_dead (found aba): s_dead ⟶a,b s_dead

Accept states: {s0, s1, s2}. Key constraint: after a block of a’s, the following b-block must have ≥2 b’s before any a can reappear (one b goes to s2, a second b returns to s0).

Valid strings: blocks of a⁺ separated by bb⁺ (at least 2 b’s), with optional leading/trailing b’s and a’s. Can end mid-pattern at s1 (trailing a’s) or s2 (trailing a⁺b).

R = b*(a⁺bb⁺)*(a⁺b?)?

Verify: “aba” requires a⁺bb⁺ between the a-blocks, but only one b — rejected ✓. “abba” = a⁺bb⁺ · a⁺ ✓. “bab” = b · a⁺b (ending at s2) ✓. “b” = b ✓. ε ✓.