Wort-Ersetzungs-Systeme
Id: rewriting.tex,v 1.1 2003/11/24 13:19:24 joe Exp
Berechnungs-Modell (Markov-Algorithmen)
Regelmenge
Regel-Anwendung: .
Beispiel: Bubble-Sort:
Beispiel: Potenzieren:
Aufgaben: gibt es unendlich lange Rechnungen für: ?
Grammatiken
Id: grammatik.tex,v 1.3 2003/11/24 14:27:00 joe Exp
Grammatik besteht aus:
|
Grammatik { terminale = mkSet "abc" , nichtterminale = mkSet "SA" , startsymbol = 'S' , regeln = mkSet [ ("S", "abc") , ("ab", "aabbA") , ("Ab", "bA") , ("Ac", "cc") ] } |
Eingeschränkte Grammatiken
Id: chomsky.tex,v 1.3 2003/11/24 14:27:00 joe Exp
Für allgemeine Grammatiken ist (Wortproblem) gar nicht entscheidbar.
Regelmenge einschränken
Die Chomsky-Hierarchie
(Wortproblem nicht entscheidbar)
( Wortproblem entscheidbar, jedoch aufwendig)
( Wortproblem in Polynomialzeit)
.
( Wortproblem in Linearzeit)
Theorie der Formalen Sprachen
Id: theorie.tex,v 1.3 2003/11/24 14:27:00 joe Exp
untersucht (Hierarchien von) Sprachfamilien:
Theorie (II)
Jede Typ--Sprache ist eine Typ--Sprache.
: es gibt in Typ- Typ-:
Typ- Typ-.
Typ- Typ-.
Wenn , dann (trivial) und (Aufgabe -- benutze Automaten).
Wenn , dann (trivial -- Aufgabe).
Es gibt mit .
Typ-3-Grammatiken und Reguläre Sprachen
Id: reg.tex,v 1.3 2003/11/24 14:27:00 joe Exp
Def (Wdhlg): heißt regulär existiert regulärer Ausdruck mit .
Satz (Wdhlg): regulär existiert endlicher Automat mit . (Beweis: Analyse/Synthese)
Satz: regulär existiert Typ-3-Grammatik mit . Beweis (trivial):
Sternhöhe
Id: star.tex,v 1.2 2003/11/24 14:27:00 joe Exp
Def: die Sternhöhe eines regulären Ausdrucks ist die maximale Schachteltiefe der Sterne.
Bsp: .
Def: die Sternhöhe einer regulären Sprache ist .
Bsp: , denn
Erweiterte Sternhöhe
Def: in erweiterten regulären Ausdrücken ist als zusätzlicher Operator Komplement bzgl. und Mengendifferenz gestattet.
Def: erweiterte Sternhöhe eines Ausdrucks wie oben als maximale Schachteltiefe, erweiterte Sternhöhe einer Sprache wie oben als kleinste mit .
Bsp: , denn
beachte: wegen Komplement von .
Vermutung: für jede reguläre Sprache gilt .