COM S 331 Theory of Computation Homework 4 Due Wed 2/20/19 10:00 PM
In the lectures we defined the canonical equivalence relation ≡A of a language A ⊆ Σ∗
by
for all x,y ∈ Σ∗.
x≡A y ⇐⇒ (∀z∈Σ∗)[xz∈A ⇐⇒ yz∈A]
Question 25. What are the ≡A-equivalence classes of the language A=0nx|n∈Z+, x∈{0,1}∗, and#(0,x)≥n?
Is A regular? Explain clearly.
Question 26. What are the ≡B-equivalence class of the language B=0nx|n∈Z+, x∈{0,1}∗, and#(0,x)≤n)?
Is B regular? Explain clearly.
Question 27. Prove that there is no three-state DFA M such that
L(M) = x ∈ {0,1}∗ | #(0,x) is even and #(1,x) is even. Question 28. Design a DFA M such that
L(M) = {x1000 | x ∈ {0,1}∗}.
Question 29. Let A = x ∈ {0,1}∗ | #(01,x) = #(10,x), where, for a,b ∈ {0,1}∗, #(ab, x) is the number of places in x where an a is immediately followed by a b.
Is a regular? Prove that your answer is correct. 1
COM S 331 Theory of Computation Homework 4 2 Question 30. Let A = 0nx0n | n ∈ Z+ and x ∈ {0, 1}∗. Prove that A is regular.
A Kamae-Weiss language is a language A ⊆ Σ∗ such that A is the union of finitely many ≡A-equivalence class.
Question 31. Prove that every regular language is Kamae-Weiss. Question 32. Prove that the language
A=u110n10n |u∈{0,1}∗ andn∈N is Kamae-Weiss, but not regular.