Sprache angeben < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:00 Do 18.04.2013 | | Autor: | bandchef |
| Aufgabe | Ein [mm] $\epsilon$-NEA $M=\{Q,\Sigma,\delta, q_0, F\}$ [/mm] ist ein NEA mit erweiterter Übergangsfunktion:
[mm] $\delta: [/mm] Q [mm] \times (\Sigma \cup \{\epsilon\}) \rightarrow [/mm] P(Q)$
Interpretation: [mm] $\epsilon$ [/mm] Übergänge sind spontane Zustandsänderungen, die unabhängig vom Zeichen stattfinden, und die die Position des Lesekopfes unverändert lassen. Zu jedem Zeitpunkt können belieibig viele [mm] $\epsilon$-Übergänge [/mm] stattfinden.
- Welche Sprache L(M) akzeptiert der [mm] $\epsilon$-NEA $M=\{\{q_0, q_1, q_2, q_3\}, \{a,b\}, \delta, q_0, \{q_2,q_3\}\}$?
[/mm]
- Entwerfen sie einen DEA und einen [mm] $\epsilon$-NEA [/mm] für die Sprachen L = [mm] \{a^i b^j c^k | i,j,k \in \mathbb N_0\}$ [/mm] |
Hi Leute!
Die erste Teilaufgabe denke ich habe ich gelöst. Das einzige was mich irritiert, ist, dass von einer Sprache L(M) gesprochen wird! Meiner Ansicht nach, müssten das doch zwei Sprachen sein, oder? Wie man in dem NEA sieht, kann ich ja von q0 aus direkt in q2 kommen oder von q0 aus über das [mm] $\epsilon$ [/mm] sowie über q1 nach q2...
Bild vom NEA: [Externes Bild http://s1.directupload.net/images/130418/nzcep8kt.png]
Die zweite Teilaufgabe ist mir ein Rätsel... Die angegebene Sprache kann doch niemals durch einen DEA formalisiert werden, oder? Sprachen die man mit DEAs bauen kann müssen regulär sein; die angegebene Sprache ist aber doch niemals regulär, oder?
Bei der zweiten Teilaufgabe bräuchte ich etwas mehr Hilfe...
Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:56 Do 18.04.2013 | | Autor: | geograf |
Hallo!
Zur Frage 1 fehlt da wohl ein Teil der Angabe, nämlich wie [mm] \delta [/mm] eigentlich definiert ist.
Frage 2: die angegebene Sprache ist sehr wohl regulär, da die i,j,k ja in keiner Beziehung zueinander stehen. Drei Zustände reichen für den DEA aus.
Viel Erfolg!
Geograf
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:25 Fr 19.04.2013 | | Autor: | bandchef |
Du hast Recht. Die Interpretation vom eps-Nea hab ich vergessen hinzuschreiben. Hab ich aber nun editiert!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:39 Fr 19.04.2013 | | Autor: | bandchef |
Ich verstehe nicht, wie ich die Sprache in einen Automaten fassen soll! Da $i,j,k [mm] \in \mathbb N_0$ [/mm] gilt, akzeptiert der Automat ja auch das leere Wort!
Ich hab hier nun drei Zustände: q0 q1 und q2. q0 mit Eigenschleife auf sich selbst mit a, q1 mit Eigenschleife auf sich selbst mit b und q2 mit Eigenschleife auf sich selbst mit c. Der Zustand q2 ist akzeptierend.
Das dumme sind jetzt die Übergänge zwischen den Zuständen des DEAs! Das kapiere ich nicht! Ich kann ja von q0 ausgehenden nicht mit a (dann wäre es ja ein NEA) oder mit einem b oder c weitergehen, denn dann würde ja gefordert, dass mindestens ein b oder c kommen MUSS. Da der Automate aber auch das leere Wort akzeptieren muss weil [mm] $\mathbb N_0$ [/mm] kapier ich das irgendwie nicht.
Der [mm] $\epsilon$-Nea [/mm] ist einfacher; die gleiche Konstruktion wie ich gerade beschrieben habe, nur komm ich von Zustand q0 zu q1 mit einem eps und von q1 nach q2 mit einem eps. Fertig.
Kannst du mir nochmal helfen bzw. sagen ob der eps-Nea passt?
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:24 Sa 20.04.2013 | | Autor: | tobit09 |
> Ich verstehe nicht, wie ich die Sprache in einen Automaten
> fassen soll! Da [mm]i,j,k \in \mathbb N_0[/mm] gilt, akzeptiert der
> Automat ja auch das leere Wort!
>
> Ich hab hier nun drei Zustände: q0 q1 und q2. q0 mit
> Eigenschleife auf sich selbst mit a, q1 mit Eigenschleife
> auf sich selbst mit b und q2 mit Eigenschleife auf sich
> selbst mit c. Der Zustand q2 ist akzeptierend.
>
> Das dumme sind jetzt die Übergänge zwischen den
> Zuständen des DEAs! Das kapiere ich nicht! Ich kann ja von
> q0 ausgehenden nicht mit a (dann wäre es ja ein NEA) oder
> mit einem b oder c weitergehen, denn dann würde ja
> gefordert, dass mindestens ein b oder c kommen MUSS. Da der
> Automate aber auch das leere Wort akzeptieren muss weil
> [mm]\mathbb N_0[/mm] kapier ich das irgendwie nicht.
>
>
> Der [mm]\epsilon[/mm]-Nea ist einfacher; die gleiche Konstruktion
> wie ich gerade beschrieben habe, nur komm ich von Zustand
> q0 zu q1 mit einem eps und von q1 nach q2 mit einem eps.
> Fertig.
>
>
> Kannst du mir nochmal helfen bzw. sagen ob der eps-Nea
> passt?
Ja, er passt ![[ok]](/images/smileys/ok.gif "[ok]") !
Für den DEA beachte, dass es auch mehrere Endzustände geben kann!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:38 Sa 20.04.2013 | | Autor: | bandchef |
Kannst du auf den DEA nochmals eingehen? Ich komm einfach nicht drauf... Ich komm immer nur auf den gleichen NEA. Und der braucht dann für die erste Transition mindestens ein b und für die zweite minestens ein c. Aber das ist ja laut Definition falsch!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:51 Sa 20.04.2013 | | Autor: | tobit09 |
> Kannst du auf den DEA nochmals eingehen? Ich komm einfach
> nicht drauf... Ich komm immer nur auf den gleichen NEA. Und
> der braucht dann für die erste Transition mindestens ein b
> und für die zweite minestens ein c. Aber das ist ja laut
> Definition falsch!
Mache [mm] $q_0$, $q_1$ [/mm] und [mm] $q_2$ [/mm] zu akzeptierenden Zuständen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:54 Sa 20.04.2013 | | Autor: | bandchef |
Genau das hab ich mittlerweile auch gemacht. Aber dann stellen wir uns mal das Wort vor: [mm] $a^0b^0c^1$. [/mm] Das geht dann da nicht, weil ich durch [mm] b^0 [/mm] nicht an die Transition von q1 nach q2 komme!
Verstesht du was ich meine?
Hier noch ein Link auf den Automaten: http://s7.directupload.net/images/130420/jrkw5kwi.jpg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:16 Sa 20.04.2013 | | Autor: | tobit09 |
> Genau das hab ich mittlerweile auch gemacht. Aber dann
> stellen wir uns mal das Wort vor: [mm]a^0b^0c^1[/mm]. Das geht dann
> da nicht, weil ich durch [mm]b^0[/mm] nicht an die Transition von q1
> nach q2 komme!
>
> Verstesht du was ich meine?
Ja.
Füge daher eine mit $c$ beschriftete Transition von [mm] $q_0$ [/mm] nach [mm] $q_2$ [/mm] hinzu.
Schließlich musst du noch sicherstellen, tatsächlich einen DETERMINISTISCHEN endlichen Automaten zu konstruieren. Es muss also von jedem Zustand aus für jeden der Buchstaben a, b und c eine Transition geben.
Du wirst daher einen vierten (nicht akzeptierenden) Zustand benötigen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:30 Sa 20.04.2013 | | Autor: | bandchef |
Ich denke ich hab jetzt mal die Anforderungen von dir recht gut umgesetzt. Von jedem der drei akzeptierenden Zuständen geht jeweils eine Kante mit a,b und c weg.
Was ich nun nicht ganz verstehe ist die Sache, warum ich einen vierten Zustand brauche, der nicht akzeptierend ist.
Hier nochmal ein Bild: http://s1.directupload.net/images/130420/atqbej5q.jpg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:34 Sa 20.04.2013 | | Autor: | tobit09 |
> Ich denke ich hab jetzt mal die Anforderungen von dir recht
> gut umgesetzt. Von jedem der drei akzeptierenden Zuständen
> geht jeweils eine Kante mit a,b und c weg.
>
> Was ich nun nicht ganz verstehe ist die Sache, warum ich
> einen vierten Zustand brauche, der nicht akzeptierend ist.
Dein jetziger Automat akzeptiert jedes Wort über dem Alphabet [mm] $\{a,b,c\}$, [/mm] nicht nur die Worte von der gewünschten Form!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:41 Sa 20.04.2013 | | Autor: | bandchef |
Wenn ich von dem jetzigen Automaten die Transition a von q1 nach q0 sowie die Transition b von q2 nach q1 und die Transition a von q2 nach q0 lösche, dann bin ich bei dem Automaten wie du gerade meintest.
Aber das stimmt ja so noch nicht. Ich brauch jetzt so mindestens ein b oder ein c was nicht die Definition der Sprache ist...
Es kann doch nicht sein, dass das so schwierig ist!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:49 Sa 20.04.2013 | | Autor: | tobit09 |
> Wenn ich von dem jetzigen Automaten die Transition a von q1
> nach q0 sowie die Transition b von q2 nach q1 und die
> Transition a von q2 nach q0 lösche, dann bin ich bei dem
> Automaten wie du gerade meintest.
Jetzt müssen nur noch die "falschen" Buchstaben vom Automaten in der Art verarbeitet werden, dass sie in einen zusätzlichen nicht akzeptierenden "Fehlerzustand" führen.
> Aber das stimmt ja so noch nicht. Ich brauch jetzt so
> mindestens ein b oder ein c was nicht die Definition der
> Sprache ist...
Das Problem sehe ich nicht, solange [mm] $q_0$ [/mm] und [mm] $q_1$ [/mm] akzeptierend bleiben.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:57 Sa 20.04.2013 | | Autor: | bandchef |
So, hier dann noch ein weiterer Versuch mit der Umsetzung deines letzten Tips mit dem Fehlerzustand. Hier als leere Menge gekennzeichnet!
Bild: http://s7.directupload.net/images/130420/kucnixhb.jpg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:03 Sa 20.04.2013 | | Autor: | tobit09 |
> So, hier dann noch ein weiterer Versuch mit der Umsetzung
> deines letzten Tips mit dem Fehlerzustand. Hier als leere
> Menge gekennzeichnet!
>
> Bild: http://s7.directupload.net/images/130420/kucnixhb.jpg
Dieser Automat leistet das Gewünschte, wenn du noch eine mit c beschriftete Transposition vom "Fehlerzustand" [mm] $\emptyset$ [/mm] zu sich selbst ergänzt!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:08 Sa 20.04.2013 | | Autor: | bandchef |
Du wirst lachen; genau diese c-Eigenschleife im Fehlerzustand hatte ich dran gemacht. Ich hab sie aber dann nach längerem Überlegen wieder gelöscht, weil ich mir gedacht habe, dass dieser Fehlerzustand keine c-Eigenschleife benötigt, weil keine c-Transition zum Fehlerzustand hingeht und somit gar kein c "verbrannt" werden kann.
Könnte man so argumentieren oder ist das schlicht falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:19 Sa 20.04.2013 | | Autor: | tobit09 |
> Du wirst lachen; genau diese c-Eigenschleife im
> Fehlerzustand hatte ich dran gemacht. Ich hab sie aber dann
> nach längerem Überlegen wieder gelöscht, weil ich mir
> gedacht habe, dass dieser Fehlerzustand keine
> c-Eigenschleife benötigt, weil keine c-Transition zum
> Fehlerzustand hingeht und somit gar kein c "verbrannt"
> werden kann.
>
> Könnte man so argumentieren oder ist das schlicht falsch?
Das wäre falsch. DEA's sind (im Gegensatz zu NEA's) so definiert, dass von jedem Zustand aus zu jedem Buchstaben des Alphabetes eine Transposition ausgeht.
(Anschaulich: Jemand könnte ja "in den Automaten das (nicht von ihm akzeptierte) Wort bac eingeben". Dann ist er nach Eingabe von ba schon beim Fehlerzustand. Dann kommt jedoch noch ein c und "der Automat muss wissen, in welchen Zustand er mit der Eingabe c übergehen soll".)
Vielleicht ist es eine gute Übung (wenn nicht sogar gefordert), den Automaten nicht nur per Diagramm, sondern auch als formales Tupel anzugeben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:38 So 21.04.2013 | | Autor: | bandchef |
Danke für deine Hilfe!
Eine weitere Aufgabe den Automaten als formales Tupel anzugeben steht nicht dabei.
Ich denke die Aufgabe ist nun richtig gelöst! Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:33 Fr 19.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Die erste Teilaufgabe denke ich habe ich gelöst. Das
> einzige was mich irritiert, ist, dass von einer Sprache
> L(M) gesprochen wird! Meiner Ansicht nach, müssten das
> doch zwei Sprachen sein, oder? Wie man in dem NEA sieht,
> kann ich ja von q0 aus direkt in q2 kommen oder von q0 aus
> über das [mm]\epsilon[/mm] sowie über q1 nach q2...
>
> Bild vom NEA:
> [Externes Bild http://s1.directupload.net/images/130418/nzcep8kt.png]
Jeder [mm] $\varepsilon$-NEA [/mm] $M$ hat genau eine Sprache $L(M)$. $L(M)$ ist die Menge ALLER Wörter, die sich mit $M$ bilden lassen.
Wenn $M$ der durch das Bild gegebene [mm] $\varepsilon$-NEA [/mm] ist und [mm] $L_1(M)$ [/mm] und [mm] $L_2(M)$ [/mm] wie auf dem Bild definiert sind, gilt:
[mm] $L(M)=L_1(M)\cup L_2(M)$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:22 Fr 19.04.2013 | | Autor: | bandchef |
Reicht dann für die richtige Lösung der zweiten Teil-Aufgabe wenn ich die Aufgabe wie auf dem Bild hinschreibe nur noch mit dem Zusatz, dass gilt: $ [mm] L(M)=L_1(M)\cup L_2(M) [/mm] $?
Den auf dem Bild gezeichneten NEA hab ich aus der Definitionsvorschrift von der hier angegebenen Aufgabe erstellt. Könntest du kurz drüber schaun, ob ich ihn auch wirklich richtig konstruiert habe?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:18 Sa 20.04.2013 | | Autor: | tobit09 |
> Reicht dann für die richtige Lösung der zweiten
> Teil-Aufgabe wenn ich die Aufgabe wie auf dem Bild
> hinschreibe nur noch mit dem Zusatz, dass gilt:
> [mm]L(M)=L_1(M)\cup L_2(M) [/mm]?
Da in der Aufgabenstellung nicht von einem Beweis die Rede ist, sondern nur von "angeben", denke ich, dass das genügt.
Ich würde zwischen $:=$ statt $=$ zwischen [mm] $L_2(M)$ [/mm] und [mm] $\{b\}$ [/mm] schreiben und analog bei [mm] $L_1(M)$, [/mm] denn [mm] $L_1(M)$ [/mm] und [mm] $L_2(M)$ [/mm] sind ja im Gegensatz zu $L(M)$ keine bereits definierten Mengen.
> Den auf dem Bild gezeichneten NEA hab ich aus der
> Definitionsvorschrift von der hier angegebenen Aufgabe
> erstellt. Könntest du kurz drüber schaun, ob ich ihn auch
> wirklich richtig konstruiert habe?
Alles bis auf die Zustandsübergänge stimmt. Die Zustandsübergänge kann ich nicht prüfen, da nach wie vor die Angabe von [mm] $\delta$ [/mm] fehlt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:34 Sa 20.04.2013 | | Autor: | bandchef |
Wir haben die Zustandsübergangsfunktion für einen DEA so definiert: [mm] $\delta: [/mm] Q [mm] \times \Sigma \rightarrow [/mm] P(Q)$
Und für einen NEA (auch) so: [mm] $\delta: [/mm] Q [mm] \times \Sigma \rightarrow [/mm] P(Q)$
Bei deiner letzten Antwort verstehe ich diesen Satz nicht: "Ich würde zwischen $ := $ statt $ = $ zwischen $ [mm] L_2(M) [/mm] $ und $ [mm] \{b\} [/mm] $ schreiben und analog bei $ [mm] L_1(M) [/mm] $, denn $ [mm] L_1(M) [/mm] $ und $ [mm] L_2(M) [/mm] $ sind ja im Gegensatz zu $ L(M) $ keine bereits definierten Mengen."
Ich hätte hier gesagt, dass gerade L(1) und L(2) SCHON definierte Mengen sind!
Auch fehlt doch hier irgendwas nach dem dritten Wort "zwischen", oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:49 Sa 20.04.2013 | | Autor: | tobit09 |
> Wir haben die Zustandsübergangsfunktion für einen DEA so
> definiert: [mm]\delta: Q \times \Sigma \rightarrow P(Q)[/mm]
Es muss am Ende Q statt P(Q) heißen.
Das ist aus der allgemeinen Definition eines DEA. Wie lautet nun [mm] $\delta$ [/mm] im Falle unseres konkreten Beispieles für $M$? Welche Abbildung [mm] $\delta: [/mm] Q [mm] \times \Sigma \rightarrow [/mm] Q$ gehört zu unserem $M$?
> Bei deiner letzten Antwort verstehe ich diesen Satz nicht:
> "Ich würde zwischen [mm]:=[/mm] statt [mm]=[/mm] zwischen [mm]L_2(M)[/mm] und [mm]\{b\}[/mm]
> schreiben und analog bei [mm]L_1(M) [/mm], denn [mm]L_1(M)[/mm] und [mm]L_2(M)[/mm]
> sind ja im Gegensatz zu [mm]L(M)[/mm] keine bereits definierten
> Mengen."
Sorry, da ist mir ein "zwischen" zu viel reingerutscht. Schreibe
[mm] $L_2(M):=\{b\}$
[/mm]
statt
[mm] $L_2(M)=\{b\}$.
[/mm]
> Ich hätte hier gesagt, dass gerade L(1) und L(2) SCHON
> definierte Mengen sind!
$L(M)$ habt ihr ja in der Vorlesung definiert. Hattet ihr etwa auch eine Definition von [mm] $L_1(M)$? [/mm] Wenn ja, wie lautet sie?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:57 Sa 20.04.2013 | | Autor: | bandchef |
[mm] $L_1(M)$ [/mm] wurde nicht definiert.
$L(M)$ schon: $L(M) = [mm] \{ x | \delta(q_0,x) \in F \}$
[/mm]
Ich hoffe, dass das jetzt das ist was du noch brauchst.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:10 Sa 20.04.2013 | | Autor: | tobit09 |
> [mm]L_1(M)[/mm] wurde nicht definiert.
Hätte mich auch überrascht, wenn ihr das definiert hättet... 
Also definierst du somit eine neue Menge. Das würde ich durch ":=" statt "=" deutlich machen.
|
|
|
|
