FSK-ÜB-6

Es gibt auf dieser Seite teilweise Fehler mit dem rendern von den LaTeX ausdrücken aufgrund der $ und # ich bitte um Entschuldigung während ich nach einer Lösung suche

Falls dieses Problem noch länger besteht, bitte einen Kommentar schreiben um mich daran zu erinnen

FSK6-1 Kontextfreie Grammatiken und Kellerautomaten (2 Punkte)

Aufgabenstellung:

Sei L = \{a^{2n}\a^n \mid n \in \mathbb{N}_{\gt0}}$eineSprache\ddot{u}berdemAlphabet$\Sigma = {a, $\}$.

a) Geben Sie eine kontextfreie Grammatik an, die $L$ erkennt.

$$G=(N,\Sigma ,P,S)$$ $$N=\{S\}$$ $$\Sigma =\{a,\$\}$$

Falsch, da nicht N>0

$$P=\{S\to aaSa\mid \$\}$$

Korrekt

$$P=\{S\to aaSa,D\to \$\mid aaDa\}$$

$$S$$

Gedankengang:

• Links vom $ müssen doppelt so viele a’s stehen wie auf der rechten Seite.
• $S\to aaSa$ bildet den Basisfall für diese Anforderung.
• S \rightarrow \ ist da, um das $ zwischen der linken und der rechten Seite zu setzen.
• Bei rekursivem Benutzen von $S$ werden links immer doppelt so viele a’s hinzugefügt wie rechts.
• Nach $n$ Rekursionen ist das Wort gebildet und kann mithilfe von S \rightarrow \ getrennt werden.

$⟹$ Dadurch erkennt diese Grammatik die Sprache $L$.

b) Geben Sie einen Kellerautomaten an, der $L$ akzeptiert (mit leerem Keller oder mit Endzuständen). Erklären Sie kurz, warum Ihr Automat genau $L$ akzeptiert.

Ein Kellerautomat $M$, der die Sprache L = \{a^{2n}\a^n \mid n \in \mathbb{N}_{\gt0}}$ akzeptiert, wird wie folgt definiert:

Definition des Kellerautomaten:

• Zustände: $Z=\{q_0,q_1,q_f\}$
• Eingabealphabet: \Sigma = \{a, \}$
• Kelleralphabet: $\Gamma =\{a,\#\}$
• Startzustand: $z_0=q_0$
• Startkellersymbol: $\#$
• Akzeptierende Zustände: $F=\{q_f\}$

Übergangsfunktion $\delta$:

1. Initiale Phase (Doppelte a’s auf den Keller legen):

   • $\delta (q_0,a,\#)=\{(q_0,a\#)\}$
   • $\delta (q_0,a,a)=\{(q_0,aa)\}$

2. Dollarzeichen erkennen:

   • \delta(q_0, \, a) = {(q_1, a)}$

3. a’s nach dem Dollarzeichen verarbeiten:

   • $\delta (q_1,a,a)=\{(q_1,\epsilon )\}$

4. Keller entleeren und akzeptieren:

   • $\delta (q_1,\epsilon ,\#)=\{(q_f,\#)\}$

Erklärung:

1. Phase 1 (Initiale Phase):

   • Der Automat liest die a’s und legt sie auf den Keller, sodass die Anzahl der a’s im Keller doppelt so groß ist wie die Anzahl der a’s, die nach dem Dollarzeichen gelesen werden müssen.

2. Phase 2 (Dollarzeichen erkennen):

   • Sobald das Dollarzeichen \$$ gelesen wird, wechselt der Automat in den Zustand q_1$.

3. Phase 3 (Nachfolgende a’s verarbeiten):

   • Der Automat liest die a’s nach dem Dollarzeichen und entfernt ein a vom Keller für jedes gelesene a.

4. Phase 4 (Akzeptieren):

   • Wenn der Keller leer ist und das Startkellersymbol $\#$ erreicht wird, wechselt der Automat in den akzeptierenden Zustand $q_f$ und akzeptiert die Eingabe.

FSK6-2 CYK-Algorithmus (2 Punkte)

Aufgabenstellung

Sei $G$ die Grammatik ({A_1, A_2, A_3, A_4, A_5}, \{\, #}, P, A_1)$ mit

$$\begin{array}{rl}P=\{& A_1\to A_3{A}_4\mid A_3{A}_2,\\ & A_2\to A_2{A}_3\mid A_4{A}_4,\\ & A_3\to \$,\\ & A_4\to \#\mid A_3{A}_4,\\ & A_5\to A_4{A}_4\mid \#\}\end{array}$$

a) Prüfen Sie mit dem CYK-Algorithmus, ob die folgenden Wörter $w_1$ und $w_2$ in $L(G)$ sind. Erstellen Sie dazu für jedes Wort die entsprechende Tabelle des Algorithmus und erklären Sie anhand der Tabelle, ob das Wort in $L(G)$ ist.

i) w_1 = \#$##$

CYK-Algorithmus zur Überprüfung von w_1 = \#$##$

Gegebene Grammatik $G$:

$$\begin{array}{rl}P=\{& A_1\to A_3{A}_4\mid A_3{A}_2,\\ & A_2\to A_2{A}_3\mid A_4{A}_4,\\ & A_3\to \$,\\ & A_4\to \#\mid A_3{A}_4,\\ & A_5\to A_4{A}_4\mid \#\}\end{array}$$

Eingabewort: w_1 = \#$##$

Schritt 1: Initialisierung der Tabelle

$$\begin{array}{ccccc}1& 2& 3& 4& 5\\ \$& \#& \$& \#& \#\\ A_3& A_4,A_5& A_3& A_4,A_5& A_4,A_5\end{array}$$

Schritt 2: Rekursion

$V_{i,j}$	1	2	3	4	5
1	$A_3$	$A_4,A_5$	$A_3$	$A_4,A_5$	$A_4,A_5$
2	$A_1,A_4$		$A_1,A_4$	$A_2,A_5$	-
3		$A_2,A_5$	$A_1,A_2,A_5$	-	-
4	$A_1,A_2,A_5$		-	-	-
5		-	-	-	-

Fazit:

• Das Wort w_1 = \#$##$istnichtin$L(G)$,daStartsymbol$A_{1} \notin V_{1,5}$

Falsche Lösung zum Verständnis worauf zu achten ist

• Fehler tritt schon in Zeile 2 auf, wo nur $A_1$ als Option betrachtet wird, wobei $A_4$ auch legitim wäre
• $V_{2,2}$ ist nicht korrekt da man immer das Kreuzprodukt aus den ausgewählten Zeilen bilden muss z.B ($V_{2,1}\times V_{3,1}=A_4{A}_3,A_5{A}_3$) und $A_4{A}_3$ oder $A_5{A}_3$ beide nicht dargestellt werden können

$V_{i,j}$	1	2	3	4	5
1	$A_3$	$A_4,A_5$	$A_3$	$A_4,A_5$	$A_4,A_5$
2	$A_1$	$A_4$	$A_4$	$A_5$	-
3	$A_1$	$A_5$	$A_5$	-	-
4	$\varnothing$	$\varnothing$	-	-	-
5	$\varnothing$	-	-	-	-

Zeile 2:

• $V_{1,2}=A_1$, da $A_1$ $A_3$ und $A_4$ bilden kann
• $V_{2,2}=A_4$, da $A_4$ $A_4$ und $A_3$ bilden kann
• $V_{3,2}=A_4$, da $A_4$ $A_4$ und $A_3$ bilden kann
• $V_{4,2}=A_5$, da $A_5$ $A_4$ und $A_4$ bilden kann

Zeile 3:

• $V_{1,3}=A_1$, da $A_1$ $A_3$ ($V_{1,1}$) und $A_4$ ($V_{2,2}$) bilden kann
• $V_{2,3}=A_5$, da $A_5$ $A_4$ ($V_{1,2}$) und $A_4$ ($V_{2,3}$) bilden kann
• $V_{3,3}=A_5$, da $A_5$ $A_4$ ($V_{3,2}$) und $A_4$ ($V_{5,1}$) bilden kann

Zeile 4:

• $V_{1,4}=\varnothing$
  • $(V_{1,1})\text{und}(V_{2,3})$ bilden $A_3{A}_5$ was nicht abgebildet werden kann
  • $(V_{1,2})\text{und}(V_{3,2})$ bilden $A_1{A}_4$ was nicht abgebildet werden kann
  • $(V_{1,3})\text{und}(V_{4,1})$ bilden $A_1{A}_4,A_5$ was nicht abgebildet werden kann
• $V_{2,4}=\varnothing$
  • $(V_{2,1})\text{und}(V_{3,3})$ bilden $A_4,A_5{A}_5$ was nicht abgebildet werden kann
  • $(V_{2,2})\text{und}(V_{4,2})$ bilden $A_4{A}_5$ was nicht abgebildet werden kann
  • $(V_{2,3})\text{und}(V_{5,1})$ bilden $A_4,A_5{A}_5$ was nicht abgebildet werden kann

Zeile 5:

• $V_{1,5}=\varnothing$
  • $(V_{1,1})\text{und}(V_{2,4})$ bilden $A_3$ und $\varnothing$ was nicht abgebildet werden kann
  • $(V_{1,2})\text{und}(V_{3,3})$ bilden $A_1$ und $A_5$ was nicht abgebildet werden kann
  • $(V_{1,3})\text{und}(V_{4,2})$ bilden $A_1$ und $A_5$ was nicht abgebildet werden kann
  • $(V_{1,4})\text{und}(V_{5,1})$ bilden $\varnothing$ und $A_4,A_5$ was nicht abgebildet werden kann

ii) w_2 = \$$##$

Gegebene Grammatik $G$:

$$\begin{array}{rl}P=\{& A_1\to A_3{A}_4\mid A_3{A}_2,\\ & A_2\to A_2{A}_3\mid A_4{A}_4,\\ & A_3\to \$,\\ & A_4\to \#\mid A_3{A}_4,\\ & A_5\to A_4{A}_4\mid \#\}\end{array}$$

Eingabewort: w_2 = \$$##$

Schritt 1: Initialisierung der Tabelle

$$\begin{array}{ccccc}1& 2& 3& 4& 5\\ \$& \$& \$& \#& \#\\ A_3& A_3& A_3& A_4,A_5& A_4,A_5\end{array}$$

Schritt 2: Rekursion

$V_{i,j}$	1	2	3	4	5
1	$A_3$	$A_3$	$A_3$	$A_4,A_5$	$A_4,A_5$
2			$A_1,A_4$	$A_2,A_5$	-
3		$A_1,A_4$	$A_1,A_2,A_5$	-	-
4	$A_1,A_4$	$A_1,A_2,A_5$	-	-	-
5	$A_1,A_2,A_5$	-	-	-	-

Zeile 2:

• $V_{1,2}$ = $(V_{1,1}\times V_{2,1})=A_3{A}_3⟹\varnothing$
• $V_{2,2}$ = $(V_{2,1}\times V_{3,1})=A_3{A}_3⟹\varnothing$
• $V_{3,2}$ = $(V_{3,1}\times V_{4,1})=A_3{A}_4,A_3{A}_5\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
• $V_{4,2}$ = $(V_{4,1}\times V_{5,1})=A_4{A}_4,A_4{A}_5,A_5{A}_4,A_5{A}_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 3:

• $V_{1,3}=\varnothing$

  • $V_{1,1}\times V_{2,2}=A_3\times \varnothing ⟹\varnothing$
  • $V_{1,2}\times V_{3,2}=\varnothing \times A_3⟹\varnothing$

• $V_{2,3}=A_1,A_4$

  • $V_{2,1}\times V_{3,2}=A_3\times A_1,A_4=A_3{A}_1,A_3{A}_4\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
  • $V_{4,1}\times V_{2,2}=A_4{A}_5\times \varnothing ⟹\varnothing$

• $V_{3,3}=A_1,A_2,A_5$

  • $V_{3,1}\times V_{4,2}=A_3\times A_2,A_5=A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{5,1}\times V_{3,2}=A_4{A}_5\times A_1,A_4=A_4{A}_1,A_4{A}_4,A_5{A}_1,A_5{A}_4\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 4:

• $V_{1,4}=A_1,A_4$

  • $V_{1,1}\times V_{2,3}=A_3\times A_1,A_4=A_3{A}_1,A_3{A}_4\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
  • $V_{1,2}\times V_{3,2}=\varnothing \times A_1,A_4⟹\varnothing$
  • $V_{1,3}\times V_{4,2}=\varnothing \times A_4,A_5⟹\varnothing$

• $V_{2,4}=A_1,A_2,A_5$

  • $V_{2,1}\times V_{3,3}=A_3\times A_1,A_2,A_5=A_3{A}_1,A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{2,2}\times V_{4,2}=\varnothing \times A_2,A_5⟹\varnothing$
  • $V_{2,3}\times V_{5,1}=A_1,A_4\times A_4,A_5=A_1{A}_4,A_1{A}_5,A_4{A}_4,A_4{A}_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 5:

• $V_{1,5}=A_1,A_2,A_5$
  • $V_{1,1}\times V_{2,4}=A_3\times A_1,A_2,A_5=A_3{A}_1,A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{1,2}\times V_{3,3}=\varnothing \times A_1,A_2,A_5⟹\varnothing$
  • $V_{1,3}\times V_{4,2}=\varnothing \times A_2,A_5⟹\varnothing$
  • $V_{1,4}\times V_{5,1}=A_1,A_4\times A_4,A_5=A_1{A}_4,A_1{A}_5,A_4{A}_4,A_4,A_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Fazit:

• Das Wort w_1 = \#$##$istin$L(G)$,daStartsymbol$A_{1} \in V_{1,5}$

b) Geben Sie alle weiteren Wörter $w$ an, für die sich aus den Tabellen ergibt, dass $w\in L(G)$ ist.

Unsicher wie zu lösen ist

Identifikation weiterer Wörter $w$ in $L(G)$

Die Tabellen zeigen, dass die Grammatik die folgenden Kombinationen von $ und # zulässt:

2. Länge 2:

   • $ #

3. Länge 3:

   • $ # #

4. Länge 4 und mehr:

   • $ # $ #
   • $ $ # #
   • # $ $ #

Schlussfolgerung

Die Grammatik $G$ erlaubt Kombinationen von $ und #, die den Ableitungsregeln entsprechen. Insbesondere alle Wörter, die durch Kombinationen und Anwendungen der Produktionen von $A_3$, $A_4$, $A_5$, $A_1$ und $A_2$ entstehen, sind Teil der Sprache $L(G)$.

FSK6-3 Begrenzter Keller

a) Ein Kellerautomat mit $k$-begrenzt​em Keller ist ein Kellerautomat, bei dem maximal $k$ Symbole auf dem Keller liegen können. Wenn der Keller voll ist, können Übergänge, die ein Symbol auf den Keller legen würden, nicht gewählt werden.

Zeigen Sie, dass für jeden Kellerautomaten $K$ und $k\in {\mathbb{N}}_0$ gilt:

$$L(K\text{ mit }k\text{-begrenztem Keller})\subseteq L(K)$$

Hierbei nehmen wir an, dass $K$ mit leerem Keller akzeptiert.

Beweis:

1. Definition der akzeptierten Sprache:

   • Ein Kellerautomat $K$ akzeptiert ein Wort $w$, wenn durch Zustandsübergänge der Startzustand in einen akzeptierenden Zustand überführt wird und der Keller nach Verarbeitung von $w$ leer ist.

2. Eigenschaften des $k$-begrenzten Kellers:

   • Ein Kellerautomat mit $k$-begrenztem Keller kann höchstens $k$ Symbole im Keller haben. Bei vollem Keller sind Übergänge, die Symbole hinzufügen, nicht möglich.

3. Behauptung:

   • Jedes Wort, das vom $k$-begrenzten Kellerautomaten akzeptiert wird, wird auch vom ursprünglichen Kellerautomaten ohne Begrenzung akzeptiert: $$L(K\text{ mit }k\text{-begrenztem Keller})\subseteq L(K).$$

4. Simulation von $K$ mit $k$-begrenztem Keller:

   • Ein Wort $w$ wird vom $k$-begrenztem Kellerautomaten akzeptiert, wenn es eine Zustandsübergangsfolge $\delta$ gibt, die $w$ vollständig verarbeitet und den Keller leer macht, ohne jemals mehr als $k$ Symbole im Keller zu haben.
   • Diese Zustandsübergänge $\delta$ können auch im ursprünglichen Kellerautomaten $K$ (ohne Begrenzung) ausgeführt werden, da $K$ keine Begrenzung der Symbolanzahl im Keller hat.

5. Formalität des Beweises:

   • Angenommen, $w\in L(K\text{ mit }k\text{-begrenztem Keller})$. Das bedeutet, dass es eine akzeptierende Berechnung des $k$-begrenzten Kellerautomaten für $w$ gibt, die den Keller nie mehr als $k$ Symbole enthalten lässt.
   • Da diese Berechnung auch im unbegrenzten Kellerautomaten $K$ möglich ist, akzeptiert $K$ ebenfalls $w$.

6. Schlussfolgerung:

   • Jede akzeptierende Berechnung des $k$-begrenzten Kellerautomaten ist auch eine akzeptierende Berechnung des unbegrenzten Kellerautomaten. Daher gilt: $$L(K\text{ mit }k\text{-begrenztem Keller})\subseteq L(K).$$

b) Zeigen Sie, dass für alle $k\in {\mathbb{N}}_{>0}$ die Kellerautomaten mit $k$-begrenztem Keller genau die regulären Sprachen beschreiben.

Lösung (direkte Beweiskombination)

1. Kellerautomaten mit $k$-begrenztem Keller akzeptieren reguläre Sprachen:

• Jede reguläre Sprache $L$ kann durch einen deterministischen endlichen Automaten (DFA) akzeptiert werden.
• Ein Kellerautomat mit $k$-begrenztem Keller kann dieselbe Sprache akzeptieren, indem er den Keller nicht nutzt oder nur eine konstante Anzahl von Symbolen speichert (maximal $k$).

2. Kellerautomaten mit $k$-begrenztem Keller akzeptieren nur reguläre Sprachen:

• Der Keller ist auf $k$ Symbole begrenzt, daher gibt es nur endlich viele mögliche Kellerinhalte.
• Kombiniere die Zustände des Kellerautomaten und die möglichen Kellerinhalte, um eine endliche Zustandsmenge zu erhalten.
• Dadurch kann ein DFA konstruiert werden, der dieselbe Sprache akzeptiert wie der Kellerautomat mit $k$-begrenztem Keller.

Schlussfolgerung:

Kellerautomaten mit $k$-begrenztem Keller beschreiben genau die regulären Sprachen, da sie einerseits reguläre Sprachen akzeptieren können und andererseits nur reguläre Sprachen akzeptieren.

---

FSK6-4 Homomorphismen

Aufgabenstellung:

Gegeben Alphabete $\Sigma$ und $\Delta$ bezeichnen wir eine Abbildung $h:{\Sigma }^{\ast }\to {\Delta }^{\ast }$ als (Monoid-)Homomorphismus, wenn sie strukturerhaltend ist, d.h. wenn gilt:

$$\begin{array}{rl}h(ϵ)& =ϵ\\ h(u\circ v)& =h(u)\circ h(v)\forall u,v\in {\Sigma }^{\ast }\end{array}$$

Für $L\subseteq {\Sigma }^{\ast }$ sei $h(L)=\{h(u)\mid u\in L\}$.

Man kann leicht zeigen, dass für alle Sprachen $L_1,L_2\subseteq {\Sigma }^{\ast }$ und Homomorphismen $h$ gilt:

$$\begin{array}{rl}h(\varnothing )& =\varnothing \\ h(L_1\cup L_2)& =h(L_1)\cup h(L_2)\\ h(L_1\cap L_2)& =h(L_1)\cap h(L_2)\end{array}$$

a) Beweisen Sie für alle Sprachen $L_1,L_2\subseteq {\Sigma }^{\ast }$ und Homomorphismen $h$:

$$h(L_1\circ L_2)=h(L_1)\circ h(L_2)$$ $$h(L_1^{\ast })=(h(L_1){)}^{\ast }$$

Beweis für $h(L_1\circ L_2)=h(L_1)\circ h(L_2)$

Gegeben:

• Zwei Sprachen $L_1,L_2\subseteq {\Sigma }^{\ast }$
• Ein Homomorphismus $h:{\Sigma }^{\ast }\to {\Delta }^{\ast }$

Behauptung:

$$h(L_1\circ L_2)=h(L_1)\circ h(L_2)$$

Beweis:

1. Definition der Konkatens von Sprachen:

   $$L_1\circ L_2=\{u\circ v\mid u\in L_1\text{ und }v\in L_2\}$$

2. Bild der Konkatens zweier Sprachen unter $h$:

   $$h(L_1\circ L_2)=\{h(w)\mid w\in L_1\circ L_2\}$$

   Da $w\in L_1\circ L_2$, gibt es $u\in L_1$ und $v\in L_2$ mit $w=u\circ v$. Somit:

   $$h(w)=h(u\circ v)$$

3. Eigenschaft des Homomorphismus:

   $$h(u\circ v)=h(u)\circ h(v)$$

   Also:

   $$h(w)=h(u)\circ h(v)$$

4. Ersetzung in der Menge:

   $$h(L_1\circ L_2)=\{h(u)\circ h(v)\mid u\in L_1,v\in L_2\}$$

   Dies ist per Definition:

   $$h(L_1)\circ h(L_2)=\{x\circ y\mid x\in h(L_1),y\in h(L_2)\}$$

5. Folgerung:

   $$h(L_1\circ L_2)=h(L_1)\circ h(L_2)$$

Beweis für $h(L_1^{\ast })=(h(L_1){)}^{\ast }$

Gegeben:

• Eine Sprache $L_1\subseteq {\Sigma }^{\ast }$
• Ein Homomorphismus $h:{\Sigma }^{\ast }\to {\Delta }^{\ast }$

Behauptung:

$$h(L_1^{\ast })=(h(L_1){)}^{\ast }$$

Beweis:

1. Definition des Kleene-Sterns:

   $$L_1^{\ast }=\bigcup _{k=0}^{\infty }{L}_1^k$$

   wobei $L_1^0=\{ϵ\}$ und $L_1^{k+1}=L_1^k\circ L_1$.

2. Bild unter $h$:

   $$h(L_1^{\ast })=h\left(\bigcup _{k=0}^{\infty }{L}_1^k\right)=\bigcup _{k=0}^{\infty }h(L_1^k)$$

3. Eigenschaft des Homomorphismus für Konkatens:

   $$h(L_1^k)=(h(L_1){)}^k$$

   Beweis durch Induktion über (k):

   • Induktionsanfang:

     $$k=0:h(L_1^0)=h(\{ϵ\})=\{ϵ\}=(h(L_1){)}^0$$

   • Induktionsannahme: Angenommen, es gilt $h(L_1^k)=(h(L_1){)}^k$.

   • Induktionsschritt:

     $$h(L_1^{k+1})=h(L_1^k\circ L_1)=h(L_1^k)\circ h(L_1)=(h(L_1){)}^k\circ h(L_1)=(h(L_1){)}^{k+1}$$

Daher gilt $h(L_1^k)=(h(L_1){)}^k$ für alle $k$.

4. Zusammensetzung der Kleene-Sterns:

   $$h(L_1^{\ast })=\bigcup _{k=0}^{\infty }h(L_1^k)=\bigcup _{k=0}^{\infty }(h(L_1){)}^k=(h(L_1){)}^{\ast }$$

5. Folgerung:

   $$h(L_1^{\ast })=(h(L_1){)}^{\ast }$$

Damit sind beide Aussagen bewiesen:

$$h(L_1\circ L_2)=h(L_1)\circ h(L_2)$$ $$h(L_1^{\ast })=(h(L_1){)}^{\ast }$$

b) Beweisen Sie für alle regulären Sprachen $L$ und Homomorphismen $h$: Wenn $L$ regulär ist, dann ist auch $h(L)$ regulär.

Beweis:

1. Gegeben: $L$ ist eine reguläre Sprache über dem Alphabet $\Sigma$.

2. Eigenschaft regulärer Sprachen: Da $L$ regulär ist, existiert ein deterministischer endlicher Automat (DFA) $A=(Q,\Sigma ,\delta ,q_0,F)$, der $L$ erkennt.

3. Homomorphismus $h$: Der Homomorphismus $h:{\Sigma }^{\ast }\to {\Delta }^{\ast }$ ist eine Abbildung, die strukturerhaltend ist:

   $$h(u\circ v)=h(u)\circ h(v)\forall u,v\in {\Sigma }^{\ast }$$

4. Transformation des Automaten: Wir konstruieren einen neuen Automaten $A_h=(Q,\Delta ,{\delta }_h,q_0,F)$, der $h(L)$ erkennt. Dabei wird die Übergangsfunktion $\delta$ so angepasst, dass sie auf die Bilder der Symbole unter $h$ angewendet wird.

5. Konstruktion von $A_h$:

   • Der neue Automat $A_h$ hat denselben Zustandsraum $Q$, Startzustand $q_0$, und Endzustände $F$ wie $A$.
   • Die Übergangsfunktion ${\delta }_h$ wird so definiert, dass sie den Übergängen von $A$ folgt, aber für die Symbole in $\Delta$, die durch $h$ abgebildet werden.

6. Erkennung von $h(L)$: Da $A_h$ durch die Anwendung von $h$ auf die Übergangsfunktion von $A$ konstruiert wird, erkennt $A_h$ die Sprache $h(L)$.

Schlussfolgerung:

Da $A_h$ ein DFA ist und DFA’s genau die regulären Sprachen erkennen, ist $h(L)$ ebenfalls regulär.

Zusammenfassung:

Wenn $L$ regulär ist, gibt es einen DFA, der $L$ erkennt. Durch Transformation dieses DFA unter dem Homomorphismus $h$ erhält man einen neuen DFA, der $h(L)$ erkennt. Daher ist $h(L)$ regulär.

c) Zeigen Sie, dass über dem Alphabet $\Sigma =\{a,b,c,d\}$ die Sprache

$$L=\{a^n{b}^i{c}^n{d}^j\mid n,i,j\in \mathbb{N}\}$$

nicht regulär ist. Geben Sie zu diesem Zweck einen Homomorphismus $h$ an, so dass $h(L)=\{a^n{b}^n\mid n\in \mathbb{N}\}$ ist. Da $h(L)$ bekanntlich nicht regulär ist, kann dann auch $L$ nicht regulär sein.

Um zu zeigen, dass die Sprache $L=\{a^n{b}^i{c}^n{d}^j\mid n,i,j\in \mathbb{N}\}$ nicht regulär ist, verwenden wir einen Homomorphismus $h$, der $L$ auf eine bekannte nicht-reguläre Sprache abbildet.

Schritt-für-Schritt Beweis:

1. Definition der Sprache $L$:

   $$L=\{a^n{b}^i{c}^n{d}^j\mid n,i,j\in \mathbb{N}\}$$

2. Homomorphismus $h$: Wir definieren $h:{\Sigma }^{\ast }\to \{a,b{\}}^{\ast }$ mit dem Alphabet $\Sigma =\{a,b,c,d\}$ wie folgt:

   $$h(a)=a$$ $$h(b)=ϵ$$ $$h(c)=b$$ $$h(d)=ϵ$$

3. Bild der Sprache $L$ unter $h$:

   $$h(L)=\{h(a^n{b}^i{c}^n{d}^j)\mid n,i,j\in \mathbb{N}\}$$

   Da $h(b)=ϵ$ und $h(d)=ϵ$, vereinfacht sich das zu:

   $$h(a^n{b}^i{c}^n{d}^j)=h(a^n)h(b^i)h(c^n)h(d^j)=a^n{ϵ}^i{b}^n{ϵ}^j=a^n{b}^n$$

   Also:

   $$h(L)=\{a^n{b}^n\mid n\in \mathbb{N}\}$$

4. Nicht-Regulärität von $h(L)$: Es ist bekannt, dass die Sprache $\{a^n{b}^n\mid n\in \mathbb{N}\}$ nicht regulär ist.

5. Schlussfolgerung: Da $h(L)$ nicht regulär ist und $h$ ein Homomorphismus ist, muss auch die ursprüngliche Sprache $L$ nicht regulär sein.

Fazit:

Durch die Abbildung der Sprache $L$ auf die bekannte nicht-reguläre Sprache $\{a^n{b}^n\mid n\in \mathbb{N}\}$ mittels des Homomorphismus $h$, haben wir gezeigt, dass $L$ nicht regulär ist.

---