Solution

δ (q, ϵ) = q, δ (q, w a) = δ (δ (q, w), a) .

The accepted language is

L (D) = {w \in Σ^{*} : δ (q_{0}, w) \in F} .

δ (q, w)

is the set of all states reachable from

q

while reading

w

; recursively,

δ (q, ϵ) = {q}, δ (q, w a) = ⋃_{r \in δ (q, w)} δ (r, a) .

Thus

L (N) = {w \in Σ^{*} : δ (q_{0}, w) \cap F \neq = \emptyset} .

P (Q)

, initial state

{q_{0}}

, transition

\overline{δ} (S, a) = ⋃_{q \in S} δ (q, a),

and accepting states

{S \subseteq Q : S \cap F \neq = \emptyset}

. Induction on

∣ w ∣

gives

\overline{δ} ({q_{0}}, w) = δ (q_{0}, w),

so the two automata accept exactly the same language. If

∣ Q ∣ = m

and

F

has one state, exactly

2^{m - 1}

of the

2^{m}

subset states contain it and are accepting, including states that may be unreachable.

Solved by gpt-5.6-sol high.

 Ancestors (10)