Reguläre Sprachen Beweis |
28.04.2007, 16:52 | Auf diesen Beitrag antworten » | ||
Pampelmuse | Reguläre Sprachen Beweis Hallo, hab folgendes Problem , komme nicht weiter bzw. hab keine Idee Beweisen Sie, dass die Klasse der regulären Sprachen unter den Operationen Durschnitt und Komplement abgeschlossen ist. Gibt es noch andere Operationen, unter denen REG abgeschlossen ist? |
||
|
|||
28.04.2007, 19:12 | Auf diesen Beitrag antworten » | ||
Tobias | Welche Sprachen sind denn regulär? |
||
29.04.2007, 10:17 | Auf diesen Beitrag antworten » | ||
Pampelmuse | Hi, rechtslineare und linkslineare Grammatiken => G = {Sum,N, P, S} A->wB oder A->Bw oder C->epsilon wobei A, B und C Nichtterminalsymbole aus N und w ein Terminal aus Sum ist. |
||
29.04.2007, 10:36 | Auf diesen Beitrag antworten » | ||
Tobias | Und was ist mit Automaten? |
||
Anzeige | |||
|
|||
29.04.2007, 10:41 | Auf diesen Beitrag antworten » | ||
Pampelmuse | Muß ein endlicher Automat sein,diese akzeptieren die Typ-3-Sprachen (Reguläre Sprachen) |
||
29.04.2007, 11:25 | Auf diesen Beitrag antworten » | ||
ed209 | Ist klar, was du zeigen mußt? Also was es bedeutet, daß eine Sprache unter dem Durchschnitt (bzw. dem Komplement) abgeschlossen ist. |
||
29.04.2007, 11:40 | Auf diesen Beitrag antworten » | ||
Pampelmuse | Nein, ich denke mir aber das ich es irgendwie mit der Assoziativät Zeigen soll. |
||
29.04.2007, 12:57 | Auf diesen Beitrag antworten » | ||
Tobias | Also ich glaube ich muss konkreter werden: Wenn reguläre Sprachen mit endlichen deterministischen Automaten beschrieben werden können dann könntest du z.B. veruschen, für eine beliebige reguläre Sprachen einen Automat zu konstruieren, der das Komplement beschreibt. Warum wäre das schon ein Beweis für die Abgeschlossenheit unter Komplementbildung? |
||
29.04.2007, 12:58 | Auf diesen Beitrag antworten » | ||
ed209 | Eine Menge M von Mengen sind unter dem Durchschnitt abgeschlossen wenn für jede Menge und gilt . |
||
29.04.2007, 14:59 | Auf diesen Beitrag antworten » | ||
Pampelmuse | OK zunächst mal die Vereinigung:
mit A=(a_1,a_2,...,a_n) regulär und B=(b_1,b_2,...,b_n) regulär => (a_1,a_2,...,a_n) |(b_1,b_2,...,b_n) sind regulär => (a_1,a_2,...,a_n) Schnitt(b_1,b_2,...,b_n) sind regulär => A Schnitt B regulär und element M |
||
29.04.2007, 16:00 | Auf diesen Beitrag antworten » | ||
Tobias | Hä? Was ist denn da was? Was soll (a_1,a_2,...,a_n) sein? Wie kommst du von "|" (das soll wohl oder sein) auf "Schnitt"? |
||
29.04.2007, 20:35 | Auf diesen Beitrag antworten » | ||
Pampelmuse | Danke erstmal. |
|