Problem 1: For two languages L1 and L2 over the alphabet Σ, we define the quotient of L1 and L2 to be the language
L1/L2 := {x ∈ Σ∗ | for some y ∈ L2 we have xy ∈ L1} .
Show that if L1 is regular, then L1/L2 is regular.
Problem 2: Let M = (Q, Σ, q0, A, δ) be an NFA. Show that if Si ⊆ Q for every i ∈ I, then
UΛ(Si) = Λ(∪i∈ISi).
i∈I
Problem 3: Let M = (Q, Σ, q0, A, δ) be an NFA. Which of the following, if any, would be a correct substitute for the second part of the definition of δ∗? Either prove that it is correct, or explain why it is incorrect.
(a) δ∗(q, ay) = U δ∗(r, y) whenever a ∈ Σ, y ∈ Σ∗, q ∈ Q.
r∈Λ(δ(q,a))
(b) δ∗(q, ay) = U δ∗(r, y) whenever a ∈ Σ, y ∈ Σ∗, q ∈ Q.
r∈δ∗(q,a)
(c) (Extra credit: 4 pts.) Give a proper recursive definition of δ∗(q, ay) for a ∈ Σ, y ∈ Σ∗, and q ∈ Q.
Problem 4: Suppose M is an NF.A acceptingΣ L ⊆ Σ∗. Explain how to modify M to obtain an NFA accepting rev(L) := xR | x ∈ L where xR denotes the reverse of string x.
Problem 5: The order of a regular nonempty language L is defined to be the smallest integer k for which Lk = Lk+1 if there is such a k, and ∞ otherwise.
(a) Find the order of the regular language L1 = {Λ} ∪ {aa} {aaa}∗, and justify it. Tip: Compute the first few powers of this language starting with the 0th power. As every string in this language can contain only a's, to describe them it is enough to describe how many a's they have (be precise in your description and justify it!). Briefly explain what strings each power of the language has, and find the smallest k satisfying the definition.
(b) Show that if Lk = Lk+1 for some natural number k, then Λ ∈ L, and consequently, Ln ⊆ Ln+1 for every natural number n.
(c) Show that if Lk = Lk+1 for some natural number k, then Ln+1 = Ln+2 for every integer n ≥ k.
(d) Show that if Lk = L∗ for some natural number k, then Λ ∈ L.
(e) Let k be a natural number. Show that Lk = L∗ if and only if Lk = Lk+1.
(f) Show that the order of L is finite if and only if there is a natural number k so that Lk = L∗, and in this case the order of L is the smallest k such that Lk = L∗.
Attachment:- Theory of computation problem.rar