COMS 331: Theory of Computing, Spring 2021 Homework Assignment 6
Due at 10:00PM, Wednesday, March 10, on Gradescope.
For problems 36-40, prove that the indicated languages are not regular without using the pumping
lemma. (Proofs using the pumping lemma will receive credit if they are completely correct; they will not be eligible for partial credit.)
Problem 36. {0m1n |m is even or m > n}. Problem 37. {0k1m0n | n = k + m}.
Problem 38. {x ∈ {0, 1}∗ | |x| is a perfect square}. Problem 39. {0m1n | gcd(m, n) = 1}.
Problem 40. {xx | x ∈ {0, 1}∗}.
Problem 41. Give the formal description for a Turing machine that accepts the language
{x | the #(1, x)-th symbol of x is 1}
with Σ = {0, 1}.
Problem 42. Give the formal description for a Turing machine that accepts the language
with Σ = {0, 1}.
{1m0k |0 ≤ k < m}
1