Grundbegriffe der Informatik - gbi.ira.uka.degbi.ira.uka.de/vorlesungen/k-19-reg-ausdruecke-folien.pdf · GBI — Grundbegri˙e der InformatikKIT, Institut für Theoretische Informatik19/49

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?


Ü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


Wo sind wir?





Wo sind wir?





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, . . . )


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.


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/*))


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)


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/*))


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


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)


Ableitungsbaum eines regulären Ausdrucks

R

( R

( R

( R

a

* )

R

( R

b

* )

)

* )

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

oder kürzer(a*b*)*


Wo sind wir?





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


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}∗





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






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






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



Bestimmung von 〈R〉 entlang des Ableitungsbaums von R

R

( R

( R

( R

a

* )

R

( R

b

* )

)

* )

analog zur Auswertungarithmetischer Ausdrücke



R

( R

( R

( R

a {a}

* )

R

( R

b {b}

* )

)

* )




R

( R

( R

( R {a}

a {a}

* )

R

( R {b}

b {b}

* )

)

* )




R

( R

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )




R

( R {a}∗{b}∗

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )




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

( R {a}∗{b}∗

( R {a}∗

( R {a}

a {a}

* )

R {b}∗

( R {b}

b {b}

* )

)

* )



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?


Ä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.


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 . . .






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







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







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



Wo sind wir?





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


http://tools.ietf.org/html/rfc5322

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)


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}


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


Wo sind wir?





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}


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




„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):


















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


Wo sind wir?

Reguläre Ausdrücke




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?


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


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)*〉



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





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





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




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.


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 .




















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


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


Wo sind wir?

Reguläre Ausdrücke




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


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


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.



O/ a

*

|

Es sei A Alphabet.




O/ a

*

|

Es sei A Alphabet.




O/ a

*

|

Es sei A Alphabet.



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


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


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


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)


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 ).




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 ).






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 ).








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.


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.


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




es sei N1 ∩ N2 = ∅









es sei N1 ∩ N2 = ∅









es sei N1 ∩ N2 = ∅







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





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


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

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






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


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



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


Zusammenfassungreguläre Ausdrücke

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

rechtslineare Grammatiken

strukturelle Induktion


Documents

Grundbegriffe der Informatik - gbi.ira.uka.degbi.ira.uka.de/vorlesungen/k-19-reg-ausdruecke-folien.pdf · GBI — Grundbegri˙e der InformatikKIT, Institut für Theoretische Informatik19/49