# Pumping Lemma

Printable View

• April 28th 2009, 12:41 PM
VENI
Pumping Lemma
Show that the set $\{0^{2n}1^{n}\}$ is not regular using the pumping lemma.

$
\mbox{Pumping lemma: if }M=(S,I,f,s_{0},F)$
$\mbox{ is a deterministic finite automaton and if } x \mbox{ is a string in }L(m),$ $\mbox{ the language recognized by M, with }$ $l(x) \geq |S|,$ $\mbox{ then there are strings }u, v, w \mbox{ in } I^{*}$ $\mbox{such that }$ $x = uvw, I(uv) \leq |S| \mbox{ and }l(v) \geq 1,\mbox{ and }uv^{i}w \in L(M) \mbox{ for }i = 0, 1, 2, ...$