Thema: 2 Klausuraufgaben (reguläre Sprachen) |
|
Hallo,
danke für deine Antwort Karlito.
Zu 2b)
Deiner Argumentation kann ich folgen und finde die Idee auch gut.
DU hast also einen Algorithmus angegeben, der ein DFA, welcher L akzeptiert, zu einem anderen endlichen Automaten umwandelt, wecher L/a akzeptiert.
Wär ich nie drauf gekommen...^^
Dennoch müsste man 3. etwas modifizeiren glaub ich (sofern ich deinen Algo richtig nachvollzogen hab):
Jeder Zustandsübergang zu einem Finalzustand mit der Eingabe "a" wird gestrichen und die Vorgängerzustände dieser gestrichenen Zustandsübertragungen werden zu Finalzustände.
Jeder andere Zustandsübergang zu einem Finalzustand wird nur gestrichen.
Sonst wäre wenn wir das Beispiel von oben nehmen:
L= {wa,xa,ya,z}
-> L/a = {w,x,y}
Dann wäre auch z in L/a drin, was aber nicht sein soll
Ja, die 2. Aufgabe ist wirklich sehr knifflig besonders für eine Klausuraufgabe.
Wenn mir was dazu einfällt bzw. die Lösung zu der 2. Aufgabe habe, werde ich mich nomma melden.
|
|
Thema: 2 Klausuraufgaben (reguläre Sprachen) |
|
Hallo,
ich komme gleich zur Sache:
Ich bin dabei mich auf eine Prüfung vorzubereiten und bin über paar Aufgaben gestolpert wo ich mir nicht sicher bin
1. Aufgabe (Theorie Frage)
Nimm zur folgenden Aussage Stellung:
"Es gibt unendlich viele Typ1-Sprachen, die durch reguläre Ausdrücke beschrieben werden können."
Mein Lösungsvorschlag:
So hier habe ich ein Ansatz/Lösungsvorschlag bei dem ich aber nicht sicher bin.
-> Jede endliche Sprache ist regulär. Es gibt unendlich viele endliche Sprachen(?).
Also Beispiel für Alphabet={a} => {a},{aa},{aaa},{a....} alles endliche Sprachen und man kann das unendlich fort führen.
-> Also gibt es unendliche viele reguläre Sprachen.
-> Reguläre Sprachen lassen sich durch einen regulären Ausdruck beschreiben.
-> Da jede reguläre Sprache (typ3) auch eine Typ1 Sprache ist, stimmmt die Aussage.
Korrekt?
Das heißt, es gibt auch unendlich viele Typ3 Sprachen (das war das was mich noch unsicher macht)?
2. Aufgabe
Hier habe ich ehrlich gesagt keinen Ansatz. Also was mir klar ist, ist was L/a ist.
Beispiel:
L= {wa,xa,ya,z}
-> L/a = {w,x,y}
Richtig?
Ich kann hier aber nirgends sehen wie man hier mit Abschlusseigenschaften rangehen soll.
Hier bräuchte ich dringend Hilfe.
Hoffe es sind hier schlaue Köpfe dabei die mir weiterhelfen können.
Danke im Voraus
|
|
|