Grundbegriffe der Informatik -...

Grundbegri�e der InformatikKapitel 19: Reguläre Ausdrücke und rechtslineare Grammatiken

Thomas Worsch

KIT, Institut für Theoretische Informatik

Wintersemester 2015/2016

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 1 / 49

Was können endliche Akzeptoren?manche Sprachen mit EA erkennbar

z. B. {a}+{b} ∪ {b}+{a}

manche Sprachen nicht mit EA erkennbarz. B. {akbk | k ∈ N0}

Charakterisierung der erkennbaren Sprachen?i. e. Beschreibung ohne Benutzung endlicher Akzeptoren?

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 2 / 49

Überblick

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 3 / 49

Wo sind wir?

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 4 / 49

Wo sind wir?

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 5 / 49

Der Begri� regulärer Ausdruck hat heute verschiedeneBedeutungen

Beschreibung formaler Sprachen

Ursprung:

Stephen KleeneRepresentation of Events in Nerve Nets and Finite Automatain: Shannon, McCarthy, Ashby (eds.): Automata Studies, 1956

heute: verschiedene Bedeutungenin dieser Vorlesung: die „klassische“ DefinitionVerallgemeinerung: regular expressions

sehr nützlich (emacs, grep, sed, . . . , Java, Python, . . . )

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 6 / 49

Definition regulärer Ausdrücke (1)Alphabet Z = {|, (, ), *, O/} von «Hilfssymbolen»

Alphabet A enthalte kein Zeichen aus Z

regulärer Ausdruck über A ist eine Zeichenfolge über demAlphabet A ∪ Z , die gewissen Vorschri�en genügt.

Menge der regulären Ausdrücke (RA) ist wie folgt festgelegt:O/ ist RAfür jedes x ∈ A ist x RAwenn R1 und R2 RA sind, dann auch (R1|R2) und (R1R2)wenn R ein RA ist, dann auch (R*)Nichts anderes sind reguläre Ausdrücke.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 7 / 49

Beispiele

sei A = {a, b}

Beispiele regulärer Ausdrücke:O/ a b(ab) (O/b) (aO/)((ab)a) (((ab)a)a) ((ab)(aa))(O/|b) (a|b) (a|(ba))((a(a|b))|b) (a|(b|(a|a)))(O/*) (a*) ((a*)*)((ba)(b*)) (((ba)b)*)(((((ab)b)*)*)|(O/*))

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 8 / 49

Klammereinsparungsregeln

„Stern- vor Punktrechnung“

„Punkt- vor Strichrechnung“

Beispiel:R1|R2R3* Kurzform für(R1|(R2(R3*)))

Bei mehreren gleichen binären Operatoren ohne Klammerngilt das als links geklammert

BeispielR1|R2|R3 Kurzform für((R1|R2)|R3)

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 9 / 49

Beispiele für Klammereinsparungsregelnabaa sta� (((ab)a)a)

ab(aa) sta� ((ab)(aa))

a(a|b)|b sta� ((a(a|b))|b)

(abb)**|O/* sta� (((((ab)b)*)*)|(O/*))

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 10 / 49

Nichtbeispielekeine regulären Ausdrücke über {a, b}:

(|b) vor | fehlt ein regulärer Ausdruck|O/| vor und hinter | fehlt je ein regulärer Aus-

druck()ab zwischen ( und ) fehlt ein regulärer Ausdruck((ab) Klammern müssen „gepaart“ au�reten*(ab) vor * fehlt ein regulärer Ausdruckc* c ist nicht Zeichen des Alphabetes

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 11 / 49

Definition der Syntax regulärer Ausdrücke (2)alternative Definition mit Hilfe einerkontextfreien Grammatik

reguläre Ausdrücke:die von der folgenden Grammatik erzeugten Wörter

G = ({R}, {|, (, ), *, O/} ∪A, R, P )

mit P = {R → O/}

∪ {R → x | x ∈ A}

∪ {R → (R|R), R → (RR)}

∪ {R → (R*)}

vergleiche wohlgeformte Klammerausdrücke (Kap. 11)

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 12 / 49

Ableitungsbaum eines regulären Ausdrucks

R

( R

( R

( R

a

* )

R

( R

b

* )

)

* )

(((a*)(b*))*)

oder kürzer(a*b*)*

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 13 / 49

Wo sind wir?

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 14 / 49

Durch R beschriebene formale Sprache 〈R〉〈O/〉 = {}〈x〉 = {x } für jedes x ∈ A〈R1|R2〉 = 〈R1〉 ∪ 〈R2〉

〈R1R2〉 = 〈R1〉 · 〈R2〉

〈R*〉 = 〈R〉∗

Definition folgt der für reguläre Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 15 / 49

Beispiele für 〈R〉R = a|b: Dann ist〈R〉 = 〈a|b〉 = 〈a〉 ∪ 〈b〉 = {a} ∪ {b} = {a,b}

R = (a|b)*: Dann ist〈R〉 = 〈(a|b)*〉 = 〈a|b〉∗ = {a,b}∗

R = (a*b*)*: Dann ist〈R〉 = 〈(a*b*)*〉 = 〈a*b*〉∗

= (〈a*〉〈b*〉)∗ = (〈a〉∗〈b〉∗)∗ = ({a}∗{b}∗)∗

Nachdenken: ({a}∗{b}∗)∗ = {a,b}∗

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 49

Beispiele für 〈R〉R = a|b: Dann ist〈R〉 = 〈a|b〉 = 〈a〉 ∪ 〈b〉 = {a} ∪ {b} = {a,b}

R = (a|b)*: Dann ist〈R〉 = 〈(a|b)*〉 = 〈a|b〉∗ = {a,b}∗

R = (a*b*)*: Dann ist〈R〉 = 〈(a*b*)*〉 = 〈a*b*〉∗

= (〈a*〉〈b*〉)∗ = (〈a〉∗〈b〉∗)∗ = ({a}∗{b}∗)∗

Nachdenken: ({a}∗{b}∗)∗ = {a,b}∗

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 49

Beispiele für 〈R〉R = a|b: Dann ist〈R〉 = 〈a|b〉 = 〈a〉 ∪ 〈b〉 = {a} ∪ {b} = {a,b}

R = (a|b)*: Dann ist〈R〉 = 〈(a|b)*〉 = 〈a|b〉∗ = {a,b}∗

R = (a*b*)*: Dann ist〈R〉 = 〈(a*b*)*〉 = 〈a*b*〉∗

= (〈a*〉〈b*〉)∗ = (〈a〉∗〈b〉∗)∗ = ({a}∗{b}∗)∗

Nachdenken: ({a}∗{b}∗)∗ = {a,b}∗

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 49

Beispiele für 〈R〉R = a|b: Dann ist〈R〉 = 〈a|b〉 = 〈a〉 ∪ 〈b〉 = {a} ∪ {b} = {a,b}

R = (a|b)*: Dann ist〈R〉 = 〈(a|b)*〉 = 〈a|b〉∗ = {a,b}∗

R = (a*b*)*: Dann ist〈R〉 = 〈(a*b*)*〉 = 〈a*b*〉∗

= (〈a*〉〈b*〉)∗ = (〈a〉∗〈b〉∗)∗ = ({a}∗{b}∗)∗

Nachdenken: ({a}∗{b}∗)∗ = {a,b}∗

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R

( R

( R

a

* )

R

( R

b

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R

( R

( R

a {a}

* )

R

( R

b {b}

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R

( R

( R {a}

a {a}

* )

R

( R {b}

b {b}

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R {a}∗{b}∗

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R ({a}∗{b}∗)∗

( R {a}∗{b}∗

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 49

Wie ist das denn eigentlich?Kann man «allgemein» von regulären Ausdrücken R1,R2feststellen, ob 〈R1〉 = 〈R2〉 ist?

Geht das algorithmisch?

Welche formalen Sprachen sind denn durch reguläreAusdrücke beschreibbar?

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 18 / 49

Äquivalenz regulärer AusdrückeEs gibt Algorithmen, um für reguläre Ausdrücken R1,R2festzustellen, ob 〈R1〉 = 〈R2〉 ist

sogar konzeptionell ziemlich einfache

Aber: Dieses Problem ist PSPACE-vollständig.Definition: in einer anderen Vorlesungalle bisher bekannten (!) Algorithmen sindsehr sehr sehr sehr langsam

Man weiß nicht, ob es vielleicht doch Algorithmen mitpolynomieller Laufzeit für das Problem gibt.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 19 / 49

Weitere Beispiele für 〈R〉ab(ab)*〈ab(ab)*〉 = 〈ab〉〈(ab)*〉 = {ab}{ab}∗ = {ab}+

allgemein: R(R)*〈R〉〈(R)*〉 = 〈R〉〈R〉∗ = 〈R〉+

gelegentlich Abkürzung (R)+ bzw. R+

abc|O/*〈abc|O/*〉 = · · · = 〈abc〉 ∪ 〈O/*〉 = 〈abc〉 ∪ 〈O/〉∗

= {abc} ∪ {}∗ = {abc, ε }

allgemein: R|O/*:〈R|O/*〉 = 〈R〉 ∪ 〈O/*〉 = 〈R〉 ∪ {ε }m. a. W.: das Vorkommen eines Wortes aus 〈R〉 ist „optional“verschiedentlich Abkürzungen wie z. B. R? oder . . .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 49

Weitere Beispiele für 〈R〉ab(ab)*〈ab(ab)*〉 = 〈ab〉〈(ab)*〉 = {ab}{ab}∗ = {ab}+

allgemein: R(R)*〈R〉〈(R)*〉 = 〈R〉〈R〉∗ = 〈R〉+

gelegentlich Abkürzung (R)+ bzw. R+

abc|O/*〈abc|O/*〉 = · · · = 〈abc〉 ∪ 〈O/*〉 = 〈abc〉 ∪ 〈O/〉∗

= {abc} ∪ {}∗ = {abc, ε }

allgemein: R|O/*:〈R|O/*〉 = 〈R〉 ∪ 〈O/*〉 = 〈R〉 ∪ {ε }m. a. W.: das Vorkommen eines Wortes aus 〈R〉 ist „optional“verschiedentlich Abkürzungen wie z. B. R? oder . . .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 49

Weitere Beispiele für 〈R〉ab(ab)*〈ab(ab)*〉 = 〈ab〉〈(ab)*〉 = {ab}{ab}∗ = {ab}+

allgemein: R(R)*〈R〉〈(R)*〉 = 〈R〉〈R〉∗ = 〈R〉+

gelegentlich Abkürzung (R)+ bzw. R+

abc|O/*〈abc|O/*〉 = · · · = 〈abc〉 ∪ 〈O/*〉 = 〈abc〉 ∪ 〈O/〉∗

= {abc} ∪ {}∗ = {abc, ε }

allgemein: R|O/*:〈R|O/*〉 = 〈R〉 ∪ 〈O/*〉 = 〈R〉 ∪ {ε }m. a. W.: das Vorkommen eines Wortes aus 〈R〉 ist „optional“verschiedentlich Abkürzungen wie z. B. R? oder . . .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 49

Weitere Beispiele für 〈R〉ab(ab)*〈ab(ab)*〉 = 〈ab〉〈(ab)*〉 = {ab}{ab}∗ = {ab}+

allgemein: R(R)*〈R〉〈(R)*〉 = 〈R〉〈R〉∗ = 〈R〉+

gelegentlich Abkürzung (R)+ bzw. R+

abc|O/*〈abc|O/*〉 = · · · = 〈abc〉 ∪ 〈O/*〉 = 〈abc〉 ∪ 〈O/〉∗

= {abc} ∪ {}∗ = {abc, ε }

allgemein: R|O/*:〈R|O/*〉 = 〈R〉 ∪ 〈O/*〉 = 〈R〉 ∪ {ε }m. a. W.: das Vorkommen eines Wortes aus 〈R〉 ist „optional“verschiedentlich Abkürzungen wie z. B. R? oder . . .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 49

Wo sind wir?

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 21 / 49

RFC 5322: Internet Message Formatsiehe z. B. http://tools.ietf.org/html/rfc5322

legt fest, was wo in einer Email stehen muss, soll, darf oderauch nicht . . .

benutzt dazu etwas namens ABNF„augmented Backus Naur form“seinerseits spezifiziert in RFC 5234für nachfolgendes Beispiel: im wesentlichen reguläreAusdrückeim allgemeinen deutlich mächtiger

Beispiel: Datums- und Zeitangaben in EmailsDate: Wed, 21 Jan 2015 12:08:47 +0100

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 22 / 49

RFC 5322, Abschni� 3.3: Date and Time Specification,fast wörtlich:

date-time = [ day-of-week "," ] date time [CFWS]

day-of-week = ([FWS] day-name)day-name = "Mon" / "Tue" / "Wed" / "Thu" / . . .

date = day month yearday = ([FWS] 1*2DIGIT FWS)month = "Jan" / "Feb" / "Mar" / "Apr" / . . .year = (FWS 4*DIGIT FWS)

time = time-of-day zonetime-of-day = hour ":" minute [ ":" second ]hour = 2DIGITminute = 2DIGITsecond = 2DIGITzone = (FWS ( "+" / "-" ) 4DIGIT)

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 23 / 49

Datums- und Zeitangaben in Emails (2)Beispieltime-of-day = hour ":" minute [ ":" second ]hour = 2DIGIT

in jeder Zeilelinks vom = ein Name für einen regulären Ausdruckrechts vom = etwas wie ein regulärer Ausdruck,der sta� Teilausdrücken deren Namen benutzen kann

an anderer Stelle definiert:DIGIT = 0|1|2|3|4|5|6|7|8|9, also〈 DIGIT 〉 = {0,1,2,3,4,5,6,7,8,9}

2DIGIT ist Abkürzung für DIGIT DIGIT , also z. B.〈 2DIGIT 〉 = {00, 01, 02, . . . , 99}

also z. B. 〈 hour 〉 = {00, 01, 02, . . . , 99}

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 24 / 49

Datums- und Zeitangaben in Emails (3)Beispieltime-of-day = hour ":" minute [ ":" second ]hour = 2DIGITminute = 2DIGITsecond = 2DIGIT

Wörter in Anführungszeichen stehen für sich

eckige Klammern bedeuten, dass ein Teil optional ist

alsotime-of-day = hour : minute | hour : minute : second

Beispiele: 09:50 oder 09:50:17

beachte:9:50 ist nicht syntaktisch korrektaber 39:71 ist syntaktisch korrekt

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 25 / 49

Wo sind wir?

Reguläre AusdrückeDefinitionBeschriebene formale SpracheBeispiel: Datums-/Zeitangaben in EmailsZusammenhang mit Automaten und Grammatiken

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 26 / 49

Charakterisierungen regulärer Sprachen

SatzFür jede formale Sprache L sind äquivalent:1. L kann von einem endlichen Akzeptor erkannt werden.2. L kann durch einen regulären Ausdruck beschrieben werden.3. L kann von einer rechtslinearen Grammatik erzeugt werden.

Solche Sprachen heißen regulär.

Beweis in «Theoretische Grundlagen der Informatik»

rechtslineare Grammatiken kommen gleichsie sind kontextfrei,also ist jede reguläre Sprache eine kontextfreie Spracheaber nicht umgekehrt

Gegenbeispiel: {akbk | k ∈ N0}

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 27 / 49

Zum Beweis des Satzeskonstruktiv:

von endlichem Akzeptor A zu regulärem Ausdruck R mitL(A) = 〈R〉

„mi�el schwer“, z. B. inspiriert vom Algorithmus von Warshall

von regulärem Ausdruck R zu rechtslinearer Grammatik G mit〈R〉 = L(G ):

„relativ leicht“von rechtslinearer Grammatik G zu endlichem Akzeptor A mitL(G ) = L(A):

„am schwierigsten“

beachte: für Rückrichtungen keine Konstruktionen nötig

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 49

Zum Beweis des Satzeskonstruktiv:

von endlichem Akzeptor A zu regulärem Ausdruck R mitL(A) = 〈R〉

„mi�el schwer“, z. B. inspiriert vom Algorithmus von Warshallvon regulärem Ausdruck R zu rechtslinearer Grammatik G mit〈R〉 = L(G ):

„relativ leicht“

von rechtslinearer Grammatik G zu endlichem Akzeptor A mitL(G ) = L(A):

„am schwierigsten“

beachte: für Rückrichtungen keine Konstruktionen nötig

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 49

Zum Beweis des Satzeskonstruktiv:

von endlichem Akzeptor A zu regulärem Ausdruck R mitL(A) = 〈R〉

„mi�el schwer“, z. B. inspiriert vom Algorithmus von Warshallvon regulärem Ausdruck R zu rechtslinearer Grammatik G mit〈R〉 = L(G ):

„relativ leicht“von rechtslinearer Grammatik G zu endlichem Akzeptor A mitL(G ) = L(A):

„am schwierigsten“

beachte: für Rückrichtungen keine Konstruktionen nötig

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 49

Zum Beweis des Satzeskonstruktiv:

von endlichem Akzeptor A zu regulärem Ausdruck R mitL(A) = 〈R〉

„mi�el schwer“, z. B. inspiriert vom Algorithmus von Warshallvon regulärem Ausdruck R zu rechtslinearer Grammatik G mit〈R〉 = L(G ):

„relativ leicht“von rechtslinearer Grammatik G zu endlichem Akzeptor A mitL(G ) = L(A):

„am schwierigsten“

beachte: für Rückrichtungen keine Konstruktionen nötig

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 49

Was ist wichtigDas sollten Sie mitnehmen:

Definition „klassischer“ regulärer Ausdrückeatomare: O/, a ∈ Azusammengesetzte: (R1|R2), (R1R2), (R)*

wissen: reguläre Ausdrücke und die VerallgemeinerungRegular Expressions sind z. B. bei Textverarbeitungsaufgabenmanchmal nützlich

Das sollten Sie üben:zu L ein R mit 〈R〉 = L konstruierenzu R das 〈R〉 bestimmen

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 29 / 49

Wo sind wir?

Reguläre Ausdrücke

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 30 / 49

Motivationkontextfreie Grammatiken erzeugen jedenfalls zum Teilandere formale Sprachen, als man mit endlichen Akzeptorenerkennen kann.

Beispiel:G = ({X }, {a,b},X , {X → aXb | ε }) erzeugt {akbk | k ∈ N0}

und diese Sprache ist nicht regulär.

Kann man kontextfreie Grammatiken so einschränken,dass sie zu endlichen Akzeptoren passen?

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 31 / 49

Rechtslineare Grammatiken: DefinitionEine rechtslineare Grammatik ist eine kontextfreieGrammatik G = (N ,T , S, P ), die der folgendenEinschränkung genügt: Jede Produktion ist

entweder von der Form X → w mit w ∈ T ∗

oder von der Form X → wY mit w ∈ T ∗ und X ,Y ∈ N .

also auf jeder rechten Seitehöchstens ein Nichterminalsymbolund wenn dann nur als letztes Symbol

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 32 / 49

Rechtslineare Grammatiken: BeispieleG = ({X }, {a,b},X , {X → abX | bbaX | ε }

L(G ) = 〈(ab|bba)*〉

G = ({X ,Y }, {a,b},X ,{X → aX | bX | ababbY ,Y → aY | bY | ε }

L(G ) = 〈(a|b)*ababb(a|b)*〉

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 49

Rechtslineare Grammatiken: BeispieleG = ({X }, {a,b},X , {X → abX | bbaX | ε }

L(G ) = 〈(ab|bba)*〉

G = ({X ,Y }, {a,b},X ,{X → aX | bX | ababbY ,Y → aY | bY | ε }

L(G ) = 〈(a|b)*ababb(a|b)*〉

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 49

Rechtslineare Grammatiken: BeispieleG = ({X }, {a,b},X , {X → abX | bbaX | ε }

L(G ) = 〈(ab|bba)*〉

G = ({X ,Y }, {a,b},X ,{X → aX | bX | ababbY ,Y → aY | bY | ε }

L(G ) = 〈(a|b)*ababb(a|b)*〉

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 49

Rechtslineare Grammatiken: BeispieleG = ({X }, {a,b},X , {X → abX | bbaX | ε }

L(G ) = 〈(ab|bba)*〉

G = ({X ,Y }, {a,b},X ,{X → aX | bX | ababbY ,Y → aY | bY | ε }

L(G ) = 〈(a|b)*ababb(a|b)*〉

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 49

Rechtslineare Grammatiken: NichtbeispielG = ({X }, {a,b},X , {X → aXb | ε }) ist nicht rechtslinear,

denn in X → aXb steht das Nich�erminalsymbol X nicht amrechten Ende.

Da die erzeugte formale Sprache {akbk | k ∈ N0} vonkeinem endlichen Akzeptor erkannt wird,kann es auch gar keine rechtslineare Grammatik geben.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 49

SprechweisenRechtslineare Grammatiken heißen auchTyp-3-Grammatiken.

Kontextfreien Grammatiken heißen auchTyp-2-Grammatiken.

Es gibt auch nochTyp-1-Grammatiken undTyp-0-Grammatiken,

die wir hier nicht weiter betrachten werden.

Wenn für ein i ∈ {0, 1, 2, 3} eine formale Sprache L von einerTyp-i-Grammatik erzeugt wird, dann sagt man auch, L seieine Typ-i-Sprache oder kurz vom Typ i .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 49

SprechweisenRechtslineare Grammatiken heißen auchTyp-3-Grammatiken.

Kontextfreien Grammatiken heißen auchTyp-2-Grammatiken.

Es gibt auch nochTyp-1-Grammatiken undTyp-0-Grammatiken,

die wir hier nicht weiter betrachten werden.

Wenn für ein i ∈ {0, 1, 2, 3} eine formale Sprache L von einerTyp-i-Grammatik erzeugt wird, dann sagt man auch, L seieine Typ-i-Sprache oder kurz vom Typ i .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 49

SprechweisenRechtslineare Grammatiken heißen auchTyp-3-Grammatiken.

Kontextfreien Grammatiken heißen auchTyp-2-Grammatiken.

Es gibt auch nochTyp-1-Grammatiken undTyp-0-Grammatiken,

die wir hier nicht weiter betrachten werden.

Wenn für ein i ∈ {0, 1, 2, 3} eine formale Sprache L von einerTyp-i-Grammatik erzeugt wird, dann sagt man auch, L seieine Typ-i-Sprache oder kurz vom Typ i .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 49

SprechweisenRechtslineare Grammatiken heißen auchTyp-3-Grammatiken.

Kontextfreien Grammatiken heißen auchTyp-2-Grammatiken.

Es gibt auch nochTyp-1-Grammatiken undTyp-0-Grammatiken,

die wir hier nicht weiter betrachten werden.

Wenn für ein i ∈ {0, 1, 2, 3} eine formale Sprache L von einerTyp-i-Grammatik erzeugt wird, dann sagt man auch, L seieine Typ-i-Sprache oder kurz vom Typ i .

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 49

Vorteil rechtslinearer GrammatikenWozu rechtslineare Grammatiken?

gegenüber deterministischen endlichen Akzeptoren:manchmal deutlich kürzer und übersichtlicherhinzuschreiben

genaueres Verständnis dafür: im 3. Semester beinichtdeterministischen endliche Akzeptoren

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 49

Vorteil rechtslinearer GrammatikenWozu rechtslineare Grammatiken?

gegenüber deterministischen endlichen Akzeptoren:manchmal deutlich kürzer und übersichtlicherhinzuschreiben

genaueres Verständnis dafür: im 3. Semester beinichtdeterministischen endliche Akzeptoren

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 49

Wo sind wir?

Reguläre Ausdrücke

Rechtslineare Grammatiken (Typ 3)

Kantorowitsch-Bäume und strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 37 / 49

Ziel dieses Abschni�esBeweisskizze für das folgendeLemma.Zu jedem regulären Ausdruck R gibt es eine rechtslineareGrammatik G mit L(G ) = 〈R〉.

Wie beweist man, dass eine Aussage für alle regulärenAusdrücke gilt?

eine Möglichkeit: strukturelle InduktionVariante/Verallgemeinerung vollständiger Induktion,ohne explizit über natürliche Zahlen zu sprechen

darauf arbeiten wir jetzt in mehreren Schri�en hin:Darstellung regulärer Ausdrücke mit Bäumeneine Variante „normaler vollständiger Induktion“strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 38 / 49

Mit Kantorowitsch-Bäumen kann man z. B.reguläre Ausdrücke repräsentieren

.

.

|

b O/

a

*

b

regulärer Ausdruck: ((b|O/)a)(b*)

Darstellung als sogenannterKantorowitsch-Baum

innere Knoten: «Operatoren»Blä�er: «Operanden»

«Regex-Bäume»

Beachte:das ist kein Ableitungsbaumgemäß einer Grammatikaber «genauso gut» und kompakter

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 39 / 49

Regex-Bäume — etwas genauer

O/ a

*

|

Es sei A Alphabet.

Ein Baum ist ein Regex-Baum, wenn gilt:entweder Wurzel ist Bla�, mit x ∈ A oder O/ beschri�et,oder Wurzel mit * beschri�et und hatgenau einen Nachfolger, der Wurzel eines Regex-Baumes istoder Wurzel mit · oder | beschri�et und hatgenau zwei Nachfolger, die Wurzeln zweier Regex-Bäume sind.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 49

Regex-Bäume — etwas genauer

O/ a

*

|

Es sei A Alphabet.

Ein Baum ist ein Regex-Baum, wenn gilt:entweder Wurzel ist Bla�, mit x ∈ A oder O/ beschri�et,oder Wurzel mit * beschri�et und hatgenau einen Nachfolger, der Wurzel eines Regex-Baumes istoder Wurzel mit · oder | beschri�et und hatgenau zwei Nachfolger, die Wurzeln zweier Regex-Bäume sind.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 49

Regex-Bäume — etwas genauer

O/ a

*

|

Es sei A Alphabet.

Ein Baum ist ein Regex-Baum, wenn gilt:entweder Wurzel ist Bla�, mit x ∈ A oder O/ beschri�et,oder Wurzel mit * beschri�et und hatgenau einen Nachfolger, der Wurzel eines Regex-Baumes istoder Wurzel mit · oder | beschri�et und hatgenau zwei Nachfolger, die Wurzeln zweier Regex-Bäume sind.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 49

Regex-Bäume — etwas genauer

O/ a

*

|

Es sei A Alphabet.

Ein Baum ist ein Regex-Baum, wenn gilt:entweder Wurzel ist Bla�, mit x ∈ A oder O/ beschri�et,oder Wurzel mit * beschri�et und hatgenau einen Nachfolger, der Wurzel eines Regex-Baumes istoder Wurzel mit · oder | beschri�et und hatgenau zwei Nachfolger, die Wurzeln zweier Regex-Bäume sind.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 49

Vollständige Induktion über die Baumhöhe

Größere Bäume sind „aus kleineren zusammengesetzt“,und zwar auf eindeutige Weise.

Bijektion Regex-Bäume↔ reguläre Ausdrücke

Höhe h(T ) eines Baumes

h(T ) =

0 falls die Wurzel Bla� ist

1 +maxi h(Ui ) falls die Ui alleUnterbäume von T sind

Beweis einer Aussage für alle regulären Ausdrücke:durch Beweis der Aussage für alle Regex-Bäume

Beweis einer Aussage für alle Regex-Bäume:vollständige Induktion über Höhe der Regex-Bäume

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 41 / 49

Vollständige Induktion über die Baumhöhe

Größere Bäume sind „aus kleineren zusammengesetzt“,und zwar auf eindeutige Weise.

Bijektion Regex-Bäume↔ reguläre Ausdrücke

Höhe h(T ) eines Baumes

h(T ) =

0 falls die Wurzel Bla� ist

1 +maxi h(Ui ) falls die Ui alleUnterbäume von T sind

Beweis einer Aussage für alle regulären Ausdrücke:durch Beweis der Aussage für alle Regex-Bäume

Beweis einer Aussage für alle Regex-Bäume:vollständige Induktion über Höhe der Regex-Bäume

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 41 / 49

Vollständige Induktion über die Baumhöhe — einProblem

naive Vorgehensweise:beim Schri� zu Bäumen der Höhe n + 1Induktionsvoraussetzung nur für Bäume der Höhe n

aber:die Unterbäume eines Baumes der Höhe n + 1 könnenbeliebige Höhen i ≤ n haben.

anschaulich: man darf auch für die kleineren Unterbäumeso etwas wie die Induktionsvoraussetzung benutzen.

präzise: siehe Kapitel 6

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 42 / 49

Erinnerung: Verallgemeinerung vollständiger InduktionEs sei B (n) eine Aussage, die von einer Zahl n ∈ N0 abhängt.

wollen beweisen: ∀n ∈ N0 : B (n)

definiere Aussage A (n) als ∀i ≤ n : B (i ).

beweise durch vollständige Induktion: ∀n ∈ N0 : A (n)

das reicht, denn aus A (n) folgt B (n)

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 43 / 49

Induktion über Höhe der Regex-BäumeAussage B (n):

Für jeden Regex-Baum R der Höhe n gibt es einerechtslineare Grammatik G gibt mit 〈R〉 = L(G ).

Induktionsanfang: zeige B (0):finde T3G, die {x } = 〈x〉 für x ∈ A und {} = 〈O/〉 erzeugen.

Induktionsschri�: n ; n + 1: es sei n ∈ N0 so, dass dieInduktionsvoraussetzung gilt: ∀i ≤ n : B (i ),d. h. für jeden Regex-Baum R′ der Höhe i ≤ ngibt es eine T3G G mit 〈R′〉 = L(G ).

zeige: B (n + 1) giltd. h. für jeden Regex-Baum R der Höhe n + 1existiert T3G G mit 〈R〉 = L(G ).

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 49

Induktion über Höhe der Regex-BäumeAussage B (n):

Für jeden Regex-Baum R der Höhe n gibt es einerechtslineare Grammatik G gibt mit 〈R〉 = L(G ).

Induktionsanfang: zeige B (0):finde T3G, die {x } = 〈x〉 für x ∈ A und {} = 〈O/〉 erzeugen.Induktionsschri�: n ; n + 1: es sei n ∈ N0 so, dass die

Induktionsvoraussetzung gilt: ∀i ≤ n : B (i ),

d. h. für jeden Regex-Baum R′ der Höhe i ≤ ngibt es eine T3G G mit 〈R′〉 = L(G ).

zeige: B (n + 1) giltd. h. für jeden Regex-Baum R der Höhe n + 1existiert T3G G mit 〈R〉 = L(G ).

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 49

Induktion über Höhe der Regex-BäumeAussage B (n):

Für jeden Regex-Baum R der Höhe n gibt es einerechtslineare Grammatik G gibt mit 〈R〉 = L(G ).

Induktionsanfang: zeige B (0):finde T3G, die {x } = 〈x〉 für x ∈ A und {} = 〈O/〉 erzeugen.Induktionsschri�: n ; n + 1: es sei n ∈ N0 so, dass die

Induktionsvoraussetzung gilt: ∀i ≤ n : B (i ),d. h. für jeden Regex-Baum R′ der Höhe i ≤ ngibt es eine T3G G mit 〈R′〉 = L(G ).

zeige: B (n + 1) giltd. h. für jeden Regex-Baum R der Höhe n + 1existiert T3G G mit 〈R〉 = L(G ).

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 49

Induktion über Höhe der Regex-BäumeAussage B (n):

Für jeden Regex-Baum R der Höhe n gibt es einerechtslineare Grammatik G gibt mit 〈R〉 = L(G ).

Induktionsanfang: zeige B (0):finde T3G, die {x } = 〈x〉 für x ∈ A und {} = 〈O/〉 erzeugen.Induktionsschri�: n ; n + 1: es sei n ∈ N0 so, dass die

Induktionsvoraussetzung gilt: ∀i ≤ n : B (i ),d. h. für jeden Regex-Baum R′ der Höhe i ≤ ngibt es eine T3G G mit 〈R′〉 = L(G ).

zeige: B (n + 1) gilt

d. h. für jeden Regex-Baum R der Höhe n + 1existiert T3G G mit 〈R〉 = L(G ).

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 49

Induktion über Höhe der Regex-BäumeAussage B (n):

Für jeden Regex-Baum R der Höhe n gibt es einerechtslineare Grammatik G gibt mit 〈R〉 = L(G ).

Induktionsanfang: zeige B (0):finde T3G, die {x } = 〈x〉 für x ∈ A und {} = 〈O/〉 erzeugen.Induktionsschri�: n ; n + 1: es sei n ∈ N0 so, dass die

Induktionsvoraussetzung gilt: ∀i ≤ n : B (i ),d. h. für jeden Regex-Baum R′ der Höhe i ≤ ngibt es eine T3G G mit 〈R′〉 = L(G ).

zeige: B (n + 1) giltd. h. für jeden Regex-Baum R der Höhe n + 1existiert T3G G mit 〈R〉 = L(G ).

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 49

Skizze des Induktionsschri�s (1)sei R beliebiger Regex-Baum der Höhe n + 1:

*

R′

.

R′1 R′2

|

R′1R′2

Induktionsvoraussetzung: für alle Unterbäume gibt es T3G

Aus T3G für Unterbäume kann man T3G für ganzenRegex-Baum konstruieren.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 45 / 49

Skizze des Induktionsschri�s (1)sei R beliebiger Regex-Baum der Höhe n + 1:

*

R′

.

R′1 R′2

|

R′1R′2

Induktionsvoraussetzung: für alle Unterbäume gibt es T3G

Aus T3G für Unterbäume kann man T3G für ganzenRegex-Baum konstruieren.

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 45 / 49

Skizze des Induktionsschri�s (2)Beispiel: R ist R1|R2

nach Induktionsvoraussetzung gibt es T3GG1 = (N1,A, S1, P1) und G2 = (N2,A, S2, P2) mitL(G1) = 〈R1〉 bzw. L(G2) = 〈R2〉

es sei N1 ∩ N2 = ∅

keine Beschränkung der Allgemeinheitwichtig für die Konstruktion

wähle „neues“ Nich�erminalsymbol S < N1 ∪ N2

Behauptung:G = ({S } ∪ N1 ∪ N2,A, S, {S → S1 | S2} ∪ P1 ∪ P2)

ist T3G mit L(G ) = 〈R1|R2〉

Rechtslinearität: klarL(G ) = L(G1) ∪ L(G2): macht Arbeit, aber nicht hier

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 49

Skizze des Induktionsschri�s (2)Beispiel: R ist R1|R2

nach Induktionsvoraussetzung gibt es T3GG1 = (N1,A, S1, P1) und G2 = (N2,A, S2, P2) mitL(G1) = 〈R1〉 bzw. L(G2) = 〈R2〉

es sei N1 ∩ N2 = ∅

keine Beschränkung der Allgemeinheitwichtig für die Konstruktion

wähle „neues“ Nich�erminalsymbol S < N1 ∪ N2

Behauptung:G = ({S } ∪ N1 ∪ N2,A, S, {S → S1 | S2} ∪ P1 ∪ P2)

ist T3G mit L(G ) = 〈R1|R2〉

Rechtslinearität: klarL(G ) = L(G1) ∪ L(G2): macht Arbeit, aber nicht hier

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 49

Skizze des Induktionsschri�s (2)Beispiel: R ist R1|R2

nach Induktionsvoraussetzung gibt es T3GG1 = (N1,A, S1, P1) und G2 = (N2,A, S2, P2) mitL(G1) = 〈R1〉 bzw. L(G2) = 〈R2〉

es sei N1 ∩ N2 = ∅

keine Beschränkung der Allgemeinheitwichtig für die Konstruktion

wähle „neues“ Nich�erminalsymbol S < N1 ∪ N2

Behauptung:G = ({S } ∪ N1 ∪ N2,A, S, {S → S1 | S2} ∪ P1 ∪ P2)

ist T3G mit L(G ) = 〈R1|R2〉

Rechtslinearität: klarL(G ) = L(G1) ∪ L(G2): macht Arbeit, aber nicht hier

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 49

Skizze des Induktionsschri�s (2)Beispiel: R ist R1|R2

nach Induktionsvoraussetzung gibt es T3GG1 = (N1,A, S1, P1) und G2 = (N2,A, S2, P2) mitL(G1) = 〈R1〉 bzw. L(G2) = 〈R2〉

es sei N1 ∩ N2 = ∅

keine Beschränkung der Allgemeinheitwichtig für die Konstruktion

wähle „neues“ Nich�erminalsymbol S < N1 ∪ N2

Behauptung:G = ({S } ∪ N1 ∪ N2,A, S, {S → S1 | S2} ∪ P1 ∪ P2)

ist T3G mit L(G ) = 〈R1|R2〉

Rechtslinearität: klarL(G ) = L(G1) ∪ L(G2): macht Arbeit, aber nicht hier

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 49

Strukturelle Induktiongegeben «Gebilde» (eben reguläre Ausdrücke), und zwar

kleinste «atomare»/«elementare» Gebildebei RA: O/ und x für x ∈ A

Konstruktionsvorschri�(en), nach denen man aus kleinerenGebilden größere bauen kann

bei RA: R*, R1|R2, R1 · R2

Aufgabe:Zeige, dass alle Gebilde eine gewisse Eigenscha� haben.Strukturelle Induktion:

Induktionsanfang: zeige:alle «atomaren» Gebilde haben die Eigenscha�Induktionsschri�: zeige:«zusammengesetzten» Gebilde haben die Eigenscha�,weil alle Untergebilde die Eigenscha� haben

gleich welche Konstruktionsvorschri� benutzt wurde

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 47 / 49

Strukturelle Induktiongegeben «Gebilde» (eben reguläre Ausdrücke), und zwar

kleinste «atomare»/«elementare» Gebildebei RA: O/ und x für x ∈ A

Konstruktionsvorschri�(en), nach denen man aus kleinerenGebilden größere bauen kann

bei RA: R*, R1|R2, R1 · R2

Aufgabe:Zeige, dass alle Gebilde eine gewisse Eigenscha� haben.Strukturelle Induktion:

Induktionsanfang: zeige:alle «atomaren» Gebilde haben die Eigenscha�

Induktionsschri�: zeige:«zusammengesetzten» Gebilde haben die Eigenscha�,weil alle Untergebilde die Eigenscha� haben

gleich welche Konstruktionsvorschri� benutzt wurde

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 47 / 49

Strukturelle Induktiongegeben «Gebilde» (eben reguläre Ausdrücke), und zwar

kleinste «atomare»/«elementare» Gebildebei RA: O/ und x für x ∈ A

Konstruktionsvorschri�(en), nach denen man aus kleinerenGebilden größere bauen kann

bei RA: R*, R1|R2, R1 · R2

Aufgabe:Zeige, dass alle Gebilde eine gewisse Eigenscha� haben.Strukturelle Induktion:

Induktionsanfang: zeige:alle «atomaren» Gebilde haben die Eigenscha�Induktionsschri�: zeige:«zusammengesetzten» Gebilde haben die Eigenscha�,weil alle Untergebilde die Eigenscha� haben

gleich welche Konstruktionsvorschri� benutzt wurde

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 47 / 49

Was ist wichtigDas sollten Sie mitnehmen:

Definition rechtslineare Grammatiken

Das sollten Sie üben:rechtslineare Grammatiken konstruieren(zu gegebenem Akzeptor, regulären Ausdruck,formaler Sprache)strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 48 / 49

Zusammenfassungreguläre Ausdrücke

werden von diversen «Werkzeugen» unterstütztin manchen Programmiersprachen zur Textverarbeitungpraktisch

rechtslineare Grammatiken

strukturelle Induktion

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 49 / 49