reguläre Sprache von Sigma*

Modius
Erstie
Erstie
Beiträge: 19
Registriert: 9. Okt 2009 12:15

reguläre Sprache von Sigma*

Beitrag von Modius »

Moin,

bin gerade beim Klausur durchrechnen und frag mich ob das regulärer Ausdrücke über der Sprache Sigma* sind:

i (a+b+c)(a*b*c*)+0*
ii (a+bca)+((c + 0*)(0*b)(aa)*)*
iii (a+bc)*+(a+cb)*+(a+bb)*+(a+cc)*

Hat da jemand ne Lösung und kann mir erklären warum das so ist?

LG
Die Wissenschaft nötigt uns, den Glauben an einfache Kausalitäten aufzugeben.
(Nitzsche)

kartzow
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 8. Apr 2010 14:12

Re: reguläre Sprache von Sigma*

Beitrag von kartzow »

Hallo,

du muesstest erstmal genau erklaeren, was du meinst. Zunaechst bildet man regulaere Ausdruecke ueber Alphabeten, also z.B. ueber \(\Sigma\)
und nicht ueber Sprachen wie \(\Sigma^*\) (man will ja gerade Sprachen damit beschreiben!).

Zweitens, was meinst du mit 0? die leere Menge \(\emptyset\)? oder einen Buchstaben 0\(\in\Sigma\)?

Wenn wir annehmen, dass 0=\(\emptyset\) und \(a,b,c\in \Sigma\), dann sind das alles regulaere Ausdruecke.

Hilft die Antwort weiter?

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: reguläre Sprache von Sigma*

Beitrag von kain »

Hallo,

mir ist der Unterschied zwischen regulären Ausdrücken und Sprachen nicht so ganz klar. Bitte um Hilfe und Beispiele.

Z.B.:

\(\Sigma\) = {a, b} ist das Alphabet
L \(\subseteq \Sigma\) ist die Sprache
L = L(aa* + bb*) ist die akzeptierende Sprache / Ausdruck?

Was ist jetzt der Ausdruck / Sprache?

kartzow
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 8. Apr 2010 14:12

Re: reguläre Sprache von Sigma*

Beitrag von kartzow »

in deinem Beispiel ist \(aa^*+ bb^*\) ein regulaerer Ausdruck

und mit \(L(aa^* + bb^*)\) bezeichnen wir die Sprache die dieser regulaere Ausdruck beschreibt.

Im allgemeinen ist jede Teilmenge von \(\Sigma^*\) eine Sprache und regulaere Ausdruecke sind eben ausdruecke aus den
Elementen des Alphabets und aus \(\emptyset\) , die mit + und * und hinternanderschreiben zusammen gesetzt werden (wobei natuerlich noch klammerung auftritt)

Modius
Erstie
Erstie
Beiträge: 19
Registriert: 9. Okt 2009 12:15

Re: reguläre Sprache von Sigma*

Beitrag von Modius »

Also die genaue Aufgabenstellung für die drei oben genannten Ausdrücke ist wiefolgt:

"Geben Sie für die folgenden regulären Ausdrücke an, ob die beschriebene Sprache gleich \(\Sigma\)* ist."

Kommt aus der FGdI 1 Klausur WS05\06
Die Wissenschaft nötigt uns, den Glauben an einfache Kausalitäten aufzugeben.
(Nitzsche)

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: reguläre Sprache von Sigma*

Beitrag von JanM »

also, i) ist die beschriebene Sprache ungleich \(\Sigma^*\), da x=aba in \(\Sigma^*\) aber nicht in der beschriebenen Sprache. Damit können die Sprachen nicht gleich sein.

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Re: reguläre Sprache von Sigma*

Beitrag von igor.a »

seh ich nicht so:
0* ist nämlich epsilon
(a*b*c*)* = (a+b+c)* (s. Gruppenübung 3)
und damit (a+b+c) (a*b*c*)* = Sigma+
zusammen mit 0*=eps ergibt das Sigma*

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: reguläre Sprache von Sigma*

Beitrag von JanM »

Ich seh das auch so. Nur dass du eine andere Sprache hingeschrieben hast, als oben bei i) stand. da war das a^* b^* c^* nicht gesternt und ist damit nicht gleich sigma-+

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Re: reguläre Sprache von Sigma*

Beitrag von igor.a »

Ist das nicht aus der WS05/06 Klausur? Bis auf 2 kleine Abweichungen stimmts überein und dort wars nämlich gesternt.

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: reguläre Sprache von Sigma*

Beitrag von JanM »

ok, ich hab nur die klausur nicht gesehen gehabt und nur den forum eintrag und hier wars nicht gesternt.
Aber schön, dass wir uns einig sind ;)

Antworten

Zurück zu „Archiv“