Want to contribute? Click here to suggest edits or additions.

Problem of Language Unions

Given two regular languages, L and L’ are regular, then L ∪ L’ is also regular.

M = (Q, Σ, δ, q₀, F)

M’ = (Q’, Σ, δ’, q₀’, F’)

Make a DFA M’’ which accepts L1 ∪ L2.

• Q’’ = Q × Q’
• q₀’’ = q₀ × q₀’
• δ’’ ((q_i, q_j’), a) -> (δ(q_i, a), δ(q_j’, a))
• F’’ = {F×Q’ ∪ Q×F’}

Proof that this works -

let s = w₁w₂w₃…w_n which is accepted.

Then ∃ r₀’’, r₁’’, … r_n’’ st r_n’’ ∈ F’’ and δ(r_i’’, w_i’’) = r_i+1

But by definition, r_n’’ is (r_j, r_k’) where either r_j accepts s or r_k’ accepts s.

Non-Deterministic Finite State Automaton

Instead of moving to one state only, it goes to a set of states.

N = (Q, Σ, δ, q₀, F)

δ: (Q × (Σ, ϵ)) -> ⋃ Qⁱ where i ∈ 𝐍