Homework

Question 1

All expressions are over the alphabet $\Sigma=\{0,1\}$. For each expression $R$, provide:

• 2 example strings in L(R)
• 2 example strings not in L(R)
• A brief English description of L(R)
• A simpler regular expresson R' where L(R') = L(R)

Expressions:

1. Ra = 1 · ∅ · 0* ∪ 1* · ε · 0
2. Rb = ((00)* ∪ (11)*)* · (0* ∪ 1*)
3. Rc = (11 ∪ (00 ∪ (ε ∪ 00)))* 11*

Question 2

Let M be the DFA with states Q = {q₁, q₂, q₃, q₄, q₅}
, input alphabet Σ = {u, d}
, start state q₂
, and accept states F = {q₂}.

δ	u	d
q₁	q₅	q₂
q₂	q₁	q₃
q₃	q₂	q₄
q₄	q₃	q₅
q₅	q₄	q₁

Tasks:

1. Give the computation for input uududu. Is it in L(M)?
2. Draw a state transition diagram.
3. Give 2 example strings of length ≥ 5 that are accepted.
4. Give 2 example strings of length ≥ 5 that are not accepted.
5. Provide a high-level English description of M (max 2 sentences).