Informatik I - Tutorium Wintersemester 2007/08
Christian Julg
http://infotut.blogspot.com
17. Dezember 2007
Universitt Karlsruhe (TH)Forschungsuniversitt gegrndet 1825
Quellennachweis & Dank an:Susanne Dinkler, Philipp Kern, Bernhard Muller, Joachim Wilke
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Ubersicht
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Wenn doch noch Fragen auftauchen...
Kontakt
Kontakt: [email protected]
Homepage: http://infotut.blogspot.com
bitte beachten:
Im Betreff der Emails [08] einfugen!
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Wenn doch noch Fragen auftauchen...
Kontakt
Kontakt: [email protected]
Homepage: http://infotut.blogspot.com
bitte beachten:
Im Betreff der Emails [08] einfugen!
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Organisatorisches
Rechnerubung
Nachste normale RU mit Anmeldung am Di, 18.12. im RZ, Pool B- aber nur wenn es Anmeldungen gibt. Anmeldung per Email oderdirekt im Tut.
Blatt 7
Semi-Thue und Markov: Alle Termersetzungssysteme mussenausreichend kommentiert werden.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Und nochmal...
Bei Semi-Thue-Systemen...
1 ... muss man auf die Reihenfolge der Regeln achten.
2 ... kann man zu unterschiedlichen Ergebnissen kommen, wennmehr als eine Regel anwendbar ist.
3 ... kann man an der Farbe der Regel ihre Prioritat erkennen.
Nach Anwendung des Warshall-Algorithmus ist ein Graph...
1 ... reflexiv.
2 ... transitiv.
3 ... symmetrisch.
$a $b ist ...1 ... in disjunktiver Normalform.
2 ... in konjunktiver Normalform.
3 ... keines von beidem.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Und nochmal...
Bei Semi-Thue-Systemen...
1 ... muss man auf die Reihenfolge der Regeln achten.
2 ... kann man zu unterschiedlichen Ergebnissen kommen, wennmehr als eine Regel anwendbar ist.
3 ... kann man an der Farbe der Regel ihre Prioritat erkennen.
Nach Anwendung des Warshall-Algorithmus ist ein Graph...
1 ... reflexiv.
2 ... transitiv.
3 ... symmetrisch.
$a $b ist ...1 ... in disjunktiver Normalform.
2 ... in konjunktiver Normalform.
3 ... keines von beidem.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Und nochmal...
Bei Semi-Thue-Systemen...
1 ... muss man auf die Reihenfolge der Regeln achten.
2 ... kann man zu unterschiedlichen Ergebnissen kommen, wennmehr als eine Regel anwendbar ist.
3 ... kann man an der Farbe der Regel ihre Prioritat erkennen.
Nach Anwendung des Warshall-Algorithmus ist ein Graph...
1 ... reflexiv.
2 ... transitiv.
3 ... symmetrisch.
$a $b ist ...1 ... in disjunktiver Normalform.
2 ... in konjunktiver Normalform.
3 ... keines von beidem.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Und nochmal...
Bei Semi-Thue-Systemen...
1 ... muss man auf die Reihenfolge der Regeln achten.
2 ... kann man zu unterschiedlichen Ergebnissen kommen, wennmehr als eine Regel anwendbar ist.
3 ... kann man an der Farbe der Regel ihre Prioritat erkennen.
Nach Anwendung des Warshall-Algorithmus ist ein Graph...
1 ... reflexiv.
2 ... transitiv.
3 ... symmetrisch.
$a $b ist ...1 ... in disjunktiver Normalform.
2 ... in konjunktiver Normalform.
3 ... keines von beidem.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Ubungsblatt 6
Kurzer Ruckblick...
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Ubungsblatt 6
Kurzer Ruckblick...
Fragen?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue
Aufbau
Semi-Thue-Systeme bestehen aus
Zeichenvorrat und
Menge der Termersetzungsregeln T
Regeln in T werden mit dargestellt.Beispiel: = {|} und T = { ||| , |||}
Anwendung
Semi-Thue-Systeme sind nicht an ein Startwort gebunden undterminieren nur, wenn sie fur jedes Wort aus terminieren.Die Reihenfolge der Regeln ist beliebig. - Produktionen terminieren nie.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue
Los gehts
Gib ein Semi-Thue-System an, mit dem man die Anzahl derStriche halbieren kann.Dazu sei die Anzahl immer gerade und die Striche von zwei aumschlossen: Bsp: a||||aGib die Ableitung von a||||a an.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue
Los gehts
Gib ein Semi-Thue-System an, mit dem man die Anzahl derStriche halbieren kann.Dazu sei die Anzahl immer gerade und die Striche von zwei aumschlossen: Bsp: a||||aGib die Ableitung von a||||a an.
Losung
= { a, | }T = { a|||a , aa }a||||a | a || a || aa ||
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue
Losung
= { a, | }T = { a|||a , aa }a||||a | a || a || aa ||
was tun bei ungerader Anzahl?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue
Losung
= { a, | }T = { a|||a , aa }a||||a | a || a || aa ||
was tun bei ungerader Anzahl?
zusatzliche Regel: a|a
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Semi-Thue: Hinweis
Hinweis zu den Pfeilen
ist nicht das gleiche wie
:
bei der Regeldefinition, bei der Regelanwendung.
Hinweis zum Entwurf von Regelsystemen
Wenn eigene Regelsysteme entwickelt werden, dann muss jedeRegel kommentiert werden, damit es nachvollziehbar ist.Gilt insbesondere fur Markov-Systeme.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
2. Aufgabe
Und nochmal
Erstellt in eurer Gruppe eine Semi-Thue-Termersetzung mit = {a, b, c}, sodass aus jedem Startwort nur die WorteL = {a, b, c, ab, ac, bc, abc} abgeleitet werden.
Losung
1 ba ab2 ca ac3 cb bc
4 aa a5 bb b6 cc c
Die ersten 3 Regeln ordnen das Wort, wahrend die letzten 3 Regelnmehrfach vorkommende Zeichen entfernen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
2. Aufgabe
Und nochmal
Erstellt in eurer Gruppe eine Semi-Thue-Termersetzung mit = {a, b, c}, sodass aus jedem Startwort nur die WorteL = {a, b, c, ab, ac, bc, abc} abgeleitet werden.
Losung
1 ba ab2 ca ac3 cb bc
4 aa a5 bb b6 cc c
Die ersten 3 Regeln ordnen das Wort, wahrend die letzten 3 Regelnmehrfach vorkommende Zeichen entfernen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
2. Aufgabe
Und nochmal
Erstellt in eurer Gruppe eine Semi-Thue-Termersetzung mit = {a, b, c}, sodass aus jedem Startwort nur die WorteL = {a, b, c, ab, ac, bc, abc} abgeleitet werden.
Losung
1 ba ab2 ca ac3 cb bc
4 aa a5 bb b6 cc c
Die ersten 3 Regeln ordnen das Wort, wahrend die letzten 3 Regelnmehrfach vorkommende Zeichen entfernen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
2. Aufgabe
Und nochmal
Erstellt in eurer Gruppe eine Semi-Thue-Termersetzung mit = {a, b, c}, sodass aus jedem Startwort nur die WorteL = {a, b, c, ab, ac, bc, abc} abgeleitet werden.
Losung
1 ba ab2 ca ac3 cb bc
4 aa a5 bb b6 cc c
Die ersten 3 Regeln ordnen das Wort, wahrend die letzten 3 Regelnmehrfach vorkommende Zeichen entfernen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Auf hoher See
Nachteile von Semi-Thue-Systemen:
Regeln lassen sich nicht kontrolliert anwenden.
Daher fur Markov-Algorithmen folgende Meta-Regeln:
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Auf hoher See
Nachteile von Semi-Thue-Systemen:
Regeln lassen sich nicht kontrolliert anwenden.
Daher fur Markov-Algorithmen folgende Meta-Regeln:
1 Wende stets die erste mogliche Regel an.
2 Wende sie so weit links wie moglich an.
3 Nach einer Halteregel () beende den Algorithmus4 (Wenn keine Regel anwendbar ist, beende den Algorithmus)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Auf hoher See
1 Wende stets die erste mogliche Regel an.
2 Wende sie so weit links wie moglich an.
3 Nach einer Halteregel () beende den Algorithmus4 (Wenn keine Regel anwendbar ist, beende den Algorithmus)
Schiffchen
oft mochte manwissen, wo man gerade ist.
dazu fuhrt man Zeichen ein, die nicht in der Eingabe warenund spater wieder geloscht werden.
diese nennt man Schiffchen.
werden meist durch griechische Buchstaben dargestellt.(, , ,. . . )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Verdoppeln
Los gehts
Schreibe einen Markov-Algorithmus, der die Anzahl der Striche|
verdoppelt.
Losung
1 | 2 3
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Verdoppeln
Los gehts
Schreibe einen Markov-Algorithmus, der die Anzahl der Striche|
verdoppelt.
Losung
1 | 2 3
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Sortieren
Und noch mal
Sortiere mit einem Markov-Algorithmus die Zeichen in einem Wortuber = {a, b, c, d}.Ist dies auch mit einem Semi-Thue-System moglich?
Losung
1 ba ab2 ca ac3 cb bc4 da ad5 db bd6 dc cd7
Ja, das ist ohne weiteresmit den Regeln 1-6 auchals Semi-Thue-System zulosen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Sortieren
Und noch mal
Sortiere mit einem Markov-Algorithmus die Zeichen in einem Wortuber = {a, b, c, d}.Ist dies auch mit einem Semi-Thue-System moglich?
Losung
1 ba ab2 ca ac3 cb bc4 da ad5 db bd6 dc cd7
Ja, das ist ohne weiteresmit den Regeln 1-6 auchals Semi-Thue-System zulosen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Sortieren
Und noch mal
Sortiere mit einem Markov-Algorithmus die Zeichen in einem Wortuber = {a, b, c, d}.Ist dies auch mit einem Semi-Thue-System moglich?
Losung
1 ba ab2 ca ac3 cb bc4 da ad5 db bd6 dc cd7
Ja, das ist ohne weiteresmit den Regeln 1-6 auchals Semi-Thue-System zulosen.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Was sind Grammatiken?
Markov-Algorithmen sind eine Variante der Semi-Thue-Systememit sinnvollen Einschrankungen. Fur Grammatiken kann man dasahnlich machen:
Trennung des Alphabets in Terminalsymbole undNicht-Terminale N.
Die Regeln heien Produktionen und stecken in der Menge P.
Man hat keine Eingabe, sondern beginnt immer mit demgleichen Symbol A, genannt Axiom (sinnvollerweise einNicht-Terminal).
Das ganze packt man in ein 4er-Tupel (oder Quadrupel)G = (,N,P,A) und nennt es Grammatik.
Statt fur eindeutige Ableitungsergebnisse interessieren wir unsfur alle moglichen Ableitungen des Axioms A aus , genanntdie Sprache der Grammatik und geschrieben L(G )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Was sind Grammatiken?
Markov-Algorithmen sind eine Variante der Semi-Thue-Systememit sinnvollen Einschrankungen. Fur Grammatiken kann man dasahnlich machen:
Trennung des Alphabets in Terminalsymbole undNicht-Terminale N.
Die Regeln heien Produktionen und stecken in der Menge P.
Man hat keine Eingabe, sondern beginnt immer mit demgleichen Symbol A, genannt Axiom (sinnvollerweise einNicht-Terminal).
Das ganze packt man in ein 4er-Tupel (oder Quadrupel)G = (,N,P,A) und nennt es Grammatik.
Statt fur eindeutige Ableitungsergebnisse interessieren wir unsfur alle moglichen Ableitungen des Axioms A aus , genanntdie Sprache der Grammatik und geschrieben L(G )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Was sind Grammatiken?
Markov-Algorithmen sind eine Variante der Semi-Thue-Systememit sinnvollen Einschrankungen. Fur Grammatiken kann man dasahnlich machen:
Trennung des Alphabets in Terminalsymbole undNicht-Terminale N.
Die Regeln heien Produktionen und stecken in der Menge P.
Man hat keine Eingabe, sondern beginnt immer mit demgleichen Symbol A, genannt Axiom (sinnvollerweise einNicht-Terminal).
Das ganze packt man in ein 4er-Tupel (oder Quadrupel)G = (,N,P,A) und nennt es Grammatik.
Statt fur eindeutige Ableitungsergebnisse interessieren wir unsfur alle moglichen Ableitungen des Axioms A aus , genanntdie Sprache der Grammatik und geschrieben L(G )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Was sind Grammatiken?
Markov-Algorithmen sind eine Variante der Semi-Thue-Systememit sinnvollen Einschrankungen. Fur Grammatiken kann man dasahnlich machen:
Trennung des Alphabets in Terminalsymbole undNicht-Terminale N.
Die Regeln heien Produktionen und stecken in der Menge P.
Man hat keine Eingabe, sondern beginnt immer mit demgleichen Symbol A, genannt Axiom (sinnvollerweise einNicht-Terminal).
Das ganze packt man in ein 4er-Tupel (oder Quadrupel)G = (,N,P,A) und nennt es Grammatik.
Statt fur eindeutige Ableitungsergebnisse interessieren wir unsfur alle moglichen Ableitungen des Axioms A aus , genanntdie Sprache der Grammatik und geschrieben L(G )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Was sind Grammatiken?
Markov-Algorithmen sind eine Variante der Semi-Thue-Systememit sinnvollen Einschrankungen. Fur Grammatiken kann man dasahnlich machen:
Trennung des Alphabets in Terminalsymbole undNicht-Terminale N.
Die Regeln heien Produktionen und stecken in der Menge P.
Man hat keine Eingabe, sondern beginnt immer mit demgleichen Symbol A, genannt Axiom (sinnvollerweise einNicht-Terminal).
Das ganze packt man in ein 4er-Tupel (oder Quadrupel)G = (,N,P,A) und nennt es Grammatik.
Statt fur eindeutige Ableitungsergebnisse interessieren wir unsfur alle moglichen Ableitungen des Axioms A aus , genanntdie Sprache der Grammatik und geschrieben L(G )
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Chomsky-Hierarchie
Wir konnen die Grammatiken in vier Klassen einteilen, Chomsky-0bis Chomsky-3. Dabei gilt:
Chomsky-n ) Chomsky-(n + 1)Je kleiner die Nummer, desto machtiger kann die Grammatiksein
Chomsky-0 ist so gut wie Semi-Thue und Markov
Chomsky-2-Grammatiken sind aquivalent zur(Erweiterten-)Backus-Naur-Form
Auch die Sprachen werden in diese Klassen gepackt: JedeSprache hat die Chomsky-Klasse der einfachsten Grammatik,die sie erzeugt. (Einfach = groe Chomsky-Nummer)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Chomsky-Hierarchie - Definition
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,A,B,C},P, {S})mit den folgenden Produktionen:
1 S AB2 A a3 Ab aab4 B b5 B C6 C cCc7 C c
Gib die Chomsky-Klasse von G ,L(G ) sowie die Klasse von L(G ) an.
Losung
Die Grammatik ist inCH-1: Regel 3 istkontext-sensitiv, aber alleRegeln sindlangenbeschrankt.
L(G ) = {ab, aab} {ac2n+1|n N0}L(G ) ist CH-3 (
regular)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,A,B,C},P, {S})mit den folgenden Produktionen:
1 S AB2 A a3 Ab aab4 B b5 B C6 C cCc7 C c
Gib die Chomsky-Klasse von G ,L(G ) sowie die Klasse von L(G ) an.
Losung
Die Grammatik ist inCH-1: Regel 3 istkontext-sensitiv, aber alleRegeln sindlangenbeschrankt.
L(G ) = {ab, aab} {ac2n+1|n N0}L(G ) ist CH-3 (
regular)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,A,B,C},P, {S})mit den folgenden Produktionen:
1 S AB2 A a3 Ab aab4 B b5 B C6 C cCc7 C c
Gib die Chomsky-Klasse von G ,L(G ) sowie die Klasse von L(G ) an.
Losung
Die Grammatik ist inCH-1: Regel 3 istkontext-sensitiv, aber alleRegeln sindlangenbeschrankt.
L(G ) = {ab, aab} {ac2n+1|n N0}
L(G ) ist CH-3 (regular)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 1: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,A,B,C},P, {S})mit den folgenden Produktionen:
1 S AB2 A a3 Ab aab4 B b5 B C6 C cCc7 C c
Gib die Chomsky-Klasse von G ,L(G ) sowie die Klasse von L(G ) an.
Losung
Die Grammatik ist inCH-1: Regel 3 istkontext-sensitiv, aber alleRegeln sindlangenbeschrankt.
L(G ) = {ab, aab} {ac2n+1|n N0}L(G ) ist CH-3 (
regular)
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,B,C},P, {S})P = {
1 S aSBC2 S aBC3 CB BC4 aB ab5 bB bb6 bC bc7 cC cc} Gib L(G ) und die Chomsky-Klassevon G an.
Losung
Die Grammatik ist inCH-1: Regeln 3-7 istkontext-sensitiv und alleRegeln sindlangenbeschrankt.
L(G ) = {anbncn}L(G ) ist auch CH-1
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,B,C},P, {S})P = {
1 S aSBC2 S aBC3 CB BC4 aB ab5 bB bb6 bC bc7 cC cc} Gib L(G ) und die Chomsky-Klassevon G an.
Losung
Die Grammatik ist inCH-1: Regeln 3-7 istkontext-sensitiv und alleRegeln sindlangenbeschrankt.
L(G ) = {anbncn}L(G ) ist auch CH-1
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,B,C},P, {S})P = {
1 S aSBC2 S aBC3 CB BC4 aB ab5 bB bb6 bC bc7 cC cc} Gib L(G ) und die Chomsky-Klassevon G an.
Losung
Die Grammatik ist inCH-1: Regeln 3-7 istkontext-sensitiv und alleRegeln sindlangenbeschrankt.
L(G ) = {anbncn}
L(G ) ist auch CH-1
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Beispiel 2: Chomskygrammatiken und -Sprachen
Aufgabe
Gegeben ist die GrammatikG = ({a, b, c}, {S ,B,C},P, {S})P = {
1 S aSBC2 S aBC3 CB BC4 aB ab5 bB bb6 bC bc7 cC cc} Gib L(G ) und die Chomsky-Klassevon G an.
Losung
Die Grammatik ist inCH-1: Regeln 3-7 istkontext-sensitiv und alleRegeln sindlangenbeschrankt.
L(G ) = {anbncn}L(G ) ist auch CH-1
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c
V1 Assoziativitat (x y) z = x (y z)(x y) z = x (y z)
V2 Kommutativitat x y = y x x y = y xV3 Idempotenz x x = x x x = xV4 Verschmelzung (x y) x = x (x y) x = xV5 Distributivitat x (y z) = (x y) (x z)
x (y z) = (x y) (x z)V6 Modularitat (fur z x) x (y z) = (x y) zV7 Neutrales Element x = x = x
x > = x x > = >V8 Komplement x $x = x $x = >V9 Involution $($x) = xV10 DeMorgan $(x y) = $x $y $(x y) = $x $y
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c
(b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat
$c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat
($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat
($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat
($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement
($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element
($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element
($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat
(a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Holz hacken - Losung
Ubungsaufgabe
Geben sie eine DNF fur folgenden Term an:(b c) (b a) $c (b (c a)) $c Distributivitat $c (b (c a)) Kommutativitat ($c b) ($c (c a)) Distributivitat ($c b) (($c c) a) Assoziativitat ($c b) ( a) Komplement ($c b) Neutrales Element ($c b) (a $a) Neutrales Element ($c b a) ($c b $a) Distributivitat (a b $c) ($a b $c) 6x Kommutativitat
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Chomsky-Hierarchie
Ganz einfache Computer
Eine Maschine soll zu einer eingegebenen Zeichenreihe feststellen,ob diese Zeichenreihe zu einer Sprache gehort (oder ob nicht).Es besteht ein enger Zusammenhang zwischen den durchGrammatiken erzeugten Sprachen und den Maschinen.
CH-0 Turing-Maschine
CH-1 Linear beschrankter Automat
CH-2 Kellerautomat
CH-3 Endlicher Automat
Eine vertiefte Behandlung des Zusammenhangs zwischen Sprachenund Maschinen ist Teil der Berechenbarkeitstheorie (Info 3).
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Endlich ein Automat!
Wozu?
Ein endlicher Automat ist gerade machtig genug, um ein Spracheaus CH-3 zu entscheiden. Der Vorteil von endlichen Automaten ist,dass sie sehr einfach zu implementieren sind.
Was braucht man?
endliche Menge Q von Zustanden
ein Anfangszustand q0 QZeichenvorrat
Regeln fur die Zustandsubergange
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Endlich ein Automat!
Wie arbeitet er?
Das Lesen eines Zeichens a fuhrt zu einem Zustandsubergangvom aktuellen Zustand q Q in einen neuen Zustand q Q
Notation: qa qDer Zustand lat sich als Gedachtnis uber die Vorgeschichte,also die bisher eingegebenen Zeichen, auffassen.Dieses ist allerdings immer endlich!
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Darstellung von endlichen Automaten als Graphen
Zustande Q = {q0, q1, . . . , qn}des endlichen Automaten lassensich als Ecken eines Graphenauffassen
q0 q1 qn
Zustandsubergange qia qj mita entsprechen markiertengerichteten Kanten
qi qja
Ein im endlichen Automaten erreichter Zustand qk ist durch denAnfangszustand q0 und die bisher eingegebene Zeichenreihex = x1 . . . xi bestimmtDie Graph-Notation ist hierbei: q0 + qk bzw. q0 qk
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Arten von Automaten
Es gibt zwei Arten, wie ein Automat eine Ausgabe haben kann.Wir unterscheiden dabei:
Mealy-Automat erzeugt eine Ausgabe bei jedemZustandsubergangKanten markiert mit a/ti
Moore-Automat Erzeugung einer Ausgabe bei Erreichen einesZustands
In beiden Fallen ist die Ausgabe ein Wort t = t0 . . . tn1 ubereinem Ausgabezeichenvorrat T . Die Ausgabe kann offensichtlichnicht langer sein als das Eingabewort.
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Der Akzeptor
Ist der haufigste Spezialfall eines Moore-Automaten
Eine Ausgabe findet nicht bei allen Zustanden statt
Die Zustande F Q, bei denen eine Ausgabe erfolgt, heienEndzustande
Das ausgegebene Wort t T hangt nur vom erreichtenEndzustand q F ab
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Akzeptoren unter der Lupe
Ein Akzeptor heit vollstandig, wenn fur jeden Zustand undjede Eingabe ein neuer Zustand definiert ist. Dies kann immerdurch die Einfuhrung eines Fehlerzustandes geschehen.
Ein endlicher Akzeptor lasst sich als Quintupel(,Q, q0,F ,P) auffassen:
ZeichenvorratQ nichtleere endliche Zustandsmengeq0 Anfangszustand aus QF nichtleere Menge von Endzustanden aus QP Ubergange qa q mit q, q Q, a
Die Sprache, die der Akzeptor akzeptiert:L(A) = {x |x , q0x qe , qe F}
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
1 OrganisatorischesWiederholung
2 Ubungsblatt 6
3 Semi-Thue-Termersetzungen
4 Markov-Algorithmus
5 Grammatiken
6 Boolsche Algebra: Normalform - Beispiel
7 Endliche Automaten
8 EndeFeedback
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw.DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist ein Binarbaum und wie ist seine Hohe definiert?
Wie wandle ich einen boolschen Ausdruck in seine KNF bzw. DNF um?
Wie unterscheiden sich Semi-Thue, Markov?
Was sind Grammatiken und woraus bestehen sie?
Wie sind die Stufen der Chomsky-Hierarchie definiert?
Was macht ein endlicher Automat?
Ihr wisst was nicht?
Stellt jetzt Fragen!
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
War ich zu schnell? Zu langsam?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
War ich zu schnell? Zu langsam?
Habe ich bestimmte Sachen zu kurz behandelt?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
War ich zu schnell? Zu langsam?
Habe ich bestimmte Sachen zu kurz behandelt?
Was kann ich verbessern?
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Eulenfest - 15.01.2008
Informatik I - Tutorium Christian Julg
Orga Blatt 6 Semi-Thue Markov Grammatiken Boolsche Algebra Endliche Automaten Ende
Informatik I - Tutorium Christian Julg
OrganisatorischesWiederholung
bungsblatt 6Semi-Thue-TermersetzungenMarkov-AlgorithmusGrammatikenBool'sche Algebra: Normalform - BeispielEndliche AutomatenEndeFeedback