A presentation at Tech Talk @ Tagesspiegel by Gunnar Bittersmann
What a RegExp!
charset ≠ character set
RegExp ≠ regular expression
RegExp ⊇ regular expression
Reguläre Ausdrücke • 0/ ist ein regulärer Ausdruck. • ε ist ein regulärer Ausdruck. • Für jedes a ∈ Σ ist a ein regulärer Ausdruck. • Wenn α und β reguläre Ausdrücke sind, dann auch αβ, (α|β) und (α)*. • Das sind alle regulären Ausdrücke.
(1) (2) A? = ε | A A+ = A A* (3) (4) (5) (6) (7) A{0} A{n} A{n,} A{,n} A{m,n} = = = = = ε A A{n-1} A{n} A* (A?){n} A{m} A{,n-m} (8) (9) (10) (11) (12) [] [a] [aφ] [^φ] . = = = = = ε a a | [φ] [ψ] [ω] n∈ℕ; n≥1 n∈ℕ n∈ℕ m,n∈ℕ; m≤n
[abc]{2,3} [abc]{2} [abc]{,1} [abc] [abc]{1} [abc]?{1} [abc] [abc] [abc]{0} [abc]? [abc]?{0} [abc] [abc] [abc]? [abc] [abc] (ε | [abc]) (a | [bc]) (a | [bc]) (ε | (a | [bc])) (a | b | [c]) (a | b | [c]) (ε | (a | b | [c])) (a | b | c) (a | b | c) (ε | (a | b | c))
Noam Chomsky Photo: Andrew Rusk, CC BY 2.0
Grammatik G = (V, Σ, P, S) Variablen Symbole (Alphabet) V∩Σ=∅ Sprache Startsymbol S ∈ V Produktionen (Ableitungsregeln) L(G) = { w ∈ Σ* | S ⟹*G w } Wörter
Chomsky-Hierarchie Sprache Automat Ableitungsregeln Beispiel Typ 0: rekursiv aufzählbar Turingmaschine γ→α Typ 1: kontextsensitiv linear platzbeschränkte nichtdeterministische Turingmaschine αAβ → αγβ {aⁿbⁿcⁿ, n > 0} Typ 2: kontextfrei nichtdeterministischer Kellerautomat A→α {aⁿbⁿ, n > 0} Typ 3: regulär endlicher Automat A→a A → aB {aⁿ, n ≥ 0}
science ∩ art = wonder — Brian Suda
Chomsky-Hierarchie alle Sprachen rekursiv aufzählbar kontextsensitiv kontextfrei regulär
Chomsky-Hierarchie Sprache Automat Ableitungsregeln Typ 0: rekursiv aufzählbar Turingmaschine γ→α Typ 1: kontextsensitiv linear platzbeschränkte nichtdeterministische Turingmaschine αAβ → αγβ {aⁿbⁿcⁿ, n > 0} nichtdeterministischer Kellerautomat A→α {aⁿbⁿ, n > 0} endlicher Automat A→a A → aB {aⁿ, n ≥ 0} Typ 2: kontextfrei Typ 3: regulär RegExp regulärer Ausdruck Beispiel
-?\d*()?:()?:()?:()?:[02468][048]|[13579][26])()?: [02468][048]|[13579][26])|()?:[02468][1235679]| [13579][01345789])()?:0[48]|[2468][048]|[13579] [26]))-02-()?:0[1-9]|[12]\d)|()?:()?:[02468] [1235679]|[13579][01345789])00|\d\d()?:[02468] [1235679]|[13579][01345789]))-02-()?:0[1-9]| 1\d|2[0-8]))|\d{4}-()?:()?:0[13578]|1[02])()?:0[1-9]|[12]\d|3[01])|()?:0[469]|11)()?:0[1-9]|[12]\d|30)))
-?\d* # für die Ewigkeit ()?: ()?: ()?: ()?:[02468][048] | [13579][26]) # Jahrhundert durch 4 teilbar ()?:[02468][048] | [13579][26]) # Jahr durch 4 teilbar | ()?:[02468][1235679] | [13579][01345789]) # Jahrhundert nicht durch 4 teilbar ()?:0[48] | [2468][048] | [13579][26]) # Jahr durch 4 teilbar # außer volle Jahrhunderte ) - # Trennzeichen 02 # Februar im Schaltjahr
()?:0[1-9] | [12]\d) # 01 bis 29
| ()?: ()?:[02468][1235679] | [13579][01345789]) # Jahrhundert nicht durch 4 teilbar 00 # selbsterklärend | \d\d # beliebiges Jahrhundert ()?:[02468][1235679] | [13579][01345789]) # Jahr nicht durch 4 teilbar ) )
02 # Februar im Nicht-Schaltjahr
()?:0[1-9] | 1\d | 2[0-8]) # 01 bis 28
| \d{4} # beliebiges Jahr
()?: ()?:0[13578] | 1[02]) # langer Monat
()?:0[1-9] | [12]\d | 3[01]) # 01 bis 31 | ) ) ()?:0[469] | 11) # kurzer Monat
()?:0[1-9] | [12]\d | 30) # 01 bis 30
()?: ()?:0[1-9] | 1[0-9] | 2[0-8]) # 01. bis 28. Tag [./-] # Trennzeichen (‘.’, ‘/’ oder ‘-‘) ()?:0[1-9] | 1[0-2]) # 01. bis 12. Monat | ()?:29 | 30) # 29. bis 30. Tag [./-] # Trennzeichen ()?:0[13-9] | 1[0-2]) # 01. oder 03. bis 12. Monat # (nicht Februar) | 31 # 31. Tag [./-] # Trennzeichen ()?:0[13578] | 1[02]) # 01., 03., 05., 07., 08., 10. # ) oder 12. Monat
[./-] # Trennzeichen [0-9]{4} # Jahr | 29[./-]02[./-] # 29.02. ()?: [0-9]{2} ()?:0[48] | [2468][048] | [13579][26]) # beliebiges Jahrhundert, # durch 4 teilbares Jahr # außer volle Jahrhunderte | ()?:[02468][048] | [13579][26]) 00 ) # durch 4 teilbares Jahrhundert
Some people, when confronted with a problem, think ‘I know, I’ll use regular expressions.’ Now they have two problems. — Jamie Zawinski
Endlicher Automat M = (Z, Σ, δ, z₀, E) Zustände Eingabealphabet Endzustände E ⊆ Z Startzustand z₀ ∈ Z Übergangsfunktion Z × Σ → Z
Endlicher Automat 0, 2, 4, 6, 8 1, 3, 5, 7, 9 zE z0 1, 3, 5, 7, 9 0, 2, 4, 6, 8
Natürliche Zahlen Grammatik regulärer Ausdruck V = {S} [0-9]+ Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S→0 S→1 S→2 S→3 S→4 S→5 S→6 S→7 S→8 S→9 S → 0S S → 1S S → 2S S → 3S S → 4S S → 5S S → 6S S → 7S S → 8S S → 9S endlicher Automat 0, 1, 2, …, 9 z0 zE 0, 1, 2, …, 9
Gerade Zahlen Grammatik regulärer Ausdruck V = {S} [0-9]*[02468] Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S→0 S→2 S→4 S→6 S→8 S → 0S S → 1S S → 2S S → 3S S → 4S S → 5S S → 6S S → 7S S → 8S S → 9S endlicher Automat 0, 2, 4, 6, 8 1, 3, 5, 7, 9 zE z0 1, 3, 5, 7, 9 0, 2, 4, 6, 8
Teilbarkeit durch 5 Grammatik regulärer Ausdruck V = {S} [0-9]*[05] Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S→0 S→5 S → 0S S → 1S S → 2S S → 3S S → 4S S → 5S S → 6S S → 7S S → 8S S → 9S endlicher Automat 0, 5 1, 2, 3, 4, 6, 7, 8, 9 zE z0 1, 2, 3, 4, 6, 7, 8, 9 0, 5
Teilbarkeit durch 10 Grammatik regulärer Ausdruck V = {S} [0-9]*0 Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S→0 S → 0S S → 1S S → 2S S → 3S S → 4S S → 5S S → 6S S → 7S S → 8S S → 9S endlicher Automat 0 1, 2, 3, 4, 5, 6, 7, 8, 9 zE z0 1, 2, 3, 4, 5, 6, 7, 8, 9 0
Teilbarkeit durch 4 Grammatik regulärer Ausdruck V = {S, A} ([0-9][02468])?[048] |[0-9][13579][26] Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S→0 A→2 S→4 A→6 S→8 S → 0S S → 1A S → 2S S → 3A S → 4S S → 5A S → 6S S → 7A S → 8S S → 9A A → 0S A → 1A A → 2S A → 3A A → 4S A → 5A A → 6S A → 7A A → 8S A → 9A
Teilbarkeit durch 4 Rolf B. und dedlfix im SELFHTML-Forum
Zum Reim fehlt eine Zeile hier: Hm, ich hätte jetzt gedacht, der Gedankenschritt von der 2 zur 4 wäre größer als der von der 4 zur 8. — yours truly
Teilbarkeit durch 8
Teilbarkeit durch 3
Teilbarkeit durch 6
Teilbarkeit durch 9
Teilbarkeit durch 9
Teilbarkeit durch 7 Orlok im SELFHTML-Forum
Teilbarkeit durch beliebige Zahl n M = (Z, Σ, δ, z₋₀, E) Z = {z₋₀, z₀, z₁, z₂, …, zn ₋₁} Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} δ(zu , d) = zv mit v = (10u + d) mod n E = {z₀}
römische Zahlen
TIL :lang(…) > q 言語 Language in язык in שפראך ! about in
Gerade Zahlen ohne führende Nullen Matthias Apsel im SELFHTML-Forum
Kommazahlen
Günter Seggebäing, CC BY-SA 3.0
Stephan Brunker, CC BY-SA 3.0
Space: the final frontier. Above us. Around us. Within us. We have always looked to the stars to discover who we are. — Michael Burnham in Star Trek: Discovery S2:E1
Science + art:
The following resources were mentioned during the presentation or are useful additional information.
BI-Wissenschaftsverlag, 1992
Thread im SELFHTML-Forum
SVG mit JavaScript
Tool: Formale Sprachen, abstrakte Automaten, Compiler und Interpreter
The following code examples from the presentation can be tried out live.
Here’s what was said about this presentation on social media.
