Einführung in die Automatentheorie/3. Stunde: Unterschied zwischen den Versionen

Aus ZUM-Unterrichten
main>Fieldman
Markierung: 2017-Quelltext-Bearbeitung
 
(7 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Einführung in die Automatentheorie}}
==Lösungen zu den beiden letzten Aufgaben aus der 2. Stunde==
==Lösungen zu den beiden letzten Aufgaben aus der 2. Stunde==


Zeile 56: Zeile 57:
Der Exponent n (also die Hochzahl) gibt die Anzahl der Folgen des Wortes ha an. Da in diesem Beispiel n>0 ist, muss das Wort ha mindestens einmal vorkommen.
Der Exponent n (also die Hochzahl) gibt die Anzahl der Folgen des Wortes ha an. Da in diesem Beispiel n>0 ist, muss das Wort ha mindestens einmal vorkommen.


:{{Arbeiten|NUMMER=3.1|ARBEIT=
{{Aufgaben|1=3.1|2=
Stelle die Aufgabe 2.6 ('''aaab''', '''aaabaaab''', '''aaabaaabaaab''' usw.) mit der Sprache eines Automaten dar. }}
Stelle die Aufgabe 2.6 ('''aaab''', '''aaabaaab''', '''aaabaaabaaab''' usw.) mit der Sprache eines Automaten dar. }}


Zeile 64: Zeile 65:




:{{Arbeiten|NUMMER=3.2|ARBEIT=
{{Aufgaben|1=3.2|2=
Stelle die Aufgabe 2.5 und 2.6 mit der Sprache eines Automaten dar, wenn der Startzustand auch gleich der Endzustand sein darf. }}
Stelle die Aufgabe 2.5 und 2.6 mit der Sprache eines Automaten dar, wenn der Startzustand auch gleich der Endzustand sein darf. }}


Zeile 81: Zeile 82:




:{{Arbeiten|NUMMER=3.3|ARBEIT=
{{Aufgaben|1=3.3|2=
Konstruiere einen Akzeptor, der folgende Sprache akzeptiert:
Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert:
L={(a<sup>n</sup>b<sup>2</sup>)<math>\| n>0</math>} }}
L={(a<sup>n</sup>b<sup>2</sup>)<math>\| n>0</math>} }}


Zeile 88: Zeile 89:
[[Datei:Zeichnungen_16.jpeg|500px]]<br>}}
[[Datei:Zeichnungen_16.jpeg|500px]]<br>}}


:{{Arbeiten|NUMMER=3.4|ARBEIT=
{{Aufgaben|1=3.4|2=
Konstruiere einen Akzeptor, der folgende Sprache akzeptiert:
Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert:
L={(a<sup>n</sup>b<sup>2</sup>)<math>\| n\geq0</math>} }}
L={(a<sup>n</sup>b<sup>2</sup>)<math>\| n\geq0</math>} }}


Zeile 95: Zeile 96:
[[Datei:Zeichnungen_17.jpeg|500px]]<br>}}
[[Datei:Zeichnungen_17.jpeg|500px]]<br>}}


:{{Arbeiten|NUMMER=3.5|ARBEIT=
{{Aufgaben|1=3.5|2=
Konstruiere einen Akzeptor, der folgende Sprache akzeptiert:
Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert:
L={(ab)<sup>n</sup><math>\| n>0</math>} <math>\cup</math> L={(ba)<sup>n</sup><math>\| n>0</math>}
L={(ab)<sup>n</sup><math>\| n>0</math>} <math>\cup</math> L={(ba)<sup>n</sup><math>\| n>0</math>}
<br>
<br>
Zeile 104: Zeile 105:
[[Datei:Zeichnungen_18.jpeg|500px]]<br>}}
[[Datei:Zeichnungen_18.jpeg|500px]]<br>}}


:{{Arbeiten|NUMMER=3.6|ARBEIT=
{{Aufgaben|1=3.6|2=
Konstruiere einen Akzeptor, der folgende Email-Adressen erkennt:<br>
Konstruiere einen Akzeptor, der nur die folgenden Email-Adressen erkennt:<br>
{min. ein Zeichen}@{mind. 3 Zeichen}.de <br>
{min. ein Zeichen}@{mind. 3 Zeichen}.de <br>
wobei ein Zeichen ein Element aus der Menge {a,...,z,A,...,Z,0,...9,+,-,_} sein soll.  
wobei ein Zeichen ein Element aus der Menge {a,...,z,A,...,Z,0,...9,+,-,_} sein soll.  
Zeile 114: Zeile 115:
[[Datei:Zeichnungen_19.jpeg|500px]]<br>}}
[[Datei:Zeichnungen_19.jpeg|500px]]<br>}}


:{{Arbeiten|NUMMER=3.7|ARBEIT=
{{Aufgaben|1=3.7|2=
Konstruiere einen Akzeptor, der alle Wörter akzeptiert, die eine gerade Anzahl von a's enthalten (die Zahl 0 wird hier als gerade interpretiert). Das Eingabealphabet ist dabei die Menge {a,b,c}. Der Automat soll zum Beispiel das Wort abacbaa akzeptieren, aber das Wort abacba verwerfen.
Konstruiere einen Akzeptor, der nur die Wörter akzeptiert, die eine gerade Anzahl von a's enthalten (die Zahl 0 wird hier als gerade interpretiert). Das Eingabealphabet ist dabei die Menge {a,b,c}. Der Automat soll zum Beispiel das Wort abacbaa akzeptieren, aber das Wort abacba verwerfen.
}}
}}


{{Lösung versteckt|1=
{{Lösung versteckt|1=
[[Datei:Zeichnungen_20.jpeg|500px]]<br>}}
[[Datei:Zeichnungen_20.jpeg|500px]]<br>}}
{{Fortsetzung|weiter=weiter mit der 4. Stunde|weiterlink=Einführung in die Automatentheorie/4. Stunde}}
{{Einführung in die Automatentheorie}}

Aktuelle Version vom 10. August 2019, 12:52 Uhr

Lösungen zu den beiden letzten Aufgaben aus der 2. Stunde

Aufgabe 2.5

Hier eine mögliche Lösung:

Zeichnungen 9.jpeg

Aufgabe 2.6

Hier eine mögliche Lösung:

Zeichnungen 10.jpeg





Bei beiden Aufgaben darf der Startzustand nicht gleich dem Endzustand sein.
Zeichnungen 12.jpegZeichnungen 11.jpeg
Überlege dir warum?

Ansonsten könnten wir auch nichts eingeben und wären am Ziel.

Akzeptanzverhalten

Die Aufgabe eines Automaten besteht oft darin, eine Eingabe auf Korrektheit zu überprüfen.
Eine Eingabe, bestehend aus einer Folge von Zeichen aus dem Eingabealphabet, wird genau dann von dem Automaten akzeptiert, wenn der Automat einen Endzustand erreicht.

So wird zum Beispiel bei Aufgabe 2.5 die Eingabe haha akzeptiert, aber hah nicht.

Die Automaten aus Aufgabe 2.5 und 2.6 gehören zu den endlich erkennenden Automaten.

Definition

Ein endlich erkennender Automat (Akzeptor) besteht aus den folgenden Bestandteilen:

  • das Eingabealphabet E
  • die endliche Menge der Zustände Z
  • ein Startzustand
  • mindestens einen Endzustand
  • eine Übergangsfunktion f, die den Zeichen E und Zustand Z genau einen neuen Zustand zuordnet





Sprache des Automaten

Gelangt der Automat in den Akzeptierzustand, so bezeichnen wir die dazu notwendige Eingabefolge als ein Wort des Automaten. Die Menge aller akzeptierten Eingabefolgen, die man Wörter nennt, bezeichnen wir als Sprache des Automaten L.

Definition

Die Sprache eines Automaten L ist die Menge aller von ihm akzeptierten Wörter über dem Eingabealphabet E.




Schauen wir uns dazu nochmal die Aufgabe 2.5 an, bei der wir einen Automaten konstruieren sollten, der die Wörter ha, haha, hahaha usw. akzeptiert.

Die Aufgabe hätte auch so lauten können:
Konstruiere einen Automaten, der die Sprache L={(ha)n|n>0} akzeptiert.
Der Exponent n (also die Hochzahl) gibt die Anzahl der Folgen des Wortes ha an. Da in diesem Beispiel n>0 ist, muss das Wort ha mindestens einmal vorkommen.

Aufgabe 3.1
Stelle die Aufgabe 2.6 (aaab, aaabaaab, aaabaaabaaab usw.) mit der Sprache eines Automaten dar.


Zeichnungen 13.jpeg


Aufgabe 3.2
Stelle die Aufgabe 2.5 und 2.6 mit der Sprache eines Automaten dar, wenn der Startzustand auch gleich der Endzustand sein darf.


Zeichnungen 14.jpeg

Übungsaufgaben zu endlichen Automaten (Akzeptoren)

Hinweise:


  • Ein Automat kann auch mehrere Endzustände besitzen.
  • Auf einer Übergangsfunktion können auch mehrere Zeichen vorhanden sein.
 Zeichnungen 15.jpeg

 Der Zustand von z1 nach z2 erfolgt, wenn a oder b gelesen wird.


Aufgabe 3.3

Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert:

L={(anb2)}


Zeichnungen 16.jpeg

Aufgabe 3.4

Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert:

L={(anb2)}


Zeichnungen 17.jpeg

Aufgabe 3.5

Konstruiere einen Akzeptor, der nur die folgende Sprache akzeptiert: L={(ab)n} L={(ba)n}

Hinweis: Die Vereinigungsmenge wird hier als oder interpretiert.


Zeichnungen 18.jpeg

Aufgabe 3.6

Konstruiere einen Akzeptor, der nur die folgenden Email-Adressen erkennt:
{min. ein Zeichen}@{mind. 3 Zeichen}.de
wobei ein Zeichen ein Element aus der Menge {a,...,z,A,...,Z,0,...9,+,-,_} sein soll.


Du kannst das Zeichen mit z bezeichnen, also z {a,...,z,A,...,Z,0,...9,+,-,_ }


Zeichnungen 19.jpeg

Aufgabe 3.7
Konstruiere einen Akzeptor, der nur die Wörter akzeptiert, die eine gerade Anzahl von a's enthalten (die Zahl 0 wird hier als gerade interpretiert). Das Eingabealphabet ist dabei die Menge {a,b,c}. Der Automat soll zum Beispiel das Wort abacbaa akzeptieren, aber das Wort abacba verwerfen.


Zeichnungen 20.jpeg



weiter mit der 4. Stunde
Abgerufen von „https://unterrichten.zum.de/index.php?title=Einführung_in_die_Automatentheorie/3._Stunde&oldid=97245“