0
Prove that Language is not regular.

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

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015

0
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.

0