Reference no: EM13322884

1. Construct a DFA that recognizes each of the following languages. Unless otherwise noted we are assuming that ω ∈ {0,1}*. (A drawing of a state diagram is sufficient.)

(a)  {ω| the length of w is at least 4 }

(b)   {ωl ω contains the substring 0101}

(c)   { ω ∈ {3, 4}* when the characters of to are added up, their sum is divisible by seven. }

(d) The language represented by the regular expression (01 U 10)*.

2. Suppose that A is a regular language, with elements belonging to E* for some alphabet Σ*. Show that the following languages are also regular:

(a) A' = {ω ∈ Σ*|ω ∈ A}.

(b) A^R = {ω^R ∈ Σ*| ω ∈ A}. Where ω^R represents the reverse of ω, i.e. if ω = ω₁ω₂......w_n then ω^R = ω_nω_n-1.......ω₁.

(c) A= {ω ∈ Σ*| ω = x₁x₂x₃......x_ky_k where x₁x₂........x_ky_k where x₁x₂........x_k ∈ A y₁y₂ ........y_k ∈ A and each x_i, y_i ∈ Σ

3. Suppose A is a regular language and let B be any language. Show that the following language is also regular A/B = {ω|ωx ∈ A for some x ∈ B}.