# SS Exercise Session Lecture 4

## Exercise 1
> Prove that the language $L_1=\left\{a b^n c^n \mid n \geq 0\right\}$ is nonregular.

1. Dæmonen vælger $p$
2. Vi laver et ord $w = ab^pc^p$, $|w| \geq p$
3. Dæmonen opdeler det i $w = xyz$, så $|xy| \leq p$ og $y \neq \epsilon$
4. Hvis $x = \epsilon$, så indeholder y mindst et a. Vi vælger en $i > 1$. Så er der mere end 1 a. Hvis $x \neq \epsilon$, så er y kun b'er. Hvis vi har mere end 1 y, er der flere b'er end c'er.

## Exercise 2

> Prove that the language $L_2=\left\{0^n 1^m 0^n \mid n, m \geq 0\right\}$ is nonregular.

1. Dæmonen vælger $p$
2. Vi laver et ord $w = 0^p1^10^p$, $|w| \geq p$
3. Dæmonen opdeler det i $w = xyz$, så $|xy| \leq p$ og $y \neq \epsilon$
4. Uanset hvad dæmonen vælger, kan man tage $i = 0$ og du vinder. Fordi $|xy|\leq p$, har $y$ kun $0$'er. Derfor $xy^0z=0^{p-|y|}10^p \notin L_2$

## Exercise 3

> Prove that the language $L_3=\left\{a^n b^m \mid n, m \geq 0\right.$ and $\left.n \neq m\right\}$ is nonregular.

1. Dæmonen vælger $p$
2. Vi laver et ord $w = a^{p}b^{p+1}$, $|w| \geq p$
3. Dæmonen opdeler det i $w = xyz$, så $|xy| \leq p$ og $y \neq \epsilon$
4. Uanset hvad dæmonen vælger, kan man tage

aaaa aaaa bbbb

$w = a^{0}b^{p}$
$w = a^{p}b^{0}$
$w = a^{p}b^{p+1}$
$w = a^{p+1}b^{p}$
$w = a^{1}b^{p}$
$w = a^{p}b^{1}$

$w = a^{p}bb^{p} = a^{p}b^{p+1}$
$w = a^{p}ab^{p} = a^{p+1}b^{p}$

---

ChatGPT:

To prove that $L_3$ is nonregular, we will use the pumping lemma for regular languages. Assume that $L_3$ is regular, and let $p$ be the pumping length given by the lemma.

Consider the string $s = a^p b^{p+1}$. Since $|s| = 2p+1 \geq p$, the pumping lemma guarantees that we can write $s$ as $s = xyz$, where $|y| \geq 1$, $|xy| \leq p$, and $xy^iz \in L_3$ for all $i \geq 0$.

Since $|xy| \leq p$, we know that $xy$ consists entirely of $a$'s. We can write $y$ as $a^k$ for some $1 \leq k \leq p$, so $x$ consists of $a$'s and $b$'s. Then $xy^iz$ consists of $a^{p-i*(k-1)} b^{p+1}$.

For $i = 0$, we have $xy^0z = xz = a^{p-k} b^{p+1}$. This string is in $L_3$ since $p-k \neq p+1$.

For $i = 1$, we have $xy^1z = xyz = a^p b^{p+1}$. This string is not in $L_3$ since $p = p+1$.

Therefore, we have found a string $s \in L_3$ such that no matter how we split it into $xyz$, there exists an $i$ such that $xy^iz \notin L_3$. This contradicts the pumping lemma, so our assumption that $L_3$ is regular must be false. Therefore, $L_3$ is nonregular.

As an example string in $L_3$, we can use $s = a^3 b^2$. This string is in $L_3$ since $3 \neq 2$.