- Einführung in die Theorie der Berechnung
- 4 INHALT
- Einführung
- 5
- Grundlagen der formalen Sprachtheorie
- 2.1 Überprüfung einiger grundlegender mathematischer Notationen und
- N,Z,Q,R,C.
- {
- }
- 7
- 8 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
- 10 KAPITEL 2. GRUNDLAGEN DER FORMALEN Sprachtheorie
- R+=
- ⋃
- R∗=
- ⋃
- 2.2. ALPHABETE, ZEICHENFOLGEN, SPRACHEN 11
- 2.2. ALPHABETE, ZEICHENFOLGEN, SPRACHEN 13
-
-
-
- 14 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
- 16 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
- 2.2. ALPHABETE, ZEICHENKETTEN, SPRACHEN 17
- 2.3. OPERATIONEN AN SPRACHEN 19
- 20 KAPITEL 2. GRUNDLAGEN DER FORMALEN Sprachtheorie
Einführung in die Theorie der Berechnung
Jean Gallier Abteilung für Computer- und Informationswissenschaftuniversity of PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]
©c Jean Gallier Bitte nicht ohne Genehmigung des Autors nachproduzieren
März 5, 2020
4 INHALT
- 6.4 Das Pumping Lemma
- 6.5 Ein schneller Algorithmus zur Überprüfung der Zustandsäquivalenz
- 7 Kontextfreie Grammatiken und Sprachen
- 7.1 Kontextfreie Grammatiken
- 7.2 Ableitungen und kontextfreie Sprachen
- 7.3 Normalformen für kontextfreie Grammatiken
- 7.4 Reguläre Sprachen sind kontextfrei
- 7.5 Nutzlose Produktionen in kontextfreien Grammatiken
- 7.6 Die Greibach-Normalform
- 7.7 Kleinste Fixpunkte
- 7.8 Kontextfreie Sprachen als kleinste Fixpunkte
- 7.9 Kleinste Fixpunkte und die Greibach-Normalform
- 7.10 Baumdomänen und Gorn-Bäume
- 7.11 Ableitungsbäume
- 7.12 Ogdens Lemma
- 7.13 Pushdown-Automaten
- 7.14 Von kontextfreien Grammatiken zu PDAs
- 7.15 Von PDAs zu kontextfreien Grammatiken
- 7.16 Der Satz von Chomsky-Schutzenberger
- 8 Eine Übersicht über Selbstanalysemethoden
- 8.1 LR(0)- Charakteristische Automaten
- 8.2 Shift / Reduce-Parser
- 8.3 Berechnung von FIRST
- 8.4 Die Intuition hinter dem Shift / Reduce-Algorithmus
- 8.5 Die Graphmethode zur Berechnung von Fixpunkten
- 8.6 Berechnung von FOLLOW
- 8.7 AlgorithmTraverse
- 8.8 Mehr onLR(0) -Charakteristische Automaten
- 8.9 LALR(1) -Lookahead-Sets
- 8.10 ZUERST rechnen, FOLGEN usw. in Anwesenheit vonǫ-Regeln
- 8.11 LR(1)-Charakteristische Automaten
Einführung
Die Theorie der Berechnung befasst sich mit Algorithmen und algorithmischen Systemen: ihredesign und Darstellung, ihre Vollständigkeit und ihre Komplexität.
Der Zweck dieser Notizen ist es, einige der Grundbegriffe der Theorie der Berechnung einzuführen, einschließlich Konzepte aus formalen Sprachen und Automatentheorie, die Theorie der Rechenbarkeit, einige Grundlagen der rekursiven Funktionstheorie und eine Einführung in die Komplexitätstheorie. Andere Themen wie die Korrektheit von Programmen werden hier nicht behandelt (es gibt einfach nicht genug Zeit!).
Die Noten sind in drei Teile gegliedert. Der erste Teil widmet sichformalen Sprachenund Automaten. Der zweite Teil befasst sich mit Berechnungsmodellen, rekursiven Funktionen und Entscheidbarkeit. Der dritte Teil befasst sich mit der Rechenkomplexität, insbesondere den Klassenspandnp.
5
Grundlagen der formalen Sprachtheorie
2.1 Überprüfung einiger grundlegender mathematischer Notationen und
N,Z,Q,R,C.
Thenatural numbers, N={ 0 , 1 , 2 ,…}.
Theintegers, Z={…,− 2 ,− 1 , 0 , 1 , 2 ,…}.
Therationals,
Q=
{
pq
|p, q∈Z, q 6 = 0
}
null
Thereals, R.Diekomplexe Zahlen, C ={a+ib/a,b∈R}.
Bei jeder Mengex, die ganze Mengexist die Menge aller Teilmengen vonxund wird mit 2X bezeichnet.Die Notation f:X→Y
bezeichnet eine funktionmitdomainxuNdbereich(oder codomain)Y.
graph(f) ={(x,f(x)}|x∈X}⊆X×Y
ist thegraphoff.
7
8 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
Im(f) =f(X) ={y∈Y |∃x∈X, y=f(x)}⊆Y
ist theimageoff.
Allgemeiner, ifA⊆X, dann
f(A) ={y∈Y |∃x∈A, y=f(x)}⊆Y
ist das(direkte) Bild vonfa.
Wenn B⊆Y, dann ist f- 1 (B) ={x∈X| f(x)∈B}⊆X
das umgekehrte Bild (oderpullback) von B.
f- 1 (B) ist eine Menge; es könnte leer sein, auch wenn B 6 =∅ .Gegeben zwei Funktionenf: X→Y undg: Y→ Z, die Funktiong◦f:X→Zgegeben durch
(g◦f)(x) =g(f(x)) für allex∈X
ist Diezusammensetzungoffundg.
Die Funktion idX:X→Xgegeben durch
idX(x) =x für allex∈X
ist Dieidentitätsfunktion(ofX).
Eine Funktionf: X→Y istinjektiv (alte Terminologieein-zu-eins)wenn für allex 1 ,x 2 ∈X,
iff(x 1 ) =f(x 2), dann x 1 =x 2 ;
äquivalent wenn x 16 =x 2, dann f(x 1 ) 6 =f(x 2 ).
Tatsache: IfX 6 =∅(und X 6 =∅), eine Funktionf:X →Y ist injektiv, wenn es eine Funktion gibtr:Y →X(aleft inverse) so dass
r◦f= idX .
Hinweis:ris Surjektiv.Eine Funktionf:X→Y issurjektiv (alte Terminologiekonto)wenn zum beispiel∈Y, gibt es einigex∈xsowie y=f(x), ifff(X) =Y.
Tatsache: wennx 6 =∅(undx 6 =∅), eine Funktionf:X→Y ist surjektiv iff es gibt eine functions:Y →X(gerade inverseorsection) so dass
f◦s= idY.
10 KAPITEL 2. GRUNDLAGEN DER FORMALEN Sprachtheorie
EIN relationR⊆X×Xissymmetricif für allx,y∈X, falls (x,y)∈R, dann (y,x)∈R
Ein relationR⊆X×Axis symmetrischen iffR− 1 ⊆R.
GivenR⊆X×X(eine relation onX), defineRnby
R 0 =IXRn+1=R◦Rn.
Thetranstive closureR+ofRis gegeben durch
R+=
⋃
n≥ 1
Rn.
Tatsache.R + ist die kleinste transitive Beziehung, die enthältr.
Dasflexiver und transitiver Schließer∗Vonris gegeben durch
R∗=
⋃
n≥ 0
Rn=R+∪IX.
Tatsache.R∗ist die kleinste transitive und reflexive Beziehung, die enthältr.
Eine relationR⊆X×Xis Anequivalenzrelationwenn es reflexiv, symmetrisch und transitiv ist.
Tatsache. Die kleinste Äquivalenzrelation, die eine Beziehung enthältr⊆X×Xis gegeben durch
(R∪R− 1 )∗.
Eine relationR⊆X×Xisantisymmetricif für allex,y∈X, if (x,y)∈Rand (y,x)∈R,thenx=y.
Eine relationR⊆X×Xis partielle Ordnung, wenn sie reflexiv, transitiv und antisymmetrisch ist.
Eine Teilreihenfolger ⊆X×X ist eine Gesamtreihenfolge, wenn für allex,y ∈X, entweder (x, y)∈ Ror(y, x)∈R.
2.2 Alphabete, Zeichenfolgen, Sprachen
Unsere Ansicht von Sprachen ist, dasseine Sprache ist eine Menge von Zeichenfolgen. Eine Zeichenfolge ist wiederum eine Endlichkeitfolge von Buchstaben aus einem Alphabet. Diese Konzepte werden rigoros wie folgt definiert.
Definition 2.1.Analphabet CASINO ist anyfiniteset.
2.2. ALPHABETE, ZEICHENFOLGEN, SPRACHEN 11
Wir schreiben oft Σ ={a 1 ,…,ak}. Die Buchstaben werden als Symbole des Alphabets bezeichnet.Beispiel:Σ ={a} Σ ={a,b,c}Σ ={ 0, 1 }Σ ={α,β,γ,δ,ǫ, λ, φ, ψ,ω, μ, ν,ρ, σ,η,ξ,ζ}Eine Zeichenfolge ist eine endliche Folge von Symbolen. Technisch ist es praktisch, Strings als zu definierenfunktionen. Für jede ganze Zahl≥1 sei
={ 1 , 2 ,…,n},
und forn= 0, sei =∅.
Definition 2.2. Gegeben ein Alphabet Σ, astring overΣ(oder einfach eine Zeichenfolge) der Länge nisany Funktion
u: →Σ.
Die ganze Zahl ist die Länge des stringu, und es wird als / u / bezeichnet. Wennn = 0, derspezielle Stringu: → Σ der Länge 0wird als bezeichnetleere Zeichenkette oder Nullzeichenkette und wird bezeichnetalsǫ.
Bei einem Stringu: →Σ der Längenn≥1 ist u(i) der i-te Buchstabe im Stringu. Für die Einfachheit der Notation schreiben wir uianstelle vonu(i), und wir bezeichnen den stringu=u(1)u(2)···u(n)als
u=u 1 u 2 ···un,
mit jedemui∈Σ.
Zum Beispiel, wenn Σ ={a,b}undu: →Σ ist so definiert, dassu(1) =a,u(2) =b, undu(3) =a, wir schreibeneu=aba.
Andere Beispiele für Strings sind
Arbeit, Spaß, gabuzomeuh
Strings der Länge 1 sind functionsu: →Σ einfach etwas elementu(1) =aiin Σ auswählen.Wir werden also jedes SymbolaiΣΣ mit der entsprechenden Zeichenfolge der Länge 1 identifizieren.
Die Menge aller Zeichenfolgen über einem Alphabet Σ, einschließlich der leeren Zeichenfolge, wird als Σ∗ bezeichnet.
2.2. ALPHABETE, ZEICHENFOLGEN, SPRACHEN 13
Für die Basis casen= 0, sinceu 0 =ǫ, wir haben
u 0 u=ǫu=u=uǫ=uu 0.
Für den Induktionsschritt haben wir
un+1u= (unu)u durch Definitionun+ = (uun)u durch die Induktionshypothese =u(unu) durch Assoziativität =uun+1 durch Definitionun+1.
Definition 2.4.Gegeben ein Alphabet Σ, gegeben zwei beliebige Zeichenfolgenu,v∈Σ∗wir definieren die folgendennotizen wie folgt:
uist ein Präfix vonviff es gibt einigey∈Σ∗so dass
v=uy.
uist ein Suffix vonviff es gibt einigex∈Σ∗so dass
v=xu.
uist ein Teilstring vonviff es gibt einigex,y∈Σ∗so dass
v=xuy.
Wir sagen dasuist ein richtiges Präfix (Suffix, Teilstring) vonviffuist ein Präfix (Suffix, Teilstring) vonvandu 6 =v.
Zum Beispiel gaist ein Präfix vongabuzo, zoist ein Suffix vongabuzoundbuzist ein Teilstring vongabuzo.Denken Sie daran, dass eine partielle Ordnung ≤ in Mengen eine binäre Beziehung≤⊆ S × S ist, die flexibel, transitiv und antisymmetrisch ist.
Die Konzepte von Präfix, Suffix und Teilzeichenfolge definieren binäre Beziehungen auf Σ∗in der offensichtlichen Weise. Es kann gezeigt werden, dass diese Beziehungen Teilordnungen sind.
Eine weitere wichtige Reihenfolge von Zeichenfolgen ist die lexikografische (oder Wörterbuch-) Reihenfolge.
Definition 2.5. Gegeben ein Alphabet Σ ={a 1 ,…,ak} angenommen, völlig so geordnet, dassata 1 < a 2 <···< ak, gegeben zwei beliebige Stringsu,v∈Σ∗, definieren wir dielexikographische Ordnungwie folgt:
uv
(1) ifv=uy, für somey∈Σ∗, oder(2) ifu=xaiy,v=xajz,ai< aj, witai,aj∈Σ, und für somex,y,z∈Σ∗.
14 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
Die Idee ist, dass wir scannenuundvgleichzeitig von links nach rechts, Vergleich ihmthsymboluminuto ihmth symbolvminv, beginnend mitm= 1. Wenn keine Diskrepanz auftritt, dasist, wenn sie-th symboluminuagreeswith them-th symbolvminvform= 1,…,|u /, dannuist ein Präfix vonvund wir erklären dasuprecedesvin die lexikographische Reihenfolge. Andernfalls für eine weileuandvagree entlang eines gemeinsamen Präfixxx(möglicherweise die leere Zeichenfolge), und dannes gibt aleftmost Diskrepanz, was bedeutet, dassuis der Formu=xaiyundvis derformv=xajz, mitai 6 =aj(undx, y,z∈Σ∗willkürlich). Dann müssen wir die Krawatte brechen, undUm dies zu tun, verwenden wir die Tatsache, dass die Symbolsa 1 < a 2 <···< ak wird angenommen, dass sie (vollständig) geordnet sind, also sehen wir, welche ofaiandajkommt zuerst, sayai< aj, und wir erklären dasu=xaiyprecedesv=xajzin die lexikographische Reihenfolge.
Beachten Sie, dass sich die Fälle (1) und (2) gegenseitig ausschließen. In Fall (1) ist uis ein Präfix vonv. Im Fall(2)v6u. 6 =v.
Zum Beispiel abb, gallhagergallier.
Es ist ziemlich mühsam zu beweisen, dass die lexikographische Ordnung tatsächlich eine apartielle Ordnung ist.In der Tat ist es eine totale Ordnung, was bedeutet, dass für zwei beliebige Stringesu,v∈Σ∗, eitheruv,odervu.
Die Querrichtung einer Stringwird induktiv wie folgt definiert:
ǫR=ǫ,(ua)R=auR,
wherea∈Σ undu∈Σ∗.
Zum Beispiel reillag=gallierR.
Durch settingu=ǫin (ua)R=auR
sinceǫR=ǫanda=ǫa, wir bekommen
aR= (ǫa)R=aǫR=aǫ=a,
namelyaR=adenn alla∈Σ.
Durch Induktion auf|v|kann gezeigt werden, dass
(uv)R=vRuR .
Ein nützlicher Trick, der die umständliche Notation bei der Induktion von Strings reduziertist die Beobachtung, dass anonempty stringw∈Σ∗der Längenn+ 1 (n≥0) kann geschrieben werden als
w=ua, für someu∈Σ∗und some symbola∈Σ, mit|u|=n.
16 KAPITEL 2. GRUNDLAGEN DER FORMALEN SPRACHTHEORIE
wennIst nicht die leere Menge, seitf: X→ Nist eine Injektion, wenn es eine Surjektion gibtr:N→ Xsowie r:f= idX, die Mengexist zählbar, wenn es eine gibturjektionvon nichttox.
Tatsache. Es kann gezeigt werden, dass ein setXis zählbar ist, wenn es entweder endlich ist oder wenn es in bijectionwithN ist (in diesem Fall ist es unendlich).
Das werden wir später sehenn×Nist zählbar. Infolgedessen ist die Menge qvon rationalen Zahlenist zählbar.
Eine Menge isuncountablewenn sie nicht zählbar ist.
Zum Beispiel ist R(die Menge der reellen Zahlen) unzählbar.Ähnlich
(0,1) ={ x∈R/ 0 < x < 1 }
ist unzählbar. Es gibt jedoch eine Bijektion zwischen (0,1) undR (finde einen!)Die Menge 2N aller Teilmengen des Unzählbaren. Dies ist ein Sonderfall des Satzes von Cantor, der unten diskutiert wird.
Angenommen,/Σ|=kmit Σ ={a 1 ,…,ak}. Beobachten Sie zuerst, dass es gibtknstrings der Längenund (kn+1-1) / (k−1) Strings der Längenhöchstensnüber Σ; wennk= 1, die zweite Formelsollte ersetzt werden durchn+ 1. In der Tat, da eine Zeichenfolge eine Funktion istu:{ 1 ,…,n} →Σ, derNummer der Zeichenfolgenist die Anzahl der Funktionen von{ 1 ,…,n} bis Σ, und da Diekardinalität von Σ istk, es gibtknsolche Funktionen (dies wird sofort durch Induktion gezeigt onn). Dann ist die Anzahl der Strings der Länge höchstens
1 +k+k 2 +···+ kn.
Wenn k = 1 ist, ist diese Zahl n+ 1, und wenn k ≥ 2, als Summe einer geometrischen Reihe, ist es(kn+1-1) / (k−1).
Wenn Σ 6 =∅ ist, dann ist die Menge Σ∗aller Strings über Σ unendlich und zählbar, wie wir jetzt zeigen, indem wir eine explizite Bijektion aus Σ constructingontoN konstruieren.
Ifk= 1 writea=a 1 , und dann
{a}∗={ǫ,ein,aa,aaa,…,ein,…}.
Wir haben die Bijektionn7→anfromNto{a}∗.Ifk≥2, dann können wir uns die Zeichenfolge
u=ai 1 ···ain
als Darstellung der ganzen Zahlv(u) in basekverschiebt um (kn−1)/(k−1), mit
2.2. ALPHABETE, ZEICHENKETTEN, SPRACHEN 17
ν(u) =i 1 kn- 1 +i 2 kn− 2 +···+ in- 1 k+in
=
kn- 1 k− 1
- ( i 1 -1)kn− 1 +···+ (in- 1 -1)k +in- 1.
( und mitv(ǫ) = 0), wobei 1≤ij≤kfor j= 1,…,n.
Wir lassen es als eine Übung, um das zu zeigenv: Σ∗→Nist eine Bijektion. Findenexplizit (dasist, eine Formel) für die Umkehrung von ist überraschend schwierig.
Tatsächlichentsprichtν der Aufzählung von Σ∗wobei uprecedesv if/u|< |v|, unduprecedesvin die lexikographische Reihenfolge if|u|=|v/. Es ist leicht zu überprüfen, ob die aboverelation (uprecedesv) eine Gesamtreihenfolge ist.
Zum Beispiel, ifk= 2 und wenn wir schreiben Σ ={a,b}, dann beginnt die Aufzählung mit
ǫ,0a, b,1 , 2 ,aa, ab, ba, bb,3 , 4 , 5 , 6 ,aaa, aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14
Um die nächste Zeile zu erhalten, concatenateaon links und dann concatenatebon links. Wehavev(bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.
Es funktioniert!
Wenn andererseits Σ 6 =∅ ist, ist die Menge 2Σ ∗ aller Teilmengen von Σ∗ (alle Sprachen) nicht zählbar.In der Tat können wir zeigen, dass es keine Surjektion von gibtNonto 2Σ ∗ Zuerst werden wir zeigenes gibt keine Surjektion von Σ∗ auf 2Σ∗. Dies ist ein Sonderfall des Satzes von Cantor.Wir behaupten, wenn es keine Surjektion von Σ∗ auf 2Σ ∗ gibt, dann gibt es auch keine Surjektion vonn auf 2Σ∗.
Beweis. Nehmen wir durch Widerspruch an, dass es eine Surjektion gibtg:N→ 2 Σ ∗ . Aber wenn Σ 6 =∅ ist, dann istσ∗unendlich und zählbar, also haben wir die Bijektionv: Σ∗→N. Dann ist die Zusammensetzung
Σ∗ ν // N
g // 2 Σ ∗
eine Surjektion, weil die Bijektion eine Surjektion ist, gis eine Surjektion, und die Zusammensetzungvon Surjektionen ist eine Surjektion, die der Hypothese widerspricht, dasses keine Surjektion vonσ∗ auf 2Σ ∗ gibt .
2.3. OPERATIONEN AN SPRACHEN 19
2.3 Operationen an Sprachen
Eine Möglichkeit, komplexere Sprachen aus einfacheren zu erstellen, besteht darin, sie mit zu kombinierenverschiedene Operationen. Zuerst überprüfen wir die mengentheoretischen Operationen von Union, intersection undcomplementation.
Gegebenen alphabet Σ, für zwei languagesL 1 ,L 2 über Σ, theunionL 1 ∪L 2 ofL 1andL 2 ist die Sprache,
L 1 ∪L 2 ={w∈Σ∗|w∈L 1 und w∈L 2 }.
TheintersectionL 1 ∩L 2 ofL 1 andL 2 ist die Sprache,
L 1 ∩L 2 ={w∈Σ∗|w∈L 1 und w∈L 2 }.
DiedifferenzeL 1 -L 2 vonL 1 undL 2 ist die Sprache
L 1 −L 2 ={w∈Σ∗|w∈L 1 und w/∈L 2 }.
Die Differenz wird auch als relatives Komplement bezeichnet.
Ein Sonderfall der Differenz wird erhalten, wennL 1 = Σ∗, in diesem Fall definieren wir diecomplementLof eine Sprachelas
L={w∈Σ∗|w /∈L}.
Die obigen Operationen verwenden nicht die Struktur von Strings. Die folgenden Operationen werden verwendetverkettung.
Definition 2.8.Gegeben ein alphabet Σ, für zwei languagesL 1 ,L 2 über Σ, theconcatenationL 1 L 2 ofL 1 andL 2 ist die Sprache,
L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.
Für jede Sprache definieren wir wie folgt:
L 0 ={ǫ},Ln+1=LnL (n≥0).
Durch settingn= 0 inLn+1=LnL, sinceL 0 ={ǫ}, erhalten wir
L 1 =L0+1=L 0 L={ǫ}L=L,
soL 1 =L.
20 KAPITEL 2. GRUNDLAGEN DER FORMALEN Sprachtheorie
Die folgenden Eigenschaften sind leicht verifiziert:
L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L,(L 1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L 1 (L 2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.
Im Allgemeinen ist L 1 L 26 =L 2 L 1.So weit, die Operationen, die wir eingeführt haben, außer Komplementierung (sinceL = Σ∗−Lis unendlich ifLis endlich und Σ ist nicht leer), Bewahren Sie die Endlichkeit der Sprachen. Dies ist bei den nächsten beiden Operationen nicht der Fall.
Definition 2.9.Gegeben ein Alphabet Σ, für jede Sprachelover Σ, dieKleene∗-closureL∗oflist die Sprache
L∗=