Theory of Computing (csc520)

CSC 520 Spring 2020 HW #1b

1.b (13 points) ∑ = {a}, L = { w : w = aⁿ, n = m², m ≥ 0}. For example: aaaa ∈ L because |aaaa| = 4, and 4 = 2²; a²⁵ ∈ L because 25 = 5²; aaa ∉ L because |aaa| = 3, and 3 is not the square of a natural number.

Use the RL pumping theorem to show that L ∉ RLs.

CSC 520 Spring 2020 HW #1b Page 1