ForSA HA2 A4b

Sei $\Sigma =\{a,b\}$. Gegeben sei die Sprache

$$A_2=\{a^q{b}^r\mid q,r\in \mathbb{N}\wedge q\mathrm{mod}3=0\wedge q/3=r\}$$

Beweise nur mit dem Pumping Lemma für reguläre Sprachen, dass $A_2$ nicht regulär ist.

Eigenschaften der Sprache in natürlichem Deutsch

Die Sprache $A_2$ besteht aus Wörtern über dem Alphabet $\Sigma =\{a,b\}$, die folgende Eigenschaften erfüllen:

1. Das Wort besteht aus einer bestimmten Anzahl von $a$‘s, gefolgt von einer bestimmten Anzahl von $b$‘s.
2. Die Anzahl der $a$‘s, die das Wort enthält, ist ein Vielfaches von 3.
3. Die Anzahl der $b$‘s im Wort ist das Ergebnis der Division der Anzahl der $a$‘s durch 3.

Mit anderen Worten, ein Wort in $A_2$ besteht aus einer Wiederholung der Buchstabe $a$ in einer Anzahl, die ein Vielfaches von 3 ist, gefolgt von einer Wiederholung des Buchstaben $b$ in einer Anzahl, die das Ergebnis der Division der Anzahl der $a$‘s durch 3 ist.

Beispielwörter der Sprache

$$A_2=\{a^q{b}^r\mid q,r\in \mathbb{N}\wedge q\mathrm{mod}3=0\wedge q/3=r\}$$ $$\underset{00}{\epsilon },\underset{3}{\mathrm{aaa}}\underset{1}{b},\underset{6}{\mathrm{aaaaaa}}\underset{2}{\mathrm{bb}},\underset{9}{\mathrm{aaaaaaaaa}}\underset{3}{\mathrm{bbb}}$$

Beweis mit Pumping Lemma, dass die Sprache nicht regulär ist

Sei $p\in \mathbb{N}$ (beliebig aber fest). Wir wählen $w=a^{3p}{b}^p$ mit $w\in A_1$, denn $3p,p\in \mathbb{N}$, und $3p\mathrm{mod}3=0$, und $3p/3=p$ . Sei $w=xyz$ eine beliebige Zerlegung mit $y\ne \epsilon$ und $|xy|\le p$. Da $|xy|\le p$ und $|a^{3p}|\ge p$ gilt, wissen wir, dass sowohl $x$ als auch $y$ nur aus Buchstaben $a$ bestehen und keinen Buchstaben $b$ enthalten. Dann ist $x=a^i,y=a^j$ und $z=a^{3p-i-j}{b}^p$ für ein $j\ne 0$ und $i+j\le p$. Wir wählen $k=0$. Dann ist $x{y}^{0}z=a^i{a}^{3p-i-j}{b}^p=a^{3p-j}{b}^p$. Um zu Überprüfen, ob $x{y}^{0}z$ ein Wort der Sprache $A_2$ ist, müssen wir alle Möglichkeiten betrachten, das Wort $x{y}^{0}z$ in die Teilworte $a^q$, und $b^r$ aufzuteilen. Da das Teilwort $a^q$ nur aus $a^{\prime }s$ bestehen kann und das Teilwort $b^r$ nur aus $b$‘s bestehen kann, können wir $x{y}^{0}z$ als $a^q{b}^r$ mit $q=3p-j$, und $r=p$ darstellen. Es gilt $x{y}^{0}z\notin A_2$, denn $q/3\ne r$, da $\frac{3p-j}{3}=p-\frac{j}{3}\ne p$ für $j\ne 0$. Da $\neg \text{PUMP-REG}(A_2)$, ist $A_2$ nach dem Pumping-Lemma nicht regulär.

---

Sources:

Related:

Tags: ForSA HA2 zum 2023-07-13