Question: Prove that Language is not regular.
0

$L = {0°10° for \ \ n = 0, 1, 2, …..}$

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015

 modified 3.3 years ago  • written 3.3 years ago by Pooja Joshi • 740
0

Assume L is regular with pumping constant k.

Consider $w = 0°10° ∈ L$.

By Pumping Lemma, $w = xyz, \ \ with \ \ |xy| ≤ k, |y| \gt 0$.

Because $|xy| ≤ k$, y must consist entirely of 0's.

By Pumping Lemma, then also $0^{k-|y|} 10^{k^2} ∈ L$, which is a contradiction.

Hence, the language $L = {0°10° for \ \ n = 0, 1, 2,...}$ is not regular.