Let L1 and L2 be two languages over alphabet Σ={x,y} as given below: L1=Set of…

Part (a): Language L₁

Regular Expression

(x+y)∗ (xx+yy)

DFA Construction

To accept strings whose last two symbols are same, we need to remember the last two symbols.

Let the DFA be M = (Q, Σ, δ, q₀, F)

• Q = {q₀, q₁, q₂, q₃, q₄}

• Σ = {x, y}

• Start state = q₀

• Final states F = {q₃, q₄}

Transition Table

Explanation

• q₃ corresponds to last two symbols = xx

• q₄ corresponds to last two symbols = yy

• Hence both are accepting states

Part (b): Language L₂

Interpretation

Strings where:

• First two symbols are anything

• Third symbol must be x

• After that at least three symbols

Regular Expression

(x+y)(x+y)x(x+y)(x+y)(x+y)(x+y)∗

DFA Construction

Let the DFA be M = (Q, Σ, δ, q₀, F)

• Q = {q₀, q₁, q₂, q₃, q₄, q₅, q₆, qd}

• Σ = {x, y}

• Start state = q₀

• Final state F = {q₆}

Transition Table

Explanation

• After reading two symbols, the third symbol must be x

• If not, the machine goes to dead state qd

• After that, at least three more symbols are required

• Hence q₆ is the only accepting state