Sehr geehrte Forummitglieder und post-Aktivisten/Innen,

Wir (eine kleine Gruppe 2.Sem.) haben uns heute gefragt, ob "Regulär" (in Zusammenhang mit) "Sprache" das gleiche wie "Rational" beschreibt und ob dies auch für alle anderen Bereiche (Grammatik, ect..) gilt.

Wir wären euch sehr dankbar, wenn ihr/einer von euch/Du uns das(gerne auch mit Bezug auf Definitionen) einleuchtend und klar erklären könntet/st/st.

Danke im Vorraus !

Es gibt ja verschiedene Sprachklassen, die von Chomsky in eine Hierarchie verpackt wurden.

Es gilt Reg (echte Teilmenge) Cf (echte Teilmenge) Cs …

Dabei ist Reg die Menge der Sprachen, die von einem DFA akzeptiert wird.

Cf ist die Menge der Kontextfreien Sprachen, die von einem Kellerautomaten akzeptiert wird. Reg ist echte Teilmenge von Cf, was z.B. mit a^n b^n gezeigt wird mit n aus N (nat. Zahlen).

Dann kommt die Menge der Kontextsensitiven Sprachen, die sich dadurch auszeichnen, dass sie monoten sind, also bei der Anwendung der Produktionen (einer Grammatik) das bearbeitete Wort immer länger wird. Es ist Cf echte Teilmenge von Cs, was z.B. mit a^n b^n c^n gezeigt werden kann. Cs wird vom LBA (linear beschränkten Automaten [ich glaube das war eine Turing-Maschine, die ein Arbeitsband hat, welches nur auf einer Seite unendliche war]).

Zu jeder regulären Menge kann man einen rationalen Ausdruck angeben, das habe ich so bei Jantzen letztes Jahr gelernt.
Die Frage ist jetzt, ob diese Mengen äauivalent sind, also Reg=Rat, wobei hier mal Rat die Menge aller rationalen Ausdrücke sei.

Reg (Teilmenge von) Rat sollte klar sein. Die Frage ist nur ob es eine ECHTE Teilmenge ist, der ob die Mengene sogar gleich sind.

Ich habe da jetzt leider spontan keine Idee.

Für die Gleichheit wäre zu zeigen, dass zu jedem beliebigen rationalen Ausdruck immer ein passender DFA angegeben werden kann.

Für die echte Teilmenge müsste nur ein Gegenbeispiel angegeben werden.

Im F2-Skript wird in Theorem 3.34 (Satz von Kleene) gezeigt, dass Reg=Rat gilt. Aber ich bin mir nicht ganz sicher, ob das der Anonyme überhaupt meinte. Meinst du "rational" im Sinne von "rationaler Ausdruck" oder in einem anderen Sinne?

Ich vermute, dass diese Frage mit Übungsaufgabe 11.1.1 zutun hat.
Dazu lässt sich sagen, dass zwar die von rationalen Ausdrücken
beschriebenen Sprachen genau die regulären sind, aber die Sprache
der rationalen Ausdrücke selbst nicht regulär ist, wie man
leicht sieht.

Sehr geehrte Forummitglieder und post-Aktivisten/Innen,

Wir (eine kleine Gruppe 2.Sem.) haben uns heute gefragt, ob "Regulär" (in Zusammenhang mit) "Sprache" das gleiche wie "Rational" beschreibt und ob dies auch für alle anderen Bereiche (Grammatik, ect..) gilt.

Wir wären euch sehr dankbar, wenn ihr/einer von euch/Du uns das(gerne auch mit Bezug auf Definitionen) einleuchtend und klar erklären könntet/st/st.

Danke im Vorraus !

Nun ja, einfach erklären ist nicht immer leicht:

Reguläre Teilmengen von X^*, X ein Alphabet, sind die, die von endlichen Automaten akzeptiert werden. (so die Definition im F2 Skript!)
Als Theorem gibt es dazu:
[img]http://mokrates.de/cgi-bin/texstring?%24L%5Csubseteq%20X%5E*%24[/img] ist regulär genau dann, wenn es ein endliches Monoid M gibt und eine Abbildung [img]http://mokrates.de/cgi-bin/texstring?%24f%20%5C%2C%20%3A%5C%2C%20X%5E*%5Cto%20M%24[/img] und eine Teilmenge [img]http://mokrates.de/cgi-bin/texstring?%24R%5Csubseteq%20M%24[/img] mit [img]http://mokrates.de/cgi-bin/texstring?%24L%20%3D%20f%5E%7B-1%7D(R)%24[/img].
Die Definition von regulären Mengen über endl. Automaten gilt nur für Teilmengen endlich erzeugter freier Monoide (wie z.B. X^*)

Hier sind rationale Mengen solche, für die es eine Darstellung mit einem endlichen Ausdruck gibt (wie in F2 erklärt)

Um in allgemeinen Monoiden diese Mengen eventuell unterscheiden zu können, definierte Eilenberg 1967
die rationalen Teilmengen und die erkennbaren Teilmengen (recognizable subsets) eines Monoides.
Dabei wird der oben zitierte Satz zur Definitiion von erkennbaren Mengen, und Rec(M) ist die Menge aller erkennbaren Teilmengen von M.
Rationale Teilmengen eines Monoides M werden wie im F2-Skript definiert, nur eben statt X^* muss nun immer M (das Monoid) stehen und einzelne Elemente aus X sind dann Elemente aus M.
Mit Rat(M) ist dann die Menge aller rationalen Teilmengen von M bezeichnet.

Mit diesen Definitionen folgt, dass in jedem endlich erzeugten Monoid M gilt:
[img]http://mokrates.de/cgi-bin/texstring?%24%5Cmathit%7BRec%7D(M)%5Csubseteq%20%5Cmathit%7BRat%7D(M)%24[/img]
Diese Inkusion gilt nicht mehr, wenn M nicht endlich erzeugt ist!
Das macht also den Unterschied!
z.B. gibt es rationale Mengen eines Monoides, deren Durchschnitt nicht mehr rational ist!!

Mehr dazu in Berstel (s.u.), aber für F2 und das berufsqualifizierende Informatikstudium ist das nur für solche Studierenden wichtig, die später mal in einer Hochschule zur theoretischen Informatik oder Mathematik arbeiten möchten.
Ich hoffe das stillt den Wissensdurst für's erste?


(J. Berstel: Transductions and Context-free languages, Teubner 1979)

[img]http://mokrates.de/cgi-bin/texstring?%24L%5Csubseteq%20X%5E*%24[/img] ist regulär genau dann, wenn es ein endliches Monoid M gibt und eine Abbildung [img]http://mokrates.de/cgi-bin/texstring?%24f%20%5C%2C%20%3A%5C%2C%20X%5E*%5Cto%20M%24[/img] und eine Teilmenge [img]http://mokrates.de/cgi-bin/texstring?%24R%5Csubseteq%20M%24[/img] mit [img]http://mokrates.de/cgi-bin/texstring?%24L%20%3D%20f%5E%7B-1%7D(R)%24[/img].

Wahrscheinlich irre ich mich, aber gilt das nicht für jede Sprache
[img]http://mokrates.de/cgi-bin/texstring?%24L%5Csubseteq%20X%5E*%24[/img], wenn man für f die charakteristische Funktion und auf {0,1}
etwa die Gruppenstruktur wählt? Wenn man zusätzlich sagt, dass
[img]http://mokrates.de/cgi-bin/texstring?f(x)%3Df(y)%5CRightarrow%20f(xz)%3Df(yz)[/img] für [img]http://mokrates.de/cgi-bin/texstring?x%2Cy%2Cz%5Cin%20X%5E*[/img] gilt, dann müsste es
stimmen, denn dann ist es ja eine Umformulierung des Satzes von
Nerode. Oder denke ich da falsch?

[img]http://mokrates.de/cgi-bin/texstring?%24L%5Csubseteq%20X%5E*%24[/img] ist regulär genau dann, wenn es ein endliches Monoid M gibt und eine Abbildung [img]http://mokrates.de/cgi-bin/texstring?%24f%20%5C%2C%20%3A%5C%2C%20X%5E*%5Cto%20M%24[/img] und eine Teilmenge [img]http://mokrates.de/cgi-bin/texstring?%24R%5Csubseteq%20M%24[/img] mit [img]http://mokrates.de/cgi-bin/texstring?%24L%20%3D%20f%5E%7B-1%7D(R)%24[/img].

Wahrscheinlich irre ich mich, aber gilt das nicht für jede Sprache
[img]http://mokrates.de/cgi-bin/texstring?%24L%5Csubseteq%20X%5E*%24[/img], wenn man für f die charakteristische Funktion und auf {0,1}
etwa die Gruppenstruktur wählt? Wenn man zusätzlich sagt, dass
[img]http://mokrates.de/cgi-bin/texstring?f(x)%3Df(y)%5CRightarrow%20f(xz)%3Df(yz)[/img] für [img]http://mokrates.de/cgi-bin/texstring?x%2Cy%2Cz%5Cin%20X%5E*[/img] gilt, dann müsste es
stimmen, denn dann ist es ja eine Umformulierung des Satzes von
Nerode. Oder denke ich da falsch?

(Nerode sagte etwas zur Endlichkeit des Indexes der von L induzierten Rechtskongruenz!)

Gute Idee, geht aber nicht, weil im Berstel zwar ' f ' nur als 'morphism' tituliert wird, aber irgendwo gaaaanz weit vorne gesagt wurde, dass das wohl (in unserer Notation) ein Homomorphismus sein muss. (Die charakteristische Funktion ist i.d.Regel KEIN Homomorphismus!)
Sorry, auch für mich gilt: erst lesen, korrekt übersetzen und dann schreiben …
sorry dafür.

(Nerode sagte etwas zur Endlichkeit des Indexes der von L induzierten Rechtskongruenz!)

Ich meinte die Formulierung im F2-Skript. Dort heißt es ja auch:
L ist regulär genau dann, wenn es Vereinigung endlich vieler
Klassen einer rechtsinvarianten Äquivalenzrelation mit endlichem
Index ist. Und aus einer solchen Relation bekommt man ja eine
Funktion, die jedem Wort seine Äquivalenzklasse zuordnet und die
dann die obige Eigenschaft (f(x)=f(y) => f(xz)=f(yz)) hat. Und
umgekehrt die Relation aus einer Funktion mit dieser Eigenschaft
(zwei Worte stehen in Relation, wenn sie das gleiche Bild haben).

… weil im Berstel zwar ' f ' nur als 'morphism' tituliert wird, aber irgendwo gaaaanz weit vorne gesagt wurde, dass das wohl (in unserer Notation) ein Homomorphismus sein muss.

Ah, das hatte ich vermutet. Sonst wäre ja auch die Struktur auf M
garnicht in die Aussage eingegangen. [img]http://www.fb18.de/gfx/25.gif[/img]