reguläre Ausdrücke <-> Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:52 Di 02.05.2006 | | Autor: | dobberph |
| Aufgabe 1 | Zeigen Sie, dass die von einem regulären Ausdruck a definierte Sprache L(a)
eine reguläre Sprache ist. |
| Aufgabe 2 | Zeigen Sie, dass es zu jeder regulären Sprache L einen regulären Ausdruck a
gibt, so dass L = L(a). Ist dieser Ausdruck eindeutig durch L bestimmt? |
Bekannte Definitionen sind:
Formale Sprache L с Σ* heißt regulär, wenn
entweder
L = {},
L = {ε}, oder
L = {x} für xєΣ
( elementare reguläre Sprachen)
oder L1,L2 с Σ* sind regulär und
L = L1 [mm] \cup [/mm] L2,
L = L1 ◦ L2, oder
L = L1*
L läßt sich mit endlich vielen regulären Operationen aus
den elementaren regulären Sprachen ableiten
und
Alphabet Σ mit { ( , ) , [mm] \cup [/mm] , ◦ , * , ε } ∩ Σ = {}
Ein Wort a є Σ* wobei Σ := Σ [mm] \cup [/mm] { ( , ) , [mm] \cup [/mm] , ◦ , * , ε } heißt
regulärer Ausdruck über Σ, wenn
entweder
a = ε
a = ε
a = x für x є Σ
( elementare reguläre Ausdrücke)
oder a1,a2 є Σ* sind reguläre Ausdrücke und
a = (a1 [mm] \cup [/mm] a2)
a = (a1 ◦ a2)
a = (a1*)
Das ist wieder einmal ein Beweis von einer Definition, ich hasse sowas...
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:05 Di 02.05.2006 | | Autor: | dobberph |
Eine Lösung, hoffe sie stimmt, für Aufgabe 1 hab ich selbst gefunden:
Ein regulärer Ausdruck ist eine Formel, die eine (endliche oder unendliche) Sprache beschreibt. Die von einem regulären Ausdruck a erzeugte reguläre Sprache L(a) ergibt sich induktiv über den Aufbau von a:
Definition: Seien x, y reguläre Ausdrücke. Dann ist
L(%) = (leere Sprache)
L(a) = {a} für alle a [mm] \varepsilon [/mm] A
L(x + y) = L(x) L(y) (Vereinigung)
L(xy) = L(x)L(y) (Produkt)
L(x*) = L(x)* (Abschluss)
Das spezielle Symbol % wird gebraucht, damit die leere Sprache durch einen regulären Ausdruck erzeugt werden kann. Die Sprache { [mm] \varepsilon [/mm] } die nur aus dem leeren Wort besteht, wird von dem Ausdruck %* erzeugt.
Stimmt das so?
Aufgabe 2 ist damit aber nicht gelöst, glaube ich... ?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:08 Di 02.05.2006 | | Autor: | dobberph |
Hab der ersten Entsprechend selbst eine Lösung für Aufgabe 2, bitte vielleicht kurz abchecken, ob das so i.O. ist?
Reguläre Ausdrücke über einem Alphabet A sind wie folgt induktiv definiert. Das Zeichen % ist ein spezielles Zeichen, das nicht im Alphabet A vorkommt.
Definition: (Regulärer Ausdruck)
a) % ist ein regulärer Ausdruck;
b) für alle a [mm] \varepsilon [/mm] A ist a ein regulärer Ausdruck;
c) sind x und y reguläre Ausdrücke, so sind auch (x + y), (xy) und x* reguläre Ausdrücke.
|
|
|
| |
|
Hallo und guten Morgen,
also hier solltest Du einen formalen Beweis durch sog. ''Strukturelle Induktion'' führen.
D.h. zB für die Richtung, daß es zu jeder reg. Sprache einen sie erzeugenden reg. Ausdruck gibt:
Zeig dies erst für die ''elementaren'' Sprachen [mm] L=\emptyset, L'=\{\epsilon\}
[/mm]
und [mm] L''=\{a\} [/mm] für [mm] a\in \Sigma [/mm] und nimm dann im Induktionsschritt an, es seien [mm] L_1 [/mm] und [mm] L_2
[/mm]
reg. Sprachen, zu denen es reg. Ausdrücke [mm] R_1, R_2 [/mm] gebe. Dann musst Du zeigen, dass unter dieser
Annahme dann auch reg. Ausdrücke für die Sprachen [mm] L_1\cup L_2, L_1L_2 [/mm] (Konkatenation) und [mm] L_1^{\star} [/mm] gibt.
Gruss,
Mathias
|
|
|
|
