Nochmal reguläre Sprachen

[Alexander Schmidt]

Hi,

sorry, mein Verständnis zu regulären Sprachen hat sich noch immer nicht
gebessert.
Sind folgende meiner Gedankengänge Eures erachtens korrekt:

a) Jede endliche Sprache ist regulär.

Würde sagen dass diese Aussage wahr ist.
Begründung: Wir können für jede endliche Sprache einen DFA konstruieren
(auch wenn dieser groß / komplex werden kann) der alle Wörter der Sprache,
also die Sprache, akzeptiert. Dies kann man sich auch so vorstellen, dass
wir für alle endlichen Sprachen einen endlich langen regulären Ausdruck (w1
+ w2 + w3 + ... + wn) konstruieren können der diese Sprache beschreibt (auch
dieser kann u.U. lang werden, aber nur endlich lang).

b) Jede Teilmenge einer regulären Sprache ist regulär.

Würde sagen dass diese Aussage wahr ist.
Begründung: Auch diese Teilsprache muß einen DFA haben der sie erkennt,
ansonsten könnte auch die Originalsprache nicht erkannt werden. Die
Teilsprache wird also im DFA der die Originalsprache an einer bestimmten
Stelle "integriert" sein, d.h. eine Untermenge der Zustände des DFA der die
Originalsprache erkennt kann die Teilsprache erkennen. Wie oben kann man
sich auch vorstellen, dass es einen regulären Ausdruck geben muß der die
Teilsprache erkennt und der Teil des ursprünglichen regulären Ausdrucks war.

c) Sei L eine reguläre Sprache. Dann ist { uv aus E* | u aus L und v nicht
aus L} regulär.

Würde sagen dass diese Aussage falsch ist.
Begründung: u mag Element einer Sprache L sein, die regulär ist. v kann aber
z.B. Element einer Sprache L2 sein die nicht regulär ist. Die Konkatenation
zweier solcher Wörter könnte normalerweise durch einen NFA wie folgt erkannt
werden: Gegeben seien zwei disjunkte Kopien eines NFA (genannt A1 und A2)
die L erkennen. Der Anfangszustand von A1 wird Anfangzustand des neuen
Automaten. Von jedem Zustand in A1 gibt es eine epsilon-Bewegung zum
Anfangszustand von A2. Immer wenn der Wortanfang zu L gehört kann
nichtdeterministiusch entschieden werden, ob in A1 weitergeprüft oder ob
geprüft werden soll ib das Restwort (also v) zu L2 gehört. Leider können wir
zwar eine "Stelle" raten aber wegen der möglichen Irregularität von L2 u.U.
nicht verifizieren ob v aus L2 ist und somit keinen NFA bauen der uns das
Problem löst. Somit muß dies nicht regulär sein.

d) Die Sprache {w aus B* | |w|0 = |w|1 } ist regulär.
Mit |w|x, w aus E*, x aus E* sei die Antahl des Vorkommens des Zeichens
a im Wort w gemeint.

Würde sagen dass diese Aussage wahr ist.
Begründung: DFAs sind in der Lage zu zählen (über Ihre Zustände). So könnte
man einen DFA bauen der bei Vorkommen des Zeichens 0 seinen Zustand wechselt
und beim Vorkommen des Zeichens 1 seinen Zustnd (in die entgegengesetzte
"Richtung") wechselt und bei allen anderen Zeichen im Zustand verbleibt.
Sind wir am Ende wieder im Ausgangszustand können wir akzeptieren da wir in
beide "Richtungen" gleich weit gewandert sind, also geliche oft 0 wie 1
gelesen haben. Folglich ist die Sprache regulär.

Vielen Dank für Eure Meinungen.

MfG

[Felix Fontein]

Hi,

Post by Alexander Schmidt
sorry, mein Verständnis zu regulären Sprachen hat sich noch immer nicht
gebessert.
a) Jede endliche Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.
Begründung: [...]

Das stimmt so.

Post by Alexander Schmidt
b) Jede Teilmenge einer regulären Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.

Wenn sie wahr waere, waere jede Sprache regulaer. (Warum?)

Post by Alexander Schmidt
c) Sei L eine reguläre Sprache. Dann ist { uv aus E* | u aus L und v nicht
aus L} regulär.
Würde sagen dass diese Aussage falsch ist.
Begründung: u mag Element einer Sprache L sein, die regulär ist. v kann
aber z.B. Element einer Sprache L2 sein die nicht regulär ist.

Jedes Wort kann Wort einer Sprache sein, die nicht regulaer ist, und
trotzdem auch Element einer regulaeren Sprache sein. Was du vielleicht
meinst: Die Menge der Woerter, die nicht in L liegt (also das Komplement
von L) ist nicht regulaer.

Bist du dir aber sicher, dass das stimmt? (Oder kennst du sogar ein
Verfahren, wie man aus einem DFA einen DFA konstruiert, der das Komplement
der Sprache des ersten erkennt?)

Post by Alexander Schmidt
Die
Konkatenation zweier solcher Wörter könnte normalerweise durch einen NFA
wie folgt erkannt werden: Gegeben seien zwei disjunkte Kopien eines NFA
(genannt A1 und A2) die L erkennen. Der Anfangszustand von A1 wird
Anfangzustand des neuen Automaten. Von jedem Zustand in A1 gibt es eine
epsilon-Bewegung zum Anfangszustand von A2. Immer wenn der Wortanfang zu L
gehört kann nichtdeterministiusch entschieden werden, ob in A1
weitergeprüft oder ob geprüft werden soll ib das Restwort (also v) zu L2
gehört. Leider können wir zwar eine "Stelle" raten aber wegen der
möglichen Irregularität von L2 u.U. nicht verifizieren ob v aus L2 ist und
somit keinen NFA bauen der uns das Problem löst. Somit muß dies nicht
regulär sein.

Aus jedem NFA kann ein aequivalenter (im dem Sinne, dass er die gleiche
Sprache erkennt) DFA konstruiert werden, also waere die Sprache dann
regulaer.

Denk ueber diesen Aufgabenteil nochmal gut nach.

Post by Alexander Schmidt
d) Die Sprache {w aus B* | |w|0 = |w|1 } ist regulär.
Mit |w|x, w aus E*, x aus E* sei die Antahl des Vorkommens des Zeichens
a im Wort w gemeint.
Würde sagen dass diese Aussage wahr ist.
Begründung: DFAs sind in der Lage zu zählen (über Ihre Zustände). So

Wer hat dir denn das erzaehlt? DFAs koennen zaehlen, aber nur bis zu einer
vorher festgelegten Grenze (die z.B. durch die Anzahl der Zustaende
beschraenkt ist). Womit beliebige Zahlen nicht im DFA gespeichert werden
koennen, was fuer die obige Sprache aber notwendig ist, denn es liegen die
Woerter 0^n1^n fuer alle natuerlichen Zahlen n in ihr.

-felix

[Martin Fuchs]

Post by Alexander Schmidt
a) Jede endliche Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.

ja

Post by Alexander Schmidt
b) Jede Teilmenge einer regulären Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.

Betrachte zum Beispiel die Sprache, die von [0*1*]* erzeugt
wird, diese Sprache ist offenbar regulär.
Eine Teilmenge davon ist L = { 0^n1^n | n \in |N},
die jedoch nicht regulär ist.
Verallgemeinert könnte man sogar zu jeder nichtregulären Sprache eine
reguläre Obermenge angeben (trivial).

Post by Alexander Schmidt
c) Sei L eine reguläre Sprache. Dann ist { uv aus E* | u aus L und v nicht
aus L} regulär.
Würde sagen dass diese Aussage falsch ist.

Hier ist nicht völlig klar, was "v nicht aus L" bedeuten soll, vielleicht
"v aus dem Komplement von L" ?

In diesem Fall:
Netterweise sind die regulären Sprachen nicht nur abgeschlossen unter Konkatenation,
sondern sogar unter Komplementbildung, damit kannst Du die Richtigkeit der Aussage
beantworten.

Post by Alexander Schmidt
d) Die Sprache {w aus B* | |w|0 = |w|1 } ist regulär.
Mit |w|x, w aus E*, x aus E* sei die Antahl des Vorkommens des Zeichens
a im Wort w gemeint.
Würde sagen dass diese Aussage wahr ist.

Diese Sprache ist eines der Standardbeispiele für nicht-reguläre Sprachen,
Beweis über die Myhill-Nerode-Relation.
Man darf sich nicht etwa davon verwirren lassen, dass diese Sprache das
pumping-lemma erfüllt, bekanntermaßen kann man mit dem pl nur zeigen, dass
eine Sprache /nicht/ regulär ist.

Post by Alexander Schmidt
Begründung: DFAs sind in der Lage zu zählen (über Ihre Zustände). So könnte
man einen DFA bauen der bei Vorkommen des Zeichens 0 seinen Zustand wechselt
und beim Vorkommen des Zeichens 1 seinen Zustnd (in die entgegengesetzte
"Richtung") wechselt

Ja, damit kannst Du z.B. die Sprache { (01)^n | n \in |N } erzeugen, aber
nicht die oben gewünschte Sprache.
Die "Zählmöglichkeiten" von DFA's - wenn man überhaupt davon sprechen kann - sind
doch sehr eingegrenzt.


mf

PS: Schreib' nicht soviel "Lyrik", sondern argumentiere mit Definition und Sätzen
oder finde griffige Gegenbeispiele, um zu zeigen, dass Aussagen falsch sind.

[Alexander Schmidt]

Post by Martin Fuchs

Post by Alexander Schmidt
a) Jede endliche Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.

ja

Post by Alexander Schmidt
b) Jede Teilmenge einer regulären Sprache ist regulär.
Würde sagen dass diese Aussage wahr ist.

Betrachte zum Beispiel die Sprache, die von [0*1*]* erzeugt
wird, diese Sprache ist offenbar regulär.
Eine Teilmenge davon ist L = { 0^n1^n | n \in |N},
die jedoch nicht regulär ist.
Verallgemeinert könnte man sogar zu jeder nichtregulären Sprache eine
reguläre Obermenge angeben (trivial).

Post by Alexander Schmidt
c) Sei L eine reguläre Sprache. Dann ist { uv aus E* | u aus L und v nicht
aus L} regulär.
Würde sagen dass diese Aussage falsch ist.

Hier ist nicht völlig klar, was "v nicht aus L" bedeuten soll, vielleicht
"v aus dem Komplement von L" ?
Netterweise sind die regulären Sprachen nicht nur abgeschlossen unter Konkatenation,
sondern sogar unter Komplementbildung, damit kannst Du die Richtigkeit der Aussage
beantworten.

Post by Alexander Schmidt
d) Die Sprache {w aus B* | |w|0 = |w|1 } ist regulär.
Mit |w|x, w aus E*, x aus E* sei die Antahl des Vorkommens des Zeichens
a im Wort w gemeint.
Würde sagen dass diese Aussage wahr ist.

Diese Sprache ist eines der Standardbeispiele für nicht-reguläre Sprachen,
Beweis über die Myhill-Nerode-Relation.
Man darf sich nicht etwa davon verwirren lassen, dass diese Sprache das
pumping-lemma erfüllt, bekanntermaßen kann man mit dem pl nur zeigen, dass
eine Sprache /nicht/ regulär ist.

Post by Alexander Schmidt
Begründung: DFAs sind in der Lage zu zählen (über Ihre Zustände). So könnte
man einen DFA bauen der bei Vorkommen des Zeichens 0 seinen Zustand wechselt
und beim Vorkommen des Zeichens 1 seinen Zustnd (in die entgegengesetzte
"Richtung") wechselt

Ja, damit kannst Du z.B. die Sprache { (01)^n | n \in |N } erzeugen, aber
nicht die oben gewünschte Sprache.
Die "Zählmöglichkeiten" von DFA's - wenn man überhaupt davon sprechen kann - sind
doch sehr eingegrenzt.
mf
PS: Schreib' nicht soviel "Lyrik", sondern argumentiere mit Definition und Sätzen
oder finde griffige Gegenbeispiele, um zu zeigen, dass Aussagen falsch sind.

Hi,

erstmal Danke für Deine Hilfe.

b) und c) leuchten ein.
Bei dem einen Problem hab ich übersehen, dass mit "nicht aus L" das
Komplement gemeint war und der andere Denkfehler ist wohl offensichtlich.
Dein Kommentar aus dem "Post Scriptum" werde (muß) ich mir dringend zu Herze
nehmen ;-)

Zu d):
Mit dem Satz von Nerode habe ich noch immer so meine Probleme.
Kannst Du da kurz was dazu sagen (allgemein) und wie man ihn verwenden kann
um nichtregularität von Sprachen wie in Beispiel d) zu beweisen ?

Vielen lieben Dank.

MfG

[Martin Fuchs]

Post by Alexander Schmidt
Mit dem Satz von Nerode habe ich noch immer so meine Probleme.
Kannst Du da kurz was dazu sagen (allgemein) und wie man ihn verwenden kann
um nichtregularität von Sprachen wie in Beispiel d) zu beweisen ?

Der Satz von Myhill & Nerode sagt aus (zumindest genügt diese
Fassung hier):


Eine Sprache L ist regulär

gdw

Die Nerode-Relation R_L ist von endlichem Index


Dabei ist die Nerode-Relation R_L wie folgt definiert:
(u,v) \in R_L gdw Für alle w \in \Sigma* gilt: uw \in L <=> vw \in L


Du sollst zeigen, dass L={w aus B* | |w|0 = |w|1 } nicht regulär ist.
Nach Satz von Myhill-Nerode genügt es dafür, zu zeigen, dass R_L /nicht/
von endlichem Index ist.
(Der Index einer Relation ist die Anzahl ihrer Äquivalenzklassen)

Schau' Dir zum besseren Verständnis mal ein paar Äqivalenzklassen an:
[01] = [10] = [1001] = L
[010] = [0] = [00011] = ...
[0001] = [110000] = [00] = ...

Betrachte nun z.B. die Äquivalenzklassen [0^k] und [0^n] für
k ungleich n und zeige, dass diese beiden Äquivalenzklassen verschieden sind.

- Was gilt dann allgemein für Äquivalenzklassen der Form [0^k] ?
- Was folgt daraus für den Index von R_L ?


mf

[Duke Luke]

Hallo,

Post by Martin Fuchs
(u,v) \in R_L gdw Für alle w \in \Sigma* gilt: uw \in L <=> vw \in L

[...]´

Post by Martin Fuchs
Eine Sprache L ist regulär
gdw
Die Nerode-Relation R_L ist von endlichem Index

dass das stimmt, kann man sich intuitiv relativ leicht klar machen:
ein endlicher automat, der keine schleifen hat, erkennt offensichtlich
nur eine endliche anzahl von wörtern.
Durch schleifen kann man jetzt stücke von diesen wörtern beliebig oft
vorkommen lassen, wodurch man genügend ausdruckskraft erhält, um alle
regulären sprachen beschreiben zu können. (soweit die vorrede)

die nerode-relation vereinigt nun alle wörter, die zum selben zustand
(in einem minimal-automaten) führen (klar, denn zwei wörter u, v sind
genau dann in der selben klasse, wenn für alle wörter w gilt entweder
uw UND vw sind in der Sprache oder beide nicht - und das kann (bei
endl. automaten) nur bedeuten, dass u und v zum selben zustand führen,
denn hinter dem ende von u bzw. v hängt es ja nur noch von w ab, ob
das wort zur sprache gehört oder nicht, also kann am ende von u und v
nur derselbe zustand erreicht worden sein).

bsp: L = L( a(ba)* )

hier wären die äquivalenzklassen:
1.) [e] = [ab] = [abab] = ... = {e, ab, abab, ...}
2.) [a] = [aba] = [ababa] = ... = {a, aba, ababa, ...}

(daraus resultierender minimal-) Automat:
->(1) -a-> ((2))
<-b-

was bedeutet es aber, wenn die relation endlichen index hat:
das bedeutet, dass der (minimal-) automat für die beschriebene sprache
eine endliche anzahl von zuständen hat (was - intuitiv - ein
notwendiges und hinreichendes kriterium für einen endlichen automaten
ist, denn ein endl. automat kann def-gem. nicht unendlich sein).
Es gibt sogar GENAUSO viele zustände im minimal-automaten, wie
äquivalenzklassen nach myhill-nerode.
Jede äquivalenzklasse entspricht einem zustand, da sie alle wörter
beinhaltet, die zu dem zustand geführt haben können.

das kann aber dennoch heißen, dass es unendlich viele wege (im
endlichen automaten) gibt, die zu einem bestimmten zustand führen, nur
sind diese nach myhill-nerode zu einer klasse zusammengefasst (z.b.
bei der sprache 1*, die einen trivialen minimalautomaten hat, gibt es
nur die klasse [epsilon] = [1] = [11] = ... und dennoch hat die
sprache unendlich viele wörter).

ich hoffe, ich konnte helfen. viel spaß noch mit theorie!

Gruß
Lukas

[Alexander Schmidt]

Hi !

Post by Duke Luke
Hallo,

Post by Martin Fuchs
(u,v) \in R_L gdw Für alle w \in \Sigma* gilt: uw \in L <=> vw \in L

[...]Ž

Post by Martin Fuchs
Eine Sprache L ist regulär
gdw
Die Nerode-Relation R_L ist von endlichem Index

ein endlicher automat, der keine schleifen hat, erkennt offensichtlich
nur eine endliche anzahl von wörtern.
Durch schleifen kann man jetzt stücke von diesen wörtern beliebig oft
vorkommen lassen, wodurch man genügend ausdruckskraft erhält, um alle
regulären sprachen beschreiben zu können. (soweit die vorrede)
die nerode-relation vereinigt nun alle wörter, die zum selben zustand
(in einem minimal-automaten) führen (klar, denn zwei wörter u, v sind
genau dann in der selben klasse, wenn für alle wörter w gilt entweder
uw UND vw sind in der Sprache oder beide nicht - und das kann (bei
endl. automaten) nur bedeuten, dass u und v zum selben zustand führen,
denn hinter dem ende von u bzw. v hängt es ja nur noch von w ab, ob
das wort zur sprache gehört oder nicht, also kann am ende von u und v
nur derselbe zustand erreicht worden sein).
bsp: L = L( a(ba)* )
1.) [e] = [ab] = [abab] = ... = {e, ab, abab, ...}
2.) [a] = [aba] = [ababa] = ... = {a, aba, ababa, ...}
->(1) -a-> ((2))
<-b-
das bedeutet, dass der (minimal-) automat für die beschriebene sprache
eine endliche anzahl von zuständen hat (was - intuitiv - ein
notwendiges und hinreichendes kriterium für einen endlichen automaten
ist, denn ein endl. automat kann def-gem. nicht unendlich sein).
Es gibt sogar GENAUSO viele zustände im minimal-automaten, wie
äquivalenzklassen nach myhill-nerode.
Jede äquivalenzklasse entspricht einem zustand, da sie alle wörter
beinhaltet, die zu dem zustand geführt haben können.
das kann aber dennoch heißen, dass es unendlich viele wege (im
endlichen automaten) gibt, die zu einem bestimmten zustand führen, nur
sind diese nach myhill-nerode zu einer klasse zusammengefasst (z.b.
bei der sprache 1*, die einen trivialen minimalautomaten hat, gibt es
nur die klasse [epsilon] = [1] = [11] = ... und dennoch hat die
sprache unendlich viele wörter).
ich hoffe, ich konnte helfen. viel spaß noch mit theorie!
Gruß
Lukas

Also ich glaube soweit habt Ihr mir das verständlich klar gemacht, nur habe
ich anscheinend nicht verstanden wie man die Äquivalenzklassen findet (bin
ich doof ?).

Martin schrieb:

Schau' Dir zum besseren Verständnis mal ein paar Äqivalenzklassen an:
[01] = [10] = [1001] = L
[010] = [0] = [00011] = ...
[0001] = [110000] = [00] = ...

Wie kommst Du darauf dass das Äquivalenzklassen sind ?
Wie findet man die i.A. ?
Könnt ihr mal 1-2 Beispiele geben ?

Sorry, ich war in der Vorlesungswoche in der das alles behandelt wurde krank
und steh nun total aufm Schlauch wie man merkt.

Noch eine Frage die dazu im Zusammenhang steht:
Wie konstruiert man den Äquivalenzklassenautomat zu einem gegebenen DFA ?
Ist das einfach ein minimalisierter DFA ?

Vielen lieben Dank !!!

MfG

[Martin Fuchs]

Post by Martin Fuchs
[01] = [10] = [1001] = L
[010] = [0] = [00011] = ...
[0001] = [110000] = [00] = ...
Wie kommst Du darauf dass das Äquivalenzklassen sind ?

Ok, wie ich schon schrieb, gilt:
(u,v) \in R_L gdw für alle w \in \Sigma* gilt: uw \in L <=> vw \in L

Dass alle x aus L in der selben Äquivalenzklasse liegen, sollte klar sein.

Nehmen wir jetzt mal die Äquivalenzklasse zu [010]:
010w ist genazu dann in L, wenn die Anzahl der "1" in w um eins
größer ist, als die Anzahl der "0" in w.
Wenn wir ein solches w gegeben haben, dann gilt auch, dass vw in L
liegt, falls die Anzahl der "1" in v um eins kleiner ist, als die Anzahl
der "0" in v.
Es liegen also alle Zeichenketten in der Äquivalenzklasse [010], die
genau aus einer "1" weniger als "0" bestehen.

Post by Martin Fuchs
Wie konstruiert man den Äquivalenzklassenautomat zu einem gegebenen DFA ?
Ist das einfach ein minimalisierter DFA ?

Ja.


mf

[Duke Luke]

Vielleicht hilft dir auch ein Beispiel für eine Nicht-reguläre
Sprache:

L = {0^n 1^n | n € N} ist bekannterweise nicht regulär.

die erste Äquivalenzklasse, die einem wohl einfällt, ist (meist) die,
die Epsilon enthält:
1) [e]
welche Wörter enthält diese klasse noch? es muss für alle wörter w €
"1)" gelten, dass durch dahinterhängen von einem beliebigen wort w'
aus Sigma* entweder ALLE in L liegen oder ALLE nicht in L liegen.
Also können wir schonmal sagen: falls Epsilon.w' in L liegt, dann muss
w' € L gelten (und umgekehrt) - und wichtiger: das muss für alle
Wörter aus der Klasse gelten. Nun ist klar, dass die Klasse keine
weiteren wörter enthalten kann, denn für kein anderes wort könnte dies
gelten (betrachte z.b.
w=00: dann ist ww' [mit w'=11] € L, obwohl w' nicht € L ist.
w=10: dann ist ww' [mit w'=01] NICHT € L, obwohl w' € L ist.)

Mit einer ähnlichen argumentation kriegen wir die weiteren Klassen:
2) [0]
Hier kann man alle wörter der form "1", "011", "00111" dranhängen,
aber keine anderen. Auch diese Klasse enthält nur das eine wort
(warum?)
3) [00] klar (genauso)
...
es sollte schon jetzt klar sein, dass wir unendlich viele
Äquivalenzklassen erhalten - damit wäre schon gezeigt, dass die
sprache nicht regulär ist! es gibt aber noch mehr:

i) [01]: hier gilt [mit w € "i)"] ww' € L <=> w' = epsilon. Für diese
klasse kann man unendlich viele Wörter finden:
[01] = {01, 0011, 000111, 00001111, ...}

i+1) [001]: hier gilt, dass w' = 1 sein müsste - es gibt also wieder
unendlich viele wörter:
[001] = {001, 00011...}
usw.
...
und letzendlich fehlt noch die unendliche klasse der total unförmigen
wörter:
[1] = {1, 1110, 1011011, ...}


Ich muss gestehen, dass mir das beispiel etwas über den kopf gewachsen
ist - ich hoffe, es stimmt trotzdem und konnte helfen!
Prinzipiell ist bei der sache ein wenig intuition gefordert... aber
man kriegts hin!

Gruß

Lukas