Problem 29.
Problem 30.
Problem 31.
Problem 32.
is not regular.
Problem 33.
COMS 331: Theory of Computing, Spring 2021 Homework Assignment 5
Due at 10:00PM, Wednesday, March 3, on Gradescope.
Prove or disprove: If A and A ∩ B are regular, then B is regular.
Prove or disprove: If A is regular and A ∩ B is not regular, then B is not regular.
Prove or disprove: If A is regular and B is not regular, then A ∩ B is not regular.
Prove that the language
A = {x ∈ {0,1}∗ |#(0,x) = #(1,x)}
Prove that the language
A = {x ∈ {0,1}∗ |#(01,x) = #(10,x)}
is regular. (Here, for a, b ∈ {0, 1}, #(ab, x) is the number of a’s in x that are immediately followed by b.)
Recall that the canonical equivalence relation of a language A ⊆ Σ∗ is the binary relation ≡A on Σ∗ defined by
x ≡A y if and only if, for all z ∈ Σ∗, [xz ∈ A ⇐⇒ yz ∈ A]. Problem 34. (a) What are the equivalence classes of ≡A if A = {0n1n | n ∈ N}?
(b) Prove that your answer to (a) is correct.
1
(c) Explain why your answer to (a) implies that A is not regular.
Problem 35. Define Σ, top, and bottom as in Problem 19. Prove: If A, B ⊆ {0, 1}∗ are regular, then the language
is regular.
A ∗
B ={z∈Σ |top(z)∈Aandbottom(z)∈B}
2