Revision history for AutomatentheorieUndFormaleSprachen
Deletions:
~-Skript (SkriptAtfsEckNr1, SkriptAtfsEckNr2)
~-Schoening2008
~-Mitschrift
~-Übungen (Eck)
~-Übungen (Vorlesung)
Additions:
==a==Menschen==a==
[[http://en.wikipedia.org/wiki/Noam_Chomsky Avram Noam Chomsky]]
[[http://en.wikipedia.org/wiki/Noam_Chomsky Avram Noam Chomsky]]
Additions:
==a==Tools==a==
**bnfc (Linux)**
The BNF Converter is a compiler construction tool that generates a compiler front-end and a readable syntax description document from a Labelled BNF grammar. It was originally written to generate Haskell, but it can now also be used for generating Java, C++, and C.
To process C or C++ output, you need a C or C++ compiler, respectively, the Bison parser generator (package bison) and the flex scanner generator (package flex). Homepage: http://www.cs.chalmers.se/~markus/BNFC/
**bnfc (Linux)**
The BNF Converter is a compiler construction tool that generates a compiler front-end and a readable syntax description document from a Labelled BNF grammar. It was originally written to generate Haskell, but it can now also be used for generating Java, C++, and C.
To process C or C++ output, you need a C or C++ compiler, respectively, the Bison parser generator (package bison) and the flex scanner generator (package flex). Homepage: http://www.cs.chalmers.se/~markus/BNFC/
Additions:
~-[[PumpingLemma Pumping Lemma]]
Additions:
~-[[ChomskyHierarchie Chomsky-Hierarchie]]
Additions:
~-Skript (SkriptAtfsEckNr1, SkriptAtfsEckNr2)
~-Schoening2008
~-Mitschrift
~-Übungen (Eck)
~-Übungen (Vorlesung)
~-Schoening2008
~-Mitschrift
~-Übungen (Eck)
~-Übungen (Vorlesung)
Deletions:
Schoening2008
Siehe auch Notizen und Übungen
Additions:
~-Backus-Naur-Form [[http://de.wikipedia.org/wiki/Backus-Naur-Form W]], (SkriptAtfsEckNr2, S. 9)
Deletions:
Additions:
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten ]] (DEA)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten]] (NEA)
~-[[FormaleSprachen Formale Sprachen]]
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]]
~-[[AtfsProduktionen Grammatik und Produktionen]]
~-Backus-Naur-Form [[http://de.wikipedia.org/wiki/Backus-Naur-Form W]]
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten]] (NEA)
~-[[FormaleSprachen Formale Sprachen]]
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]]
~-[[AtfsProduktionen Grammatik und Produktionen]]
~-Backus-Naur-Form [[http://de.wikipedia.org/wiki/Backus-Naur-Form W]]
Deletions:
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten]] (NEA), (SkriptAtfsEckNr1, S. 19)
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEckNr1, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEckNr1, S. 33)
~-[[AtfsProduktionen Grammatik und Produktionen]], (SkriptAtfsEckNr2, S. 47)
~-Backus-Naur-Form [[http://de.wikipedia.org/wiki/Backus-Naur-Form W]], (SkriptAtfsEckNr1, S. 9)
Additions:
~-[[AtfsProduktionen Grammatik und Produktionen]], (SkriptAtfsEckNr2, S. 47)
Deletions:
Additions:
~-Backus-Naur-Form [[http://de.wikipedia.org/wiki/Backus-Naur-Form W]], (SkriptAtfsEckNr1, S. 9)
Additions:
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten ]] (DEA), (SkriptAtfsEckNr1, S. 15)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten]] (NEA), (SkriptAtfsEckNr1, S. 19)
~-Kellerautomaten (Schoening2008, S. 97)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten]] (NEA), (SkriptAtfsEckNr1, S. 19)
~-Kellerautomaten (Schoening2008, S. 97)
Deletions:
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA)]], (SkriptAtfsEckNr1, S. 19)
Additions:
~-[[AtfsProduktionen Produktionen]], Ersetzungsregeln, (SkriptAtfsEckNr2, S. 47)
Deletions:
Additions:
==a==Zustandsautomaten und formale Sprachen==a==
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEckNr1, S. 15)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA)]], (SkriptAtfsEckNr1, S. 19)
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEckNr1, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEckNr1, S. 33)
~-Produktionen: Ersetzungsregeln, (SkriptAtfsEckNr2, S. 47)
==a==Material==a==
Skript
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEckNr1, S. 15)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA)]], (SkriptAtfsEckNr1, S. 19)
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEckNr1, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEckNr1, S. 33)
~-Produktionen: Ersetzungsregeln, (SkriptAtfsEckNr2, S. 47)
==a==Material==a==
Skript
Deletions:
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEck, S. 15)
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA)]], (SkriptAtfsEck, S. 19)
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEck, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEck, S. 33)
Deletions:
Additions:
==a==Grundlagen==a==
~-[[MathematikQuantoren Quantoren]]
~-[[MathematikPraedikate Prädikate]]
~-[[MathematikMengen Mengen]]
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEck, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEck, S. 33)
.,
~-[[MathematikQuantoren Quantoren]]
~-[[MathematikPraedikate Prädikate]]
~-[[MathematikMengen Mengen]]
~-[[FormaleSprachen Formale Sprachen]], (SkriptAtfsEck, S. 25)
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]], (SkriptAtfsEck, S. 33)
.,
Deletions:
[[MathematikQuantoren Quantoren]]
[[MathematikPraedikate Prädikate]]
[[MathematikMengen Mengen]]
~-[[FormaleSprachen Formale Sprachen]]
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]]
Deletions:
Zeichen: Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen: Wörter, Sätze, Satzgefüge
in der Theorie: Wörter über Alphabet
S ist ein Alphabet
S = {a,b,c,x,k,l,...,z}
===Mengen===
S ist eine Menge
S = {o, t}
//o und t sind Elemente der Menge S//
s ∈ S
//s ist eine Element der Menge S//
S""<sup>+</sup>""
//beschreibt Wörter über S mit mindestens einem Zeichen//
Beispiele:
s = o
s = t
s = ot
s = to
s = otto
S* beschreibt Wörter über S mit mindestens einem Zeichen oder ein leeres Wort (enthält kein Zeichen)
s = t
s = otto
s = ∅
s = s""<sub>0</sub>"" s""<sub>1</sub>"" ... s""<sub>n</sub>"", s""<sub>i</sub>"" ∈ S
===Länge===
s = otto
|s| = 4
|otto| = 4
|s|""<sub>x</sub>""
ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
leeres Wort |epsilon| = 0
""|0110101|<sub>1</sub>"" = 4
""|0110101|<sub>0</sub>"" = 3
""|0110101|<sub>2</sub>"" = 0
===Konkatenation===
[[http://de.wikipedia.org/wiki/Konkatenation_(Formale_Sprache)#Konkatenation Konkatenation]]: Verkettung, Hintereinanderschreiben
s = s""<sub>0</sub>"" s""<sub>1</sub>"" s""<sub>2</sub>"" ... s""<sub>n</sub>"" |s| = n + 1
t = t""<sub>0</sub>"" t""<sub>1</sub>"" t""<sub>2</sub>"" ... t""<sub>m</sub>"" |t| = m + 1
Kat(s,t) = st |st| = n+m+2
Wirkung von Epsilon:
Kat(eps, s) = epss = s = seps = Kat(s,eps)
Additions:
S ist eine Menge
S = {o, t}
//o und t sind Elemente der Menge S//
s ∈ S
//s ist eine Element der Menge S//
S""<sup>+</sup>""
//beschreibt Wörter über S mit mindestens einem Zeichen//
Beispiele:
s = o
s = t
s = ot
s = to
s = otto
s = t
s = otto
s = ∅
s = s""<sub>0</sub>"" s""<sub>1</sub>"" ... s""<sub>n</sub>"", s""<sub>i</sub>"" ∈ S
s = otto
|s| = 4
|otto| = 4
|s|""<sub>x</sub>""
ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
S = {o, t}
//o und t sind Elemente der Menge S//
s ∈ S
//s ist eine Element der Menge S//
S""<sup>+</sup>""
//beschreibt Wörter über S mit mindestens einem Zeichen//
Beispiele:
s = o
s = t
s = ot
s = to
s = otto
s = t
s = otto
s = ∅
s = s""<sub>0</sub>"" s""<sub>1</sub>"" ... s""<sub>n</sub>"", s""<sub>i</sub>"" ∈ S
s = otto
|s| = 4
|otto| = 4
|s|""<sub>x</sub>""
ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
Deletions:
s = s""<sub>0</sub>"" s""<sub>1</sub>"" ... s""<sub>n</sub>"", s""<sub>i</sub>"" e S
s = otto (Länge von s ist 4)
|s| = |otto| = 4
|s|""<sub>x</sub>"" ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
Additions:
[[MathematikQuantoren Quantoren]]
[[MathematikPraedikate Prädikate]]
[[MathematikMengen Mengen]]
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]]
[[MathematikPraedikate Prädikate]]
[[MathematikMengen Mengen]]
~-[[ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe]]
Additions:
~-[[FormaleSprachen Formale Sprachen]]
Additions:
~-[[NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA)]], (SkriptAtfsEck, S. 19)
Deletions:
Additions:
==a==Zustandsautomaten==a==
~-[[ZustandsAutomaten Zustandsautomaten]] allgemein
~-[[EndlicherAutomat Endliche Zustandsautomaten]]
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEck, S. 15)
~-Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19)
~-[[ZustandsAutomaten Zustandsautomaten]] allgemein
~-[[EndlicherAutomat Endliche Zustandsautomaten]]
~-[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEck, S. 15)
~-Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19)
Deletions:
[[EndlicherAutomat Endliche Zustandsautomaten]]
[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEck, S. 15)
Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19)
Additions:
[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]], (SkriptAtfsEck, S. 15)
Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19)
Siehe auch Notizen und Übungen
Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19)
Siehe auch Notizen und Übungen
Deletions:
Additions:
Schoening2008
Additions:
[[DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA)]]
Additions:
===Zustandsautomaten===
[[EndlicherAutomat Endliche Zustandsautomaten]]
[[EndlicherAutomat Endliche Zustandsautomaten]]
Deletions:
Additions:
CategoryStudiumSE
Additions:
EndlicherAutomat
Deletions:
Formalisierung reaktiver Systeme (diskrete Systeme)
Additions:
===Zeichen und Zeichenmenge===
===Mengen===
===Länge===
===Konkatenation===
===Endlicher Automat===
Formalisierung reaktiver Systeme (diskrete Systeme)
===Mengen===
===Länge===
===Konkatenation===
===Endlicher Automat===
Formalisierung reaktiver Systeme (diskrete Systeme)
Additions:
[[http://de.wikipedia.org/wiki/Konkatenation_(Formale_Sprache)#Konkatenation Konkatenation]]: Verkettung, Hintereinanderschreiben
s = s""<sub>0</sub>"" s""<sub>1</sub>"" s""<sub>2</sub>"" ... s""<sub>n</sub>"" |s| = n + 1
t = t""<sub>0</sub>"" t""<sub>1</sub>"" t""<sub>2</sub>"" ... t""<sub>m</sub>"" |t| = m + 1
Kat(s,t) = st |st| = n+m+2
Wirkung von Epsilon:
Kat(eps, s) = epss = s = seps = Kat(s,eps)
s = s""<sub>0</sub>"" s""<sub>1</sub>"" s""<sub>2</sub>"" ... s""<sub>n</sub>"" |s| = n + 1
t = t""<sub>0</sub>"" t""<sub>1</sub>"" t""<sub>2</sub>"" ... t""<sub>m</sub>"" |t| = m + 1
Kat(s,t) = st |st| = n+m+2
Wirkung von Epsilon:
Kat(eps, s) = epss = s = seps = Kat(s,eps)
Additions:
""|0110101|<sub>1</sub>"" = 4
""|0110101|<sub>0</sub>"" = 3
""|0110101|<sub>2</sub>"" = 0
""|0110101|<sub>0</sub>"" = 3
""|0110101|<sub>2</sub>"" = 0
Deletions:
|0110101|""<sub>0</sub>"" = 3
|0110101|""<sub>2</sub>"" = 0
Additions:
s = s""<sub>0</sub>"" s""<sub>1</sub>"" ... s""<sub>n</sub>"", s""<sub>i</sub>"" e S
s = otto (Länge von s ist 4)
|s| = |otto| = 4
|s|""<sub>x</sub>"" ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
leeres Wort |epsilon| = 0
|0110101|""<sub>1</sub>"" = 4
|0110101|""<sub>0</sub>"" = 3
|0110101|""<sub>2</sub>"" = 0
s = otto (Länge von s ist 4)
|s| = |otto| = 4
|s|""<sub>x</sub>"" ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x
leeres Wort |epsilon| = 0
|0110101|""<sub>1</sub>"" = 4
|0110101|""<sub>0</sub>"" = 3
|0110101|""<sub>2</sub>"" = 0
Additions:
S""<sup>+</sup>"" beschreibt Wörter über S mit mindestens einem Zeichen
Deletions:
Additions:
S""<sub>+</sub>"" beschreibt Wörter über S mit mindestens einem Zeichen
Deletions:
Additions:
==a==Kurze Einführung==a==
Zeichen: Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen: Wörter, Sätze, Satzgefüge
S ist ein Alphabet
S = {a,b,c,x,k,l,...,z}
S"<sub>+</sub>" beschreibt Wörter über S mit mindestens einem Zeichen
S* beschreibt Wörter über S mit mindestens einem Zeichen oder ein leeres Wort (enthält kein Zeichen)
Zeichen: Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen: Wörter, Sätze, Satzgefüge
S ist ein Alphabet
S = {a,b,c,x,k,l,...,z}
S"<sub>+</sub>" beschreibt Wörter über S mit mindestens einem Zeichen
S* beschreibt Wörter über S mit mindestens einem Zeichen oder ein leeres Wort (enthält kein Zeichen)
Deletions:
Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen
Wörter, Sätze, Satzgefüge
Additions:
Zeichen
Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen
Wörter, Sätze, Satzgefüge
in der Theorie: Wörter über Alphabet
Ein Alphabet ist eine vereinbarte Zeichenmenge
Zeichenfolgen
Wörter, Sätze, Satzgefüge
in der Theorie: Wörter über Alphabet