ForSA HA2 A4a

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

$$A_1=\left\{xy{x}^R\mid x\in {\Sigma }^{\ast }\wedge y\in \{a{\}}^{\ast }\wedge |x{|}_a\ge 1\wedge |x{|}_a=|y|\right\}$$

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

$$xyz$$

Eigenschaften der Sprache in natürlichem Deutsch

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

1. Das Wort hat die Form $xy{x}^R$, wobei $x$ ein beliebiges Wort über $\Sigma$ ist und $y$ ein Wort über $\Sigma$, das nur aus dem Buchstaben $a$ besteht.
2. Das Wort $x$ enthält mindestens einmal den Buchstaben $a$.
3. Die Anzahl der Vorkommen des Buchstabens $a$ in $x$ ist gleich der Länge des Wortes $y$.

Mit anderen Worten, ein Wort in $A_1$ besteht aus einer beliebigen Kombination von Buchstaben aus $\Sigma$, gefolgt von einem Wort, das nur aus dem Buchstaben $a$ besteht und die gleiche Länge hat wie die Anzahl der $a$‘s in der vorherigen Kombination von Buchstaben. Schließlich wird das Wort durch die Rückwärtsdarstellung der vorherigen Kombination von Buchstaben abgeschlossen.

Beispielwörter der Sprache

$$A_1=\left\{xy{x}^R\mid x\in {\Sigma }^{\ast }\wedge y\in \{a{\}}^{\ast }\wedge |x{|}_a\ge 1\wedge |x{|}_a=|y|\right\},\Sigma =\{a,b\}$$ $$aaa,aaaaaa,ababa,aabaabaa,bababaaaaababab$$ $$abaaaaaba\notin A$$

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

Sei $p\in \mathbb{N}$ (beliebig aber fest). Wir wählen das Wort $w=a^{p+1}b\cdot a^{p+1}\cdot b{a}^{p+1}$ mit $w\in A_1$, denn $(b{a}^{p+1}{)}^R=a^{p+1}b$, und $a^{p+1}b\in {\Sigma }^{\ast }$, und $a^{p+1}\in \{a{\}}^{\ast }$, und $|a^{p+1}b{|}_a=p+1\ge 1$ da $p\in \mathbb{N}$, und $|a^{p+1}b{|}_a=p+1=|a^{p+1}|$. Sei $w=xyz$ eine beliebige Zerlegung mit $y\ne \epsilon$ und $|xy|\le p$. Dann ist $x=a^i$, $y=a^j$ und $z=a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}$ für ein $j\ne 0$ und $i+j\le p+1$.

Wir wählen $k=0$. Dann ergibt

$${xy}^{0}z=a^i\cdot a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}=a^{p+1-j}b{a}^{p+1}b{a}^{p+1}$$

Um zu Überprüfen, ob ${xy}^{0}z$ ein Wort der Sprache $A_1$ ist, prüfen wir, ob wir ${xy}^{0}z$ so in die drei Teilworte $x$, $y$, und $x^R$ aufteilen können, dass die Bedingungen ${\left(x^R\right)}^R=x\wedge x\in {\Sigma }^{\ast }\wedge y\in \{a{\}}^{\ast }\wedge {\left|x\right|}_a\ge 1\wedge {\left|x\right|}_a=\left|y\right|$ erfüllt sind. $b$’s können nur im Teilwort $x\in {\Sigma }^{\ast }$ oder $x^R\in {\Sigma }^{\ast }$ vorkommen, jedoch nicht in $y\in \{a{\}}^{\ast }$. Das Wort ${xy}^{0}z$ enthält den Buchstaben $b$ zweimal: $|a^{p+1-j}b{a}^{p+1}b{a}^{p+1}{|}_b=2$. Da $x^R$ eine Rückwärtsdarstellung von $x$ ist, müssen beide Teilworte gleich viele, also genau eines der beiden $b$‘s enthalten, also gilt $|x{|}_b={\left|x^R\right|}_b=1$. Dann ist $x=a^{p+1-j}b{a}^l$, $y=a^{p+1-2l}$, und $x^R=a^{l}b{a}^{p+1}$ für ein $2l\le p+1$ mit $l\in \mathbb{N}$.

$${xy}^{0}z=a^{p+1-j}b{a}^{p+1}b{a}^{p+1}=a^{p+1-j}b{a}^l\cdot a^{p+1-2l}\cdot a^{l}b{a}^{p+1}$$

${xy}^{0}z\notin A_1$, denn ${\left(x^R\right)}^R\ne x$, da $(a^{l}b{a}^{p+1}{)}^R=a^{p+1}b{a}^l$ ungleich $a^{p+1-j}b{a}^l$ für $j\ne 0$ ist. Da $\neg \text{PUMP-REG}(A_1)$, ist $A_1$ nach dem Pumping-Lemma nicht regulär.

---

Sei $p\in \mathbb{N}$ (beliebig aber fest). Wir wählen das Wort $w=a^{p+1}b\cdot a^{p+1}\cdot b{a}^{p+1}$ mit $w\in A_1$, denn $(b{a}^{p+1}{)}^R=a^{p+1}b$, und $a^{p+1}b\in {\Sigma }^{\ast }$, und $a^{p+1}\in \{a{\}}^{\ast }$, und $|a^{p+1}b{|}_a=p+1\ge 1$ da $p\in \mathbb{N}$, und $|a^{p+1}b{|}_a=p+1=|a^{p+1}|$. Sei $w=xyz$ eine beliebige Zerlegung mit $y\ne \epsilon$ und $|xy|\le p$. Das Wort $w$ beginnt mit dem Präfix $a^{p+1}$, wobei $\left|a^{p+1}\right|=p+1>p$. Da $|xy|\le p$ und $|a^{p+1}|>p$ gilt, wissen wir, dass sowohl $x$ als auch $y$ nur aus Buchstaben $a$ bestehen. Dann ist $x=a^i$, $y=a^j$ und $z=a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}$ für ein $j\ne 0$ und $i+j\le p$:

Sei $p\in \mathbb{N}$ (beliebig aber fest). Wir wählen das Wort $w=a^{p+1}b\cdot a^{p+1}\cdot b{a}^{p+1}$ mit $w\in A_1$, denn $(b{a}^{p+1}{)}^R=a^{p+1}b$, und $a^{p+1}b\in {\Sigma }^{\ast }$, und $a^{p+1}\in \{a{\}}^{\ast }$, und $|a^{p+1}b{|}_a=p+1\ge 1$ da $p\in \mathbb{N}$, und $|a^{p+1}b{|}_a=p+1=p+1=|a^{p+1}|$. Sei $w=xyz$ eine beliebige Zerlegung mit $y\ne \epsilon$ und $|xy|\le p$. Da $|xy|\le p$ und $|a^{p+1}|>p$ gilt, wissen wir, dass sowohl $x$ als auch $y$ nur aus Buchstaben $a$ bestehen. Dann ist $x=a^i$, $y=a^j$ und $z=a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}$ für ein $j\ne 0$ und $i+j\le p$:

$$\begin{array}{rl}w=a^{p+1}b\cdot a^{p+1}\cdot b{a}^{p+1}& =\stackrel{p+1}{\overbrace{\underset{i}{\underbrace{a\dots a}}\underset{j}{\underbrace{a\dots a}}\underset{p+1-i-j}{\underbrace{a\dots a}}}}b\stackrel{p+1}{\overbrace{a\dots a}}b\stackrel{p+1}{\overbrace{a\dots a}}\\ & =\underset{x}{\underbrace{\overbrace{a\dots a}}}\underset{y}{\underbrace{\overbrace{a\dots a}}}\underset{z}{\underbrace{\overbrace{a\dots a}ba\dots aba\dots a}}\\ & =a^i\cdot a^j\cdot a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}=xyz\end{array}$$ $$\begin{array}{rl}w=a^{p+1}b\cdot a^{p+1}\cdot b{a}^{p+1}& =\stackrel{p+1}{\overbrace{\underset{i}{\underbrace{a\dots a}}\underset{j}{\underbrace{a\dots a}}\underset{p+1-i-j}{\underbrace{a\dots a}}}}b\stackrel{p+1}{\overbrace{a\dots a}}b\stackrel{p+1}{\overbrace{a\dots a}}\\ & =\underset{x}{\underbrace{\overbrace{a\dots a}}}\underset{y}{\underbrace{\overbrace{a\dots a}}}\underset{z}{\underbrace{\overbrace{a\dots a}ba\dots aba\dots a}}\\ & =a^i\cdot a^j\cdot a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}=xyz\end{array}$$

Wir wählen $k=0$. Dann ergibt

$${xy}^{0}z=a^i\cdot a^{p+1-i-j}b{a}^{p+1}b{a}^{p+1}=a^{p+1-j}b{a}^{p+1}b{a}^{p+1}$$

Um zu Überprüfen, ob ${xy}^{0}z$ ein Wort der Sprache $A_1$ ist, prüfen wir, ob wir ${xy}^{0}z$ so in die drei Teilworte $x$, $y$, und $x^R$ aufteilen können, dass die Bedingungen ${\left(x^R\right)}^R=x\wedge x\in {\Sigma }^{\ast }\wedge y\in \{a{\}}^{\ast }\wedge {\left|x\right|}_a\ge 1\wedge {\left|x\right|}_a=\left|y\right|$ erfüllt sind. $b$’s können nur im Teilwort $x\in {\Sigma }^{\ast }$ oder $x^R\in {\Sigma }^{\ast }$ vorkommen, jedoch nicht in $y\in \{a{\}}^{\ast }$. Das Wort ${xy}^{0}z$ enthält den Buchstaben $b$ zweimal: $|a^{p+1-j}b{a}^{p+1}b{a}^{p+1}{|}_b=2$. Da $x^R$ eine Rückwärtsdarstellung von $x$ ist, müssen beide Teilworte gleich viele, also genau eines der beiden $b$‘s enthalten, also gilt $|x{|}_b={\left|x^R\right|}_b=1$. Dann ist $x=a^{p+1-j}b{a}^l$, $y=a^{p+1-2l}$, und $x^R=a^{l}b{a}^{p+1}$ für ein $2l\le p+1$ mit $l\in \mathbb{N}$.

$$\begin{array}{rl}{xy}^{0}z=a^{p+1-j}b{a}^{p+1}b{a}^{p+1}& =\stackrel{p+1-j}{\overbrace{a\dots a}}b\stackrel{p+1}{\overbrace{\underset{l}{\underbrace{a\dots a}}\underset{p+1-2l}{\underbrace{a\dots a}}\underset{l}{\underbrace{a\dots a}}}}b\stackrel{p+1}{\overbrace{a\dots a}}\\ & =\underset{x}{\underbrace{a\dots ab\overbrace{a\dots a}}}\underset{y}{\underbrace{\overbrace{a\dots a}}}\underset{x^R}{\underbrace{\overbrace{a\dots a}ba\dots a}}\\ & =a^{p+1-j}b{a}^l\cdot a^{p+1-2l}\cdot a^{l}b{a}^{p+1}\end{array}$$

${xy}^{0}z\notin A_1$, denn ${\left(x^R\right)}^R\ne x$, da $(a^{l}b{a}^{p+1}{)}^R=a^{p+1}b{a}^l\ne a^{p+1-j}b$ für $j\ne 0$. Da $\neg \text{PUMP-REG}(A_1)$, ist $A_1$ nach dem Pumping-Lemma nicht regulär.

---

Sources:

Related:

Tags: ForSA HA2 zum 2023-07-13