Is the set of quadratic-length strings over {0} a regular set? Is it a CFL? Prove both.

 

Answer:

• The set of quadratic length strings over {0} is not a CFL, which automatically implies that it is not regular as well.
• To prove that it is not a CFL, apply the pumping lemma for CFLs as follows.
• Let the pumping length be P≥1
• Consider the word W = 0^{(P^2)}
• which has quadratic length.
• Consider any breakup of the word
• W=UVXYZ
• with |VXY|≤P
• And |VY|≥1
• Then this implies that vy = 0ⁱ
• for some 1≤i≤P as implied by the two constraints
• Consider the pumped up word w' = uv²xy²z = 0^{{p^2 + i}.}
• Now note that as i≥ 1,
• this implies that i > 0,
• hence, P² + i >P²
• so, as i ≤p, it implies that P²+ i ≤ P² +P
• Now consider that (P+1)² = P² + 2P+ 1.
• As P ≥ 1, this implies P < 2P,
• therefore P < 2P + 1.
• Therefore
• P² + i ≤ P² + P < P² + 2p + 1 = (P+1)²
• The two observations above give that P² < P² + i < (P+1)²
• As P² +i
• is between two consecutive squares but not equal to any of them, this implies that it cannot be a perfect square itself.
• This implies that
• is not a quadratic length string.
• Hence, it is not in the given set.
• As pumping up produces a word that is not in the set, this implies that the set doesn't satisfy the pumping lemma for CFLs, proving that it is not a CFL.
• Note that as each regular set is a CFL as well, this implies that the given set is not regular either.