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.
Regex -> reguläre Grammatik
@Ü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.
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: 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]
[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]