$1.$ Prove by contraction that

L $=\{1^$x $2^$y $1^$x$+$y $|$ x $>=1$ and y $>=1\}$ is not Regular.

Must use the Pumping Lemma. $[35$ points$]$

$[$ HINT: Describe the language in English first. $]$

$1)$ Choose one S from L where S is longer than N

$($Describe S in terms of N and M$)$

S $=?**?$

$2)$ List all places v can be in S: $($i$.$e$.$ all possible uvw mappings$)$

$($Note: v has to be in the first N chars$)$

v has to be where? $?**?$

$3)$ For each possible place for v in #$2$ above, is there is a way to repeat$/$skip v to make it

go out of the language L$?$

o Where v is: $?**?$

o Repeat factor: i $=?**?$

o What does u v$^$i w look like? $?**?$

o Is u v$^$i w in L$??**?$

Thus, there was no way to break S into uvw and repeat or skip v

as much as we want. We found a counter example S that does not satisfy Pumping Lemma.

$4)$ Conclusion about L: $?**?$