Induktion Menge < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wenn L eine reguläre und F eine endliche Menge ist, dann ist F u L eine reguläre Menge. |
Kann mir jemand bei diesem Beispiel weiterhelfen? Ich denke mal eine reguläre Menge ist ja laut Definition eine endlilche Menge, deshalb ist ist F u L auch eine reguläre Menge?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:57 Mi 02.04.2008 | | Autor: | bazzzty |
[Sei F reguläre, L endliche Menge]
> Kann mir jemand bei diesem Beispiel weiterhelfen? Ich
> denke mal eine reguläre Menge ist ja laut Definition eine
> endlilche Menge, deshalb ist ist F u L auch eine reguläre
> Menge?
Zunächst ist eine reguläre Menge im allgemeinen nicht endlich. Woher stammt diese Vermutung? Was für reguläre Mengen kennst Du?
Ansonsten helfe ich Dir gerne weiter, aber um Dich nicht mit neuen Notationen zu verwirren - kannst Du kurz "eure" Definition einer regulären Menge/Sprache beschreiben?
|
|
|
| |
|
Hm aber umgekehrt gilt es schon oder? Jede endliche Menge ist eine reguläre Menge?
Eine reguläre Menge ist beispielsweise die leere Menge {} oder das Leerwort {e} oder auch {aaa, aba, bba}, da {a} und {b} reguläre Mengen sind und ich durch Verkettung und Vereinigung auf {aaa, aba, bba} kommen kann. hm...
|
|
|
| |
|
Mehr kann ich mit dem Begriff reguläre Menge noch nicht anfangen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:33 Mi 02.04.2008 | | Autor: | leduart |
Hallo
Du solltest die DEFINITION für reguläre menge aus eurer Vorlesung angeben.
Gruss leduart
|
|
|
| |
|
DEFINITION: Die Menge [mm] \alpha (\summe) [/mm] der regulären Sprachen über [mm] \summe [/mm] ist die kleinste Menge, für die gilt:
a) {},{e} [mm] \in \alpha(\summe)
[/mm]
b) Wenn A,B [mm] \in \alpha(\summe), [/mm] dann gilt auch A u B, A.B,A* [mm] $\in \alpha(\summe)$, [/mm] d.h., [mm] \alpha(\summe) [/mm] ist abgeschlossen gegenüber Vereinigung, Verkettung und Kleene-Stern.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:03 Do 03.04.2008 | | Autor: | bazzzty |
> Mehr kann ich mit dem Begriff reguläre Menge noch nicht
> anfangen...
Okay, ich versuche mal zu helfen, bin aber nicht ganz sicher, daß wir die gleichen Begrifflichkeiten haben.
Was Du angegeben hast (in dem anderen Beitrag), ist die Definition der Menge der regulären Sprachen (aka regulären Mengen) über einem Alphabet Sigma. Ich nehme an, daß die unvollständig ist, denn zu einem gegebenen Alphabet sollte als Basisfall nicht nur die leere Menge und die Sprache, die nur das leere Wort enthält, in der Menge der regulären Sprachen sein, sondern auch jede Sprache, die nur endlich viele Wörter über [mm]\Sigma [/mm] enthält.
Die Definition, "wie ich sie kenne", kann man in
http://www.ling.uni-potsdam.de/kurse/EndlicheTechniken/Sprachen.pdf
nachlesen.
Du siehst hoffentlich, daß Deine Aufgabe mit so einer Definition ein Kinderspiel ist. Vielleicht verstehst Du jetzt auch, warum es so wichtig ist, mit anzugeben, was man zur Verfügung hat, wenn man eine Frage stellt.
Interessant wäre aber: Woher kommt Deine Definition? Falsch abgeschrieben?
Daß sie unvollständig ist, kann man leicht daran sehen, daß nach Deiner Definition der zweite Teil der Definition völlig sinnlos ist. Wenn nach 1) nur die leere Menge und die Menge, die das leere Wort enthält, in der Menge der regulären Sprachen ist, kommen durch den Abschluß über 2) ja keine weiteren Buchstaben ins Spiel.
Zweitens versuche ich kurz, Dir die Begriffe auseinanderzubringen, so gut ich kann: Eine Reguläre Menge (im wesentlichen synonym: Reguläre Sprache) ist eine Menge von Wörtern über einem Alphabet, die sich mit einem einfachen Regelsystem beschreiben läßt. Eine Variante, solche Regeln zu notieren, sind reguläre Ausdrücke (eine andere Chomsky-3-Grammatiken). Jeder Reguläre Ausdruck beschreibt eine Reguläre Sprache/Menge und jede Reguläre Menge läßt sich durch einen Regulären Ausdruck beschreiben.
Die Menge [mm]\{0,1,10,11,100,101...\}[/mm] der Binärzahlen ist eine reguläre Menge/Sprache, der zugehörige Reguläre Ausdruck ist [mm](0|(1(0|1)^\star)[/mm].
Man braucht diese Beschreibung allerdings nicht. Man kann reguläre Mengen/Sprachen äquivalent auch durch die Definition aus dem Link beschreiben: Jede endliche Sprache ist regulär (Weil durch endlich viele Regeln beschreibbar), und reguläre Sprachen lassen sich durch die gegebenen Operationen (Alternative, Konkatenation und Kleene-Stern) zu neuen Regulären Sprachen verbinden.
|
|
|
|
