Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
 |
|
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 16:52 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Welche Sprachen sind denn regulär?
|
|
|
28.04.2007 19:12 |
|
|
|
Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
|
|
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:17 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Und was ist mit Automaten?
|
|
|
29.04.2007 10:36 |
|
|
|
Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
|
|
Muß ein
endlicher Automat sein,diese akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)
|
|
|
29.04.2007 10:41 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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:25 |
|
|
|
Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
|
|
Nein, ich denke mir aber das ich es irgendwie mit der Assoziativät Zeigen soll.
|
|
|
29.04.2007 11:40 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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:57 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Eine Menge M von Mengen sind unter dem Durchschnitt abgeschlossen wenn für jede Menge ![[latex]A \in M[/latex]](http://www.matheboard.de/latex2png/latex2png.php?A \in M) und ![[latex]B \in M[/latex]](http://www.matheboard.de/latex2png/latex2png.php?B \in M) gilt ![[latex]A \cap B \in M[/latex]](http://www.matheboard.de/latex2png/latex2png.php?A \cap B \in M) .
|
|
|
29.04.2007 12:58 |
|
|
|
Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
|
|
OK zunächst mal die Vereinigung:
| Zitat: |
Original von ed209
Sei und |
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 14:59 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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 16:00 |
|
|
|
Pampelmuse
Mitglied
Dabei seit: 12.04.2007
Beiträge: 32
|
|
|
|
29.04.2007 20:35 |
|
|
|
|
  |
|
