Regex -> reguläre Grammatik

Alles, was nicht direkt mit Python-Problemen zu tun hat. Dies ist auch der perfekte Platz für Jobangebote.
Antworten
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Hallo mal wieder,
alle sagen immer, dass reguläre Ausdrücke äquivalent zu regulären Grammatiken sind. Aber wie würden zB die Ersetzungsregeln der von [ab]*@c* aussehen?
Meine Idee dafür wäre
S -> A@C
C -> leeres Wort
C -> cC
A -> leeres Wort
A -> aA
A-> bA
aber das wäre doch nicht regulär, weil bei der ersten Regel zwei Nichtterminalsymbole auf der rechten Seite stehen, oder?
Grüße, euer y.
BlackJack

@Üpsilon: Wäre das was passendes?

S → aS
S → bS
S → @A
A → ε
A → cA

Edit: Man beweist so eine Äquivalenz ja dadurch das man Induktiv zeigt das/wie die einzelnen Teile von regulären Ausdrücken in reguläre Grammatiken umsetzt. Anhand dessen lässt sich sicher ein Programm schreiben das Dir reguläre Ausdrücke in reguläre Grammatiken übersetzt. :-)
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Okay dankeschön :D Der Fehler den ich gemacht habe war, den Regex sozusagen in "Sinnabschnitte" zu zerlegen, aber man muss offenbar streng von links nach rechts denken.
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: Man kann schon irgendwo anfangen, man muss die Teilgrammatiken dann nur richtig zusammenfügen. Das fällt mit Zustandsautomaten vielleicht leichter. Denn an so einem kann man die Grammatik ziemlich leicht fast 1:1 ablesen:
[codebox=text file=Unbenannt.txt] a c
┌───┐ ┌───┐
∨ │ ∨ │
┌───────┐ @ ╔═══════╗
│ S │ ───> ║ A ║
└───────┘ ╚═══════╝
∧ b │
└───┘
[/code]
Vielleicht noch ein wenig einfacher wenn man sich für das Ende des regulären Ausdrucks ein eigenes, zusätzliches Zeichen definiert und damit einen eigenen Zustand bekommt:
[codebox=text file=Unbenannt.txt] a c
┌───┐ ┌───┐
∨ │ ∨ │
┌───────┐ @ ┌───────┐ ε ╔═══╗
│ S │ ───> │ A │ ───> ║ $ ║
└───────┘ └───────┘ ╚═══╝
∧ b │
└───┘
[/code]
Antworten