Reguläre Sprachen Beweis

Neue Frage »

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?
 
Auf diesen Beitrag antworten »
Tobias

Welche Sprachen sind denn regulär?
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.
Auf diesen Beitrag antworten »
Tobias

Und was ist mit Automaten?
 
Auf diesen Beitrag antworten »
Pampelmuse

Muß ein
endlicher Automat sein,diese akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)
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.
Auf diesen Beitrag antworten »
Pampelmuse

Nein, ich denke mir aber das ich es irgendwie mit der Assoziativät Zeigen soll.
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?
Auf diesen Beitrag antworten »
ed209

Eine Menge M von Mengen sind unter dem Durchschnitt abgeschlossen wenn für jede Menge [latex]A \in M[/latex] und [latex]B \in M[/latex] gilt [latex]A \cap B \in M[/latex].
Auf diesen Beitrag antworten »
Pampelmuse

OK zunächst mal die Vereinigung:
Zitat:
Original von ed209
Sei [latex]A \in M[/latex] und [latex]B \in M[/latex]

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
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"?
Auf diesen Beitrag antworten »
Pampelmuse

Danke erstmal.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »