Reguläre Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:12 Do 25.04.2013 | | Autor: | bandchef |
| Aufgabe | Sei [mm] $L_3$ [/mm] die Menge aller regulären Sprachen. Zeigen Sie, dass für [mm] $L_1, L_2 \in L_3$ [/mm] gilt:
1.) [mm] $L_1 \cup L_2 \in L_3$
[/mm]
2.) [mm] $L_1L_2 \in L_3$
[/mm]
3.) [mm] $L_1^{\star} \in L_3$ [/mm] |
Für die Teilaufgabe 1.) bin ich so vorgegangen:
[mm] $M_1 [/mm] = [mm] (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)$
[/mm]
[mm] $M_2 [/mm] = [mm] (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)$
[/mm]
[mm] $M_3 [/mm] = [mm] (Q_1 \times Q_2, \Sigma_1 \cup \Sigma_2, \delta_3, (q_0^1, q_0^2), F_3)$
[/mm]
[mm] $F_3 [/mm] = [mm] \{(q_i, q_j) | q_i \in F_1 \vee q_j \in F_2\}
[/mm]
[mm] $\delta_3 [/mm] = [mm] ((q_i, q_j), [/mm] x) = [mm] (q_i^{'}, q_j^{'}) \Leftrightarrow \delta_1(q_i, [/mm] x) = [mm] q_i^{'} \text{ oder } \delta_2(q_j, [/mm] x) = [mm] q_j^{'}$
[/mm]
Durch die Vorlseung weiß ich mittlerweile, dass das so stimmt. Nun würde ich aber gerne die 2.) lösen. Hier weiß ich aber jetzt so gar nicht weiter :-(
Kann mir jemand helfen?
Angefangen hab ich natürlich schon:
[mm] $M_1 [/mm] = [mm] (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)$
[/mm]
[mm] $M_2 [/mm] = [mm] (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)$
[/mm]
[mm] $M_3 [/mm] = [mm] (Q_3, \Sigma_1 \cap \Sigma_2, \delta_3, q_0^1, [/mm] ?)$
Bei der Menge der akzeptierenden Zustände weiß ich dann schon nicht mehr weiter :-(
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:40 Fr 26.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Sei [mm]L_3[/mm] die Menge aller regulären Sprachen. Zeigen Sie,
> dass für [mm]L_1, L_2 \in L_3[/mm] gilt:
>
> 1.) [mm]L_1 \cup L_2 \in L_3[/mm]
> 2.) [mm]L_1L_2 \in L_3[/mm]
> 3.)
> [mm]L_1^{\star} \in L_3[/mm]
> Für die Teilaufgabe 1.) bin ich so
> vorgegangen:
Seien [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] reguläre Sprachen. Dann gibt es deterministische endlichen Automaten
> [mm]M_1 = (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)[/mm]
> [mm]M_2 = (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)[/mm]
mit [mm] $L(M_1)=L_1$ [/mm] und [mm] $L(M_2)=L_2$.
[/mm]
Um die Regularität von [mm] $L_1\cup L_2$ [/mm] zu verifizieren, geben wir einen deterministischen endlichen Automaten [mm] $M_3$ [/mm] mit [mm] $L(M_3)=L_1\cup L_2$ [/mm] an:
> [mm]M_3 = (Q_1 \times Q_2, \Sigma_1 \cup \Sigma_2, \delta_3, (q_0^1, q_0^2), F_3)[/mm]
>
> [mm]$F_3[/mm] = [mm]\{(q_i, q_j) | q_i \in F_1 \vee q_j \in F_2\}[/mm]
>
> [mm]\delta_3 = ((q_i, q_j), x) = (q_i^{'}, q_j^{'}) \Leftrightarrow \delta_1(q_i, x) = q_i^{'} \text{ oder } \delta_2(q_j, x) = q_j^{'}[/mm]
Es muss "und" statt "oder" heißen. Einfacher aufgeschrieben:
[mm] $\delta_3((q_1,q_2)):=(\delta_1(q_1),\delta_2(q_2))$.
[/mm]
> Nun würde ich aber gerne die 2.) lösen.
Es heißt dort wirklich [mm] $L_1L_2$ [/mm] und nicht [mm] $L_1\cap L_2$, [/mm] oder?
> Hier
> weiß ich aber jetzt so gar nicht weiter :-(
>
> Kann mir jemand helfen?
>
> Angefangen hab ich natürlich schon:
>
> [mm]M_1 = (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)[/mm]
> [mm]M_2 = (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)[/mm]
>
> [mm]M_3 = (Q_3, \Sigma_1 \cap \Sigma_2, \delta_3, q_0^1, ?)[/mm]
>
> Bei der Menge der akzeptierenden Zustände weiß ich dann
> schon nicht mehr weiter :-(
Wenn
[mm] $M_3=(Q_3,\Sigma_3,\delta_3,q_0^3, F_3)$
[/mm]
gelten soll: Bisher hast du nur [mm] $q_3:=q_0^1$ [/mm] und [mm] $\Sigma_3:=\Sigma_1\cap\Sigma_2$ [/mm] erklärt, die anderen drei Komponenten müsstest du noch erklären.
Kannst du wirklich [mm] $\Sigma_3:=\Sigma_1\cap\Sigma_2$ [/mm] wählen? [mm] $\Sigma_3$ [/mm] soll ja ein Alphabet sein, über dem [mm] $L_1L_2$ [/mm] eine Sprache ist...
Einfacher als die Angabe eines DEA für [mm] $L_1L_2$ [/mm] ist wohl die Angabe eines [mm] $\varepsilon$-NEA [/mm] für diese Sprache.
Seine Zustände sollten "registrieren", ob man im Moment noch bei der Ableitung vom Wortteil aus [mm] $L_1$ [/mm] oder schon bei der Ableitung vom Wortteil aus [mm] $L_2$ [/mm] ist. Es sind also zwei Arten von Zuständen sinnvoll: Gewisse Zustände, die während der Ableitung vom Wortteil aus [mm] $L_1$ [/mm] durchlaufen werden und gewisse Zustände, die während der Ableitung vom Wortteil aus [mm] $L_2$ [/mm] durchlaufen werden.
Vielleicht versuchst du zunächst einmal in Worten zu beschreiben, wie [mm] $M_3$ [/mm] aussehen soll (Welche Zustände hat er? Welche davon sollen Start- und Endzustände sein? Welche Arten von Übergängen sind vorgesehen?), bevor du dich an die formale Notation als 5-Tupel machst.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:22 Sa 27.04.2013 | | Autor: | bandchef |
> Es heißt dort wirklich $ [mm] L_1L_2 [/mm] $ und nicht $ [mm] L_1\cap L_2 [/mm] $, oder?
Ja, es heißt bei der zweiten Teilaufgabe sicher $ [mm] L_1L_2 [/mm] $ (Konkatenation, quas) und nicht $ [mm] L_1\cap L_2 [/mm] $.
> Vielleicht versuchst du zunächst einmal in Worten zu beschreiben, wie $ [mm] M_3 [/mm] $ aussehen soll (Welche Zustände hat er?
> Welche davon sollen Start- und Endzustände sein? Welche Arten von Übergängen sind vorgesehen?), bevor du dich an die
> formale Notation als 5-Tupel machst.
Du hast Recht. Eine wörtlichen Beschreibung macht hier vielleicht wirklich Sinn. Ich brauch also einen DEA bzw. der Einfachheit halber einen [mm] $\epsilon$-NEA. [/mm] Ich hab auch schon einen ganz konkrete Vorstellung: Ich hab also einen Automaten M1, der die Sprache L1 akzeptiert. Des Weiteren hab ich einen Automaten M2 der die Sprache M2 akzeptiert. Nun soll ich einen Automaten M3 bauen, der Konkatenation der Sprachen L1L2 formalisiert. Ich denke, dass eine hintereinanderschaltung der beiden Automaten M1 und M2 mit einer [mm] $\epsilon$-Transition [/mm] zum richtigen Ergebnis führt. Ich hab hier auch mal ein Bild gemalt, wie ich mir das vorstelle: http://s14.directupload.net/images/130427/v5iayo8b.jpg
Ich probier dann denoch gleich mal die formale Notation:
$ [mm] M_1 [/mm] = [mm] (Q_1, \Sigma_1, \delta_1, q_0^1, F_1) [/mm] $
$ [mm] M_2 [/mm] = [mm] (Q_2, \Sigma_2, \delta_2, q_0^2, F_2) [/mm] $
$ [mm] M_3 [/mm] = [mm] (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \{\delta_1, \delta_2\}, \{q_0^1, q_0^2\}, F_1 \cup F_2) [/mm] $
$ [mm] \delta_3 [/mm] := [mm] (Q_1 \cup Q_2) \times ((\Sigma_1 \cup \Sigma_2) \cup \{\epsilon\} [/mm] $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:50 Sa 27.04.2013 | | Autor: | tobit09 |
> Eine wörtlichen Beschreibung macht hier
> vielleicht wirklich Sinn. Ich brauch also einen DEA bzw.
> der Einfachheit halber einen [mm]\epsilon[/mm]-NEA. Ich hab auch
> schon einen ganz konkrete Vorstellung: Ich hab also einen
> Automaten M1, der die Sprache L1 akzeptiert. Des Weiteren
> hab ich einen Automaten M2 der die Sprache M2 akzeptiert.
Du solltest noch festlegen (und hier posten), was für eine Art Automaten M1 und M2 seien sollen (DEA, NEA oder [mm] $\varpsilon$-NEA).
[/mm]
> Nun soll ich einen Automaten M3 bauen, der Konkatenation
> der Sprachen L1L2 formalisiert. Ich denke, dass eine
> hintereinanderschaltung der beiden Automaten M1 und M2 mit
> einer [mm]\epsilon[/mm]-Transition zum richtigen Ergebnis führt.
> Ich hab hier auch mal ein Bild gemalt, wie ich mir das
> vorstelle:
> http://s14.directupload.net/images/130427/v5iayo8b.jpg
Wenn im Beispiel
[mm] $L_1=\{w\in\{a,b\}^\star\;|\;w\not=\epsilon,\text{erster Buchstabe von }w\text{ ist ein }a\}$
[/mm]
und
[mm] $L_2=\{w\in\{a,b\}^\star\;|\;w\not=\epsilon,\text{erster Buchstabe von }w\text{ ist ein }b\}$
[/mm]
sein soll, stimmt die Idee.
(Zunächst ändern wir nötigenfalls [mm] $M_2$ [/mm] so ab, dass [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] keine gemeinsamen Zustände haben. Dazu geben wir den Zuständen von [mm] $M_2$ [/mm] einfach neue Namen, die nicht als Zustände von [mm] $M_1$ [/mm] vorkommen.)
Wir nehmen alle Zustände von [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] als Zustände von [mm] $M_3$.
[/mm]
Startzustand(/stände) sollen nur der(/die) Startzustand(/stände) von [mm] $M_1$ [/mm] sein. Endzustände sollen genau die Endzustände von [mm] $M_2$ [/mm] sein.
Für jeden möglichen Zustandsübergang in [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] sehen wir jeweils einen entsprechenden Zustandsübergang in [mm] $M_3$ [/mm] vor. Außerdem ergänzen wir Übergänge von sämtlichen Endzuständen von [mm] $M_1$ [/mm] in den(/die) Startzustand(/stände) von [mm] $M_2$.
[/mm]
> Ich probier dann denoch gleich mal die formale Notation:
>
> [mm]M_1 = (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)[/mm]
> [mm]M_2 = (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)[/mm]
>
> [mm]M_3 = (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \{\delta_1, \delta_2\}, \{q_0^1, q_0^2\}, F_1 \cup F_2)[/mm]
>
> [mm]\delta_3 := (Q_1 \cup Q_2) \times ((\Sigma_1 \cup \Sigma_2) \cup \{\epsilon\}[/mm]
[mm] $Q_1\cup Q_2$ [/mm] (nachdem [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] keine gemeinsamen Zustände haben): ![[ok]](/images/smileys/ok.gif "[ok]")
[mm] $\Sigma_1\cup\Sigma_2$: [/mm]
[mm] $\{q_0^1, q_0^2\}$: [/mm] Nein, es soll ja in jedem Fall mit einem Wort aus [mm] $L_1$ [/mm] losgehen, nicht mit einem Wort aus [mm] $L_2$.
[/mm]
[mm] $F_1\cup F_2$: [/mm] Nein, wir wollen ja in jedem Fall mit einem Wort aus [mm] $L_2$ [/mm] enden, nicht mit einem Wort aus [mm] $L_1$.
[/mm]
[mm] $\delta_3$ [/mm] hast du überhaupt nicht sinnvoll angegeben. [mm] $\delta_3$ [/mm] muss eine Abbildung
[mm] $\delta_3\colon(Q_1\cup Q_2)\times(\Sigma_1\cup\Sigma_2\cup\{\varepsilon\})\to \mathcal{P}(Q_1\cup Q_2)$
[/mm]
sein.
Gib also nacheinander
[mm] $\delta_3(q_1,a_1)$ [/mm] für [mm] $q_1\in Q_1$, $a_1\in\Sigma_1$,
[/mm]
[mm] $\delta_3(q_2,a_2)$ [/mm] für [mm] $q_2\in Q_2$, $a_2\in\Sigma_2$,
[/mm]
[mm] $\delta_3(q_1,a_2)$ [/mm] für [mm] $q_1\in Q_1$, $a_2\in\Sigma_2\setminus\Sigma_1$,
[/mm]
[mm] $\delta_3(q_2,a_1)$ [/mm] für [mm] $q_2\in Q_2$, $a_1\in\Sigma_1\setminus\Sigma_2$,
[/mm]
[mm] $\delta_3(q_1,\varepsilon)$ [/mm] für [mm] $q_1\in Q_1$,
[/mm]
und [mm] $\delta_3(q_2,\varepsilon)$ [/mm] für [mm] $q_2\in Q_2$
[/mm]
an.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:08 Sa 27.04.2013 | | Autor: | bandchef |
> Du solltest noch festlegen (und hier posten), was für eine Art Automaten M1 und M2 seien sollen (DEA, NEA oder $ [mm] \varpsilon [/mm] $-NEA).
Ich hab auch schon einen ganz konkrete Vorstellung: Ich hab also einen deterministischen endlichen Automaten M1, der die Sprache L1 akzeptiert. Des Weiteren hab ich einen deterministischen endlichen Automaten M2 der die Sprache M2 akzeptiert.
> $ [mm] \{q_0^1, q_0^2\} [/mm] $: Nein, es soll ja in jedem Fall mit einem Wort aus $ [mm] L_1 [/mm] $ losgehen, nicht mit einem Wort aus $ [mm] L_2 [/mm] $.
> $ [mm] F_1\cup F_2 [/mm] $: Nein, wir wollen ja in jedem Fall mit einem Wort aus $ [mm] L_2 [/mm] $ enden, nicht mit einem Wort aus $ [mm] L_1 [/mm] $.
$ [mm] M_1 [/mm] = [mm] (Q_1, \Sigma_1, \delta_1, q_0^1, F_1) [/mm] $
$ [mm] M_2 [/mm] = [mm] (Q_2, \Sigma_2, \delta_2, q_0^2, F_2) [/mm] $
$ [mm] M_3 [/mm] = [mm] (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \delta_3, q_0^1, F_2) [/mm] $
So sollte das nun schon mal besser passen. So wie ich denke, brauch ich [mm] $F_2$ [/mm] (wie bspw. bei der Aufgabe die ich als Beispiel Eingangs gezeigt habe) nicht weiter spezifizieren, weil eben klar ist, welche akzept. Zustände der neue [mm] $\epsilon$-Nea [/mm] haben soll.
>Gib also nacheinander
>
> $ [mm] \delta_3(q_1,a_1) [/mm] $ für $ [mm] q_1\in Q_1 [/mm] $, $ [mm] a_1\in\Sigma_1 [/mm] $,
> $ [mm] \delta_3(q_2,a_2) [/mm] $ für $ [mm] q_2\in Q_2 [/mm] $, $ [mm] a_2\in\Sigma_2 [/mm] $,
>
> $ [mm] \delta_3(q_1,a_2) [/mm] $ für $ [mm] q_1\in Q_1 [/mm] $, $ [mm] a_2\in\Sigma_2\setminus\Sigma_1 [/mm] $,
> $ [mm] \delta_3(q_2,a_1) [/mm] $ für $ [mm] q_2\in Q_2 [/mm] $, $ [mm] a_1\in\Sigma_1\setminus\Sigma_2 [/mm] $,
>
> $ [mm] \delta_3(q_1,\varepsilon) [/mm] $ für $ [mm] q_1\in Q_1 [/mm] $,
>und $ [mm] \delta_3(q_2,\varepsilon) [/mm] $ für $ [mm] q_2\in Q_2 [/mm] $
>an.
Was ich aber leider nun überhaupt nicht verstehe, ist die Angabe der Übergangsfunktion für den [mm] $\epsilon$-NEA [/mm] M3. Beziehst du das nun auf meine beispielhaft angegebenen Sprachen aus meinem ersten Versuch? Kannst du auf die Übergangsfunktion genauer eingehen? Wenn du das nun auf meine Eingangs verwendeten beispielhaften Sprachen bezogen hast, verstehe ich es nicht, warum man das jetzt nicht allgemein machen soll...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:25 Sa 27.04.2013 | | Autor: | tobit09 |
> [mm]M_1 = (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)[/mm]
> [mm]M_2 = (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)[/mm]
>
> [mm]M_3 = (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \delta_3, q_0^1, F_2)[/mm]
>
> So sollte das nun schon mal besser passen.
(Schreibe [mm] $\{q_0^1\}$ [/mm] statt [mm] $q_0^1$, [/mm] denn ein [mm] $\varepsilon$-NEA) [/mm] hat eine Menge von Startzuständen anstelle eines Startzustandes.)
> So wie ich
> denke, brauch ich [mm]F_2[/mm] (wie bspw. bei der Aufgabe die ich
> als Beispiel Eingangs gezeigt habe) nicht weiter
> spezifizieren, weil eben klar ist, welche akzept. Zustände
> der neue [mm]\epsilon[/mm]-Nea haben soll.
![[haee]](/images/smileys/haee.gif "[haee]") [mm] $F_2$ [/mm] ist die Menge der akzeptierenden Zustände von [mm] $M_2$. [/mm] Genau die nehmen wir auch als Menge der akzeptierenden Zustände von [mm] $M_3$.
[/mm]
> >Gib also nacheinander
> >
> > [mm]\delta_3(q_1,a_1)[/mm] für [mm]q_1\in Q_1 [/mm],
> [mm]a_1\in\Sigma_1 [/mm],
> > [mm]\delta_3(q_2,a_2)[/mm] für [mm]q_2\in Q_2 [/mm],
> [mm]a_2\in\Sigma_2 [/mm],
> >
> > [mm]\delta_3(q_1,a_2)[/mm] für [mm]q_1\in Q_1 [/mm],
> [mm]a_2\in\Sigma_2\setminus\Sigma_1 [/mm],
> > [mm]\delta_3(q_2,a_1)[/mm]
> für [mm]q_2\in Q_2 [/mm], [mm]a_1\in\Sigma_1\setminus\Sigma_2 [/mm],
> >
> > [mm]\delta_3(q_1,\varepsilon)[/mm] für [mm]q_1\in Q_1 [/mm],
>
> >und [mm]\delta_3(q_2,\varepsilon)[/mm] für [mm]q_2\in Q_2[/mm]
>
> >an.
>
> Was ich aber leider nun überhaupt nicht verstehe, ist die
> Angabe der Übergangsfunktion für den [mm]\epsilon[/mm]-NEA M3.
> Beziehst du das nun auf meine beispielhaft angegebenen
> Sprachen aus meinem ersten Versuch? Kannst du auf die
> Übergangsfunktion genauer eingehen? Wenn du das nun auf
> meine Eingangs verwendeten beispielhaften Sprachen bezogen
> hast, verstehe ich es nicht, warum man das jetzt nicht
> allgemein machen soll...
Nein, das hat nichts mit deinem Beispiel zu tun.
Etwa mit
"Gib [mm]\delta_3(q_1,a_1)[/mm] für [mm]q_1\in Q_1 [/mm], [mm]a_1\in\Sigma_1 [/mm] an""
meine ich: Gib für alle Zustände [mm] $q_1\in Q_1$ [/mm] von [mm] $M_1$ [/mm] und alle Buchstaben [mm] $a_1\in\Sigma_1$ [/mm] des Alphabetes von [mm] $L_1$ [/mm] die Menge [mm] $\delta_3(q_1,a_1)\subseteq Q_1\cup Q_2$ [/mm] der Zustände an, in die [mm] $M_3$ [/mm] bei Verarbeitung von [mm] $a_1$ [/mm] aus dem Zustand [mm] $q_1$ [/mm] heraus wechseln kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:55 So 28.04.2013 | | Autor: | bandchef |
> >Gib also nacheinander
> >
> > [mm]\delta_3(q_1,a_1)[/mm] für [mm]q_1\in Q_1 [/mm],
> [mm]a_1\in\Sigma_1 [/mm],
> > [mm]\delta_3(q_2,a_2)[/mm] für [mm]q_2\in Q_2 [/mm],
> [mm]a_2\in\Sigma_2 [/mm],
> >
> > [mm]\delta_3(q_1,a_2)[/mm] für [mm]q_1\in Q_1 [/mm],
> [mm]a_2\in\Sigma_2\setminus\Sigma_1 [/mm],
> > [mm]\delta_3(q_2,a_1)[/mm]
> für [mm]q_2\in Q_2 [/mm], [mm]a_1\in\Sigma_1\setminus\Sigma_2 [/mm],
> >
> > [mm]\delta_3(q_1,\varepsilon)[/mm] für [mm]q_1\in Q_1 [/mm],
>
> >und [mm]\delta_3(q_2,\varepsilon)[/mm] für [mm]q_2\in Q_2[/mm]
>
> >an.
Bei diesem Teil den du mir hier geschrieben hast, weiß ich nämlich schon gar nicht wie du da drauf kommst. Wie kommst du da drauf? Was sagt mir das? Ich kann das auch irgendwie nicht richtig interpretieren. Du hast hier vier Übergangsfunktionen angegeben. Warum steht da q1 und q2? Woher kommt das a1 und a2? Was bedeutet das q1? q1 ist ja eigentlich ein einziger Zustand aus allen Zuständen des Automaten M1...; warum aber nun gerade q1? Für q2 gilt die gleiche Frage...
Das obige Problem ist wohl auch das grundsätzliche Problem, warum ich jetzt mit der Antwort leider nix anfangen kann:
>Etwa mit
> "Gib [mm]\delta_3(q_1,a_1)[/mm] für [mm]q_1\in Q_1 [/mm], [mm]a_1\in\Sigma_1 [/mm] an""
>meine ich: Gib für alle Zustände [mm] $q_1\in Q_1$ [/mm] von [mm] $M_1$ [/mm] und alle Buchstaben [mm] $a_1\in\Sigma_1$ [/mm] des Alphabetes von [mm] $L_1$ [/mm] die Menge [mm] >$\delta_3(q_1,a_1)\subseteq Q_1\cup Q_2$ [/mm] der Zustände an, in die [mm] $M_3$ [/mm] bei Verarbeitung von [mm] $a_1$ [/mm] aus dem Zustand [mm] $q_1$ [/mm] heraus >wechseln kann.
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:12 Mo 29.04.2013 | | Autor: | tobit09 |
> > >Gib also nacheinander
> > >
> > > [mm]\delta_3(q_1,a_1)[/mm] für [mm]q_1\in Q_1 [/mm],
> > [mm]a_1\in\Sigma_1 [/mm],
> > > [mm]\delta_3(q_2,a_2)[/mm] für [mm]q_2\in Q_2 [/mm],
> > [mm]a_2\in\Sigma_2 [/mm],
> > >
> > > [mm]\delta_3(q_1,a_2)[/mm] für [mm]q_1\in Q_1 [/mm],
> > [mm]a_2\in\Sigma_2\setminus\Sigma_1 [/mm],
> > > [mm]\delta_3(q_2,a_1)[/mm]
> > für [mm]q_2\in Q_2 [/mm], [mm]a_1\in\Sigma_1\setminus\Sigma_2 [/mm],
> > >
> > > [mm]\delta_3(q_1,\varepsilon)[/mm] für [mm]q_1\in Q_1 [/mm],
> >
> > >und [mm]\delta_3(q_2,\varepsilon)[/mm] für [mm]q_2\in Q_2[/mm]
> >
> > >an.
> Du hast hier vier
> Übergangsfunktionen angegeben.
Nein. Ich habe keine einzige Übergangsfunktion angegeben. Ich habe lediglich geschrieben, was du angeben müsstest, um die gesuchte Übergangsfunktion zu beschreiben.
> Warum steht da q1 und q2?
> Woher kommt das a1 und a2? Was bedeutet das q1? q1 ist ja
> eigentlich ein einziger Zustand aus allen Zuständen des
> Automaten M1...; warum aber nun gerade q1? Für q2 gilt die
> gleiche Frage...
Wir wissen nicht, wie die Zustände von [mm] $Q_1$ [/mm] und [mm] $Q_2$ [/mm] "wirklich" heißen. Wir wissen auch nicht, ob ein Zustand von [mm] $M_1$ [/mm] den Namen [mm] $q_1$ [/mm] trägt. Die Zustände von [mm] $M_1$ [/mm] könnten z.B. "rot", "grün" und "blau" heißen.
Wenn du möchtest, kannst du überall, wo ich [mm] $q_1$ [/mm] oder [mm] $q_2$ [/mm] bzw. [mm] $a_1$ [/mm] oder [mm] $a_2$ [/mm] geschrieben habe, stattdessen $q$ bzw. $a$ schreiben. Ob ich sage "Für alle [mm] $q_1$ [/mm] und [mm] $a_1$ [/mm] soll [mm] $\delta_3(q_1,a_1)$ [/mm] angegeben werden." oder "Für alle $q$ und $a$ soll [mm] $\delta_3(q,a)$ [/mm] angegeben werden" ist völlig egal.
> Bei diesem Teil den du mir hier geschrieben hast, weiß ich
> nämlich schon gar nicht wie du da drauf kommst. Wie kommst
> du da drauf? Was sagt mir das? Ich kann das auch irgendwie
> nicht richtig interpretieren.
Gesucht ist eine Abbildung
[mm] $\delta_3\colon\underbrace{(Q_1\cup Q_2)\times((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\})}_{=:D}\to\mathcal{P}(Q_1\times Q_2)$,
[/mm]
die die Übergänge von [mm] $M_3$ [/mm] beschreibt. Kannst du soweit noch folgen? Ansonsten bitte nachfragen!
Ganz allgemein: Um eine Abbildung [mm] $f\colon X\to [/mm] Y$ anzugeben, muss man $f(x)$ für alle [mm] $x\in [/mm] X$ festlegen.
In unserem Fall, dass wir eine Abbildung [mm] $\delta_3\colon D\to\mathcal{P}(Q_1\times Q_2)$ [/mm] angeben wollen, müssen wir also für alle [mm] $x\in [/mm] D$ den Wert von [mm] $\delta_3(x)$ [/mm] festlegen.
Nun hat $D$ eine spezielle Gestalt: Alle Elemente von $D$ sind Paare der Form $(q,a)$ mit [mm] $q\in Q_1\cup Q_2$ [/mm] und [mm] $a\in((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\})$.
[/mm]
Also können wir genauer sagen: Wir müssen [mm] $\delta_3((q,a))$ [/mm] für alle [mm] $q\in Q_1\cup Q_2$ [/mm] und alle [mm] $a\in((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\})$ [/mm] angeben.
[mm] $\delta_3$ [/mm] soll dabei die Übergänge von [mm] $M_3$ [/mm] in folgendem Sinne beschreiben: Für jeden Zustand $q$ von [mm] $M_3$ [/mm] und jedes Zeichen $a$ aus dem Alphabet von [mm] $M_3$ [/mm] (oder [mm] $a=\varepsilon$) [/mm] soll [mm] $\delta_3((q,a))$ [/mm] die Menge der Zustände von [mm] $M_3$ [/mm] sein, in die [mm] $M_3$ [/mm] aus dem Zustand $q$ bei Lesen des Zeichens $a$ wechseln kann.
Fangen wir also nun an, [mm] $\delta((q,a))$ [/mm] anzugeben.
Was jetzt ist nochmal $q$? Ein beliebiger Zustand von [mm] $M_3$ [/mm] bzw. ein Element von [mm] $Q_1\cup Q_2$. [/mm] Das heißt $q$ ist ein Zustand von [mm] $M_1$ ($q\in Q_1$) [/mm] oder $q$ ist ein Zustand von [mm] $M_2$ ($q\in Q_2$).
[/mm]
Was war nochmal $a$? Ein Element von [mm] $(\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\}$. [/mm] Also [mm] $a\in\Sigma_1$ [/mm] (d.h. $a$ ist ein Element des Alphabetes von [mm] $M_1$) [/mm] oder [mm] $a\in\Sigma_2$ [/mm] (d.h. $a$ ist ein Element des Alphabetes von [mm] $M_2$) [/mm] oder [mm] $a\in\{\varepsilon\}$ [/mm] (d.h. $a$ ist das leere Wort).
Mein Vorschlag war nun, alle diese Fälle separat zu betrachten.
Ich fange mal mit dem Fall [mm] $q\in Q_1$ [/mm] und [mm] $a\in \Sigma_1$ [/mm] an.
In welche Zustände soll [mm] $M_3$ [/mm] wechseln können, wenn er sich in einem Zustand $q$ von [mm] $M_1$ [/mm] befindet und ein Zeichen $a$ des Alphabetes von [mm] $M_1$ [/mm] liest?
Genau in einen Zustand, nämlich den Zustand von [mm] $M_1$, [/mm] in den [mm] $M_1$ [/mm] aus $q$ übergeht, wenn [mm] $M_1$ [/mm] das Zeichen $a$ liest.
Dieser Zustand heißt [mm] $\delta_1((q,a))$.
[/mm]
Also legen wir fest (für jedes [mm] $q\in Q_1$, $a\in\Sigma_1$):
[/mm]
[mm] $\delta((q,a)):=\{\delta_1((q,a))\}$.
[/mm]
Nun sind noch alle anderen Fälle zu betrachten.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:30 Mo 29.04.2013 | | Autor: | bandchef |
Wir wissen nicht, wie die Zustände von $ [mm] Q_1 [/mm] $ und $ [mm] Q_2 [/mm] $ "wirklich" heißen. Wir wissen auch nicht, ob ein Zustand von $ [mm] M_1 [/mm] $ den Namen $ [mm] q_1 [/mm] $ trägt. Die Zustände von $ [mm] M_1 [/mm] $ könnten z.B. "rot", "grün" und "blau" heißen.
Wenn du möchtest, kannst du überall, wo ich $ [mm] q_1 [/mm] $ oder $ [mm] q_2 [/mm] $ bzw. $ [mm] a_1 [/mm] $ oder $ [mm] a_2 [/mm] $ geschrieben habe, stattdessen $ q $ bzw. $ a $ schreiben. Ob ich sage "Für alle $ [mm] q_1 [/mm] $ und $ [mm] a_1 [/mm] $ soll $ [mm] \delta_3(q_1,a_1) [/mm] $ angegeben werden." oder "Für alle $ q $ und $ a $ soll $ [mm] \delta_3(q,a) [/mm] $ angegeben werden" ist völlig egal.
> Bei diesem Teil den du mir hier geschrieben hast, weiß ich
> nämlich schon gar nicht wie du da drauf kommst. Wie kommst
> du da drauf? Was sagt mir das? Ich kann das auch irgendwie
> nicht richtig interpretieren.
Gesucht ist eine Abbildung
$ [mm] \delta_3\colon\underbrace{(Q_1\cup Q_2)\times((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\})}_{=:D}\to\mathcal{P}(Q_1\times Q_2) [/mm] $,
die die Übergänge von $ [mm] M_3 [/mm] $ beschreibt. Kannst du soweit noch folgen? Ansonsten bitte nachfragen!
Ja, soweit ist alles klar. Es handelt sich hier um ein abstraktes Gedankenmodell, das flexibel anwendbar ist. Ich hab's verstanden
Ganz allgemein: Um eine Abbildung $ [mm] f\colon X\to [/mm] Y $ anzugeben, muss man $ f(x) $ für alle $ [mm] x\in [/mm] X $ festlegen.
In unserem Fall, dass wir eine Abbildung $ [mm] \delta_3\colon D\to\mathcal{P}(Q_1\times Q_2) [/mm] $ angeben wollen, müssen wir also für alle $ [mm] x\in [/mm] D $ den Wert von $ [mm] \delta_3(x) [/mm] $ festlegen.
Auch das ist klar. Wenn ich eine Abbildung haben will brauch ich auch wie in der "normalen" Mathematik eine Funktion; hier ist das eben die Übergangsfunktion [mm] $\delta$.
[/mm]
Nun hat $ D $ eine spezielle Gestalt: Alle Elemente von $ D $ sind Paare der Form $ (q,a) $ mit $ [mm] q\in Q_1\cup Q_2 [/mm] $ und $ [mm] a\in((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\}) [/mm] $.
Also können wir genauer sagen: Wir müssen $ [mm] \delta_3((q,a)) [/mm] $ für alle $ [mm] q\in Q_1\cup Q_2 [/mm] $ und alle $ [mm] a\in((\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\}) [/mm] $ angeben.
$ [mm] \delta_3 [/mm] $ soll dabei die Übergänge von $ [mm] M_3 [/mm] $ in folgendem Sinne beschreiben: Für jeden Zustand $ q $ von $ [mm] M_3 [/mm] $ und jedes Zeichen $ a $ aus dem Alphabet von $ [mm] M_3 [/mm] $ (oder $ [mm] a=\varepsilon [/mm] $) soll $ [mm] \delta_3((q,a)) [/mm] $ die Menge der Zustände von $ [mm] M_3 [/mm] $ sein, in die $ [mm] M_3 [/mm] $ aus dem Zustand $ q $ bei Lesen des Zeichens $ a $ wechseln kann.
Fangen wir also nun an, $ [mm] \delta((q,a)) [/mm] $ anzugeben.
Auch bis hierhin ist alles klar. Durch meine Vorlesung ist mir mittlerweile klar, dass so eine Übergangsfunktion immer aus einem Paar besteht, nämlich einem Zustand "q" und einem "Übergangszeichen" "a".
Was jetzt ist nochmal $ q $? Ein beliebiger Zustand von $ [mm] M_3 [/mm] $ bzw. ein Element von $ [mm] Q_1\cup Q_2 [/mm] $. Das heißt $ q $ ist ein Zustand von $ [mm] M_1 [/mm] $ ($ [mm] q\in Q_1 [/mm] $) oder $ q $ ist ein Zustand von $ [mm] M_2 [/mm] $ ($ [mm] q\in Q_2 [/mm] $).
Was war nochmal $ a $? Ein Element von $ [mm] (\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\} [/mm] $. Also $ [mm] a\in\Sigma_1 [/mm] $ (d.h. $ a $ ist ein Element des Alphabetes von $ [mm] M_1 [/mm] $) oder $ [mm] a\in\Sigma_2 [/mm] $ (d.h. $ a $ ist ein Element des Alphabetes von $ [mm] M_2 [/mm] $) oder $ [mm] a\in\{\varepsilon\} [/mm] $ (d.h. $ a $ ist das leere Wort).
Das war eine sehr gute Erklärung. Ich hab's verstanden und ist logisch, dass das aus obigem folgt, auch durch die Vorlesung klar.
Mein Vorschlag war nun, alle diese Fälle separat zu betrachten.
Hier nun meine erste Frage: Warum gibt es Fälle? Wie heißen die Fälle? Wie viel Fälle gibt es? Ich versuch mir nun die Antwort selbst zu geben. Da ich nicht weiß, wie viele Zustände der Automat M1 bzw. M2 hat muss man das wohl unabhängig betrachten, oder?
Ich fange mal mit dem Fall $ [mm] q\in Q_1 [/mm] $ und $ [mm] a\in \Sigma_1 [/mm] $ an.
In welche Zustände soll $ [mm] M_3 [/mm] $ wechseln können, wenn er sich in einem Zustand $ q $ von $ [mm] M_1 [/mm] $ befindet und ein Zeichen $ a $ des Alphabetes von $ [mm] M_1 [/mm] $ liest?
Genau in einen Zustand, nämlich den Zustand von $ [mm] M_1 [/mm] $, in den $ [mm] M_1 [/mm] $ aus $ q $ übergeht, wenn $ [mm] M_1 [/mm] $ das Zeichen $ a $ liest.
Dieser Zustand heißt $ [mm] \delta_1((q,a)) [/mm] $.
Also legen wir fest (für jedes $ [mm] q\in Q_1 [/mm] $, $ [mm] a\in\Sigma_1 [/mm] $):
$ [mm] \delta((q,a)):=\{\delta_1((q,a))\} [/mm] $.
Nun sind noch alle anderen Fälle zu betrachten.
Wie viel Fälle gibt es denn überhaupt noch?
(für jedes $ [mm] q_1\in Q_1 [/mm] $, $ [mm] a\in\Sigma_1 [/mm] $): $ [mm] \delta((q_1,a)):=\{\delta_1((q_1,a))\} [/mm] $ (Was bedeuten eigentlich die Mengenklammern auf jeder rechten Seite der Defintion der Übergangsfunktionen?)
(für jedes $ [mm] q_2\in Q_2 [/mm] $, $ [mm] b\in\Sigma_2 [/mm] $): $ [mm] \delta((q_2,b)):=\{\delta_2((q_2,b))\} [/mm] $
Ist das so richtig? Wenn ich mich richtig entsinne, sieht das jetzt so aus, wie das, was du anfangs angegeben hast, oder? Und wenn ich weiter nachschaue, dann sehe ich, dass man ab jetzt noch zwei weitere Fälle braucht...; aber mit welcher Überlegung kommt man nun auf:
(für jedes $ [mm] q_1\in Q_1 [/mm] $, $ [mm] b\in\Sigma_2 \backslash \Sigma_1 [/mm] $): $ [mm] \delta((q_1,b)):=\{\delta_1((q_1,b))\} [/mm] $ (Warum muss man an dieser Stelle "Alphabet2 ohne Alphabet1" schreiben?)
(für jedes $ [mm] q_2\in Q_2 [/mm] $, $ [mm] a\in\Sigma_1 [/mm] $): $ [mm] \delta((q_2,a)):=\{\delta_2((q_2,a))\} [/mm] $
Und dann hat man doch noch einen Fall für den [mm] $\epsilon\$-Übergang, [/mm] oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:11 Mo 29.04.2013 | | Autor: | tobit09 |
> Was jetzt ist nochmal [mm]q [/mm]? Ein beliebiger Zustand von [mm]M_3[/mm]
> bzw. ein Element von [mm]Q_1\cup Q_2 [/mm]. Das heißt [mm]q[/mm] ist ein
> Zustand von [mm]M_1[/mm] ([mm] q\in Q_1 [/mm]) oder [mm]q[/mm] ist ein Zustand von [mm]M_2[/mm]
> ([mm] q\in Q_2 [/mm]).
>
> Was war nochmal [mm]a [/mm]? Ein Element von
> [mm](\Sigma_1\cup\Sigma_2)\cup\{\varepsilon\} [/mm]. Also
> [mm]a\in\Sigma_1[/mm] (d.h. [mm]a[/mm] ist ein Element des Alphabetes von [mm]M_1 [/mm])
> oder [mm]a\in\Sigma_2[/mm] (d.h. [mm]a[/mm] ist ein Element des Alphabetes
> von [mm]M_2 [/mm]) oder [mm]a\in\{\varepsilon\}[/mm] (d.h. [mm]a[/mm] ist das leere
> Wort).
>
> Das war eine sehr gute Erklärung. Ich hab's verstanden und
> ist logisch, dass das aus obigem folgt, auch durch die
> Vorlesung klar.
>
>
>
>
> Mein Vorschlag war nun, alle diese Fälle separat zu
> betrachten.
>
> Hier nun meine erste Frage: Warum gibt es Fälle? Wie
> heißen die Fälle? Wie viel Fälle gibt es?
[mm] $q\in Q_1$ [/mm] auf der einen Seite und [mm] $q\in Q_2$ [/mm] auf der anderen Seite sind möglich.
[mm] $a\in\Sigma_1$, $a\in\Sigma_2$ [/mm] und [mm] $a=\varepsilon$ [/mm] sind möglich.
Das ergibt jeweils drei Fälle mit [mm] $q\in Q_1$ [/mm] und drei Fälle mit [mm] $q\in Q_2$. [/mm] Also insgesamt sechs Fälle.
> Ich versuch
> mir nun die Antwort selbst zu geben. Da ich nicht weiß,
> wie viele Zustände der Automat M1 bzw. M2 hat muss man das
> wohl unabhängig betrachten, oder?
Ich glaube, du meinst etwas Richtiges.
> Ich fange mal mit dem Fall [mm]q\in Q_1[/mm] und [mm]a\in \Sigma_1[/mm] an.
>
> In welche Zustände soll [mm]M_3[/mm] wechseln können, wenn er sich
> in einem Zustand [mm]q[/mm] von [mm]M_1[/mm] befindet und ein Zeichen [mm]a[/mm] des
> Alphabetes von [mm]M_1[/mm] liest?
>
> Genau in einen Zustand, nämlich den Zustand von [mm]M_1 [/mm], in
> den [mm]M_1[/mm] aus [mm]q[/mm] übergeht, wenn [mm]M_1[/mm] das Zeichen [mm]a[/mm] liest.
>
> Dieser Zustand heißt [mm]\delta_1((q,a)) [/mm].
>
> Also legen wir fest (für jedes [mm]q\in Q_1 [/mm], [mm]a\in\Sigma_1 [/mm]):
>
> [mm]\delta((q,a)):=\{\delta_1((q,a))\} [/mm].
>
>
> Nun sind noch alle anderen Fälle zu betrachten.
>
>
>
>
>
> Wie viel Fälle gibt es denn überhaupt noch?
> (für jedes [mm]q_1\in Q_1 [/mm], [mm]a\in\Sigma_1 [/mm]):
> [mm]\delta((q_1,a)):=\{\delta_1((q_1,a))\}[/mm] (Was bedeuten
> eigentlich die Mengenklammern auf jeder rechten Seite der
> Defintion der Übergangsfunktionen?)
[mm] $\delta_3$ [/mm] soll ja die Übergangsfunktion eines [mm] $\varepsilon$-NEA [/mm] werden, nicht die Übergangsfunktion eines DEA. Und bei einem [mm] $\varepsilon$-NEA [/mm] gibt es ja i.A. nicht "den" Nachfolgerzustand eines Zustandes $q$ bei Einlesen des Zeichens $a$, sondern eine Menge von Nachfolgerzuständen bei Einlesen des Zeichens $a$ (die auch leer sein kann).
Formal soll [mm] $\delta_3$ [/mm] als Übergangsfunktion eines [mm] $\varepsilon$-NEA [/mm] eine Abbildung nach [mm] $\mathcal{P}(Q_1\cup Q_2)$ [/mm] sein, also in die Potenzmenge von [mm] $Q_1\cup Q_2$. $\delta_3((q,a))$ [/mm] muss also stets ein Element dieser Potenzmenge, also eine TEILMENGE von [mm] $Q_1\cup Q_2$ [/mm] sein. Nicht etwa ein Element von [mm] $Q_1\cup Q_2$. [/mm]
> (für jedes [mm]q_2\in Q_2 [/mm], [mm]b\in\Sigma_2 [/mm]):
> [mm]\delta((q_2,b)):=\{\delta_2((q_2,b))\}[/mm]
>
> Ist das so richtig?
> Wenn ich mich richtig entsinne, sieht
> das jetzt so aus, wie das, was du anfangs angegeben hast,
> oder?
Ja.
> Und wenn ich weiter nachschaue, dann sehe ich, dass
> man ab jetzt noch zwei weitere Fälle braucht...;
> aber mit
> welcher Überlegung kommt man nun auf:
>
> (für jedes [mm]q_1\in Q_1 [/mm], [mm]b\in\Sigma_2 \backslash \Sigma_1 [/mm]):
> [mm]\delta((q_1,b)):=\{\delta_1((q_1,b))\}[/mm] (Warum muss man an
> dieser Stelle "Alphabet2 ohne Alphabet1" schreiben?)
Es könnte ja durchaus Elemente $b$ von [mm] $\Sigma_2$ [/mm] geben, die schon Element von [mm] $\Sigma_1$ [/mm] waren. Diese Elemente haben wir ja schon "verarztet". Sie brauchen wir nicht nochmal zu betrachten. (Würden wir sie nochmal betrachten, so müssten wir aufpassen, dass wir nicht für diese $b$ zwei verschiedene Wahlen von [mm] $\delta_3((q_1,b))$ [/mm] treffen.)
Sei also nun [mm] $b\in\Sigma_2\setminus\Sigma_1$. [/mm] Dann ist [mm] $b\notin\Sigma_1$. [/mm] Also können wir nicht [mm] $\delta_1((q_1,b))$ [/mm] bilden. [mm] $\delta_1$ [/mm] ordnet ja nur Paaren [mm] $(q_1,a)$ [/mm] mit [mm] $q_1\in Q_1$ [/mm] und [mm] $a\in\Sigma_1$ [/mm] einen Nachfolgezustand zu. (Den Buchstaben $b$ "kennt" [mm] $M_1$ [/mm] gar nicht.)
Wenn der Automat [mm] $M_3$ [/mm] in einem Zustand aus [mm] $Q_1$ [/mm] ist, soll er zunächst ein Wort aus [mm] $L_1$ [/mm] verarbeiten. Er soll also gar keinen Buchstaben einlesen, der nicht zu [mm] $\Sigma_1$ [/mm] gehört. Welche Zustände kommen also als Nachfolgerzustände von [mm] $q_1\in Q_1$ [/mm] bei Lesen eines Zeichens [mm] $b\in \Sigma_2\setminus\Sigma_1$ [/mm] infrage?
Fasse alle diese Nachfolgerzustände in einer Menge zusammen und wähle diese Menge als [mm] $\delta_3((q_1,b))$.
[/mm]
> (für jedes [mm]q_2\in Q_2 [/mm], [mm]a\in\Sigma_1 [/mm]):
> [mm]\delta((q_2,a)):=\{\delta_2((q_2,a))\}[/mm]
Hier gilt Analoges.
> Und dann hat man doch noch einen Fall für den
> [mm]\epsilon\[/mm]-Übergang, oder?
Ja. (Einen oder zwei Fälle; je nachdem ob du [mm] $q\in Q_1$ [/mm] und [mm] $q\in Q_2$ [/mm] separat oder in einem Aufwasch behandeln möchtest.)
Welche [mm] $\varepsilon$-Übergänge [/mm] soll der Automat nochmal haben?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:55 Di 30.04.2013 | | Autor: | bandchef |
Ich hab dann mal weiter gemacht:
für jedes $ [mm] q_1\in Q_1 [/mm] $, $ [mm] a\in\Sigma_1 [/mm] $): $ [mm] \delta((q_1,a)):=\{\delta_1((q_1,a))\} [/mm] $
für jedes $ [mm] q_2\in Q_2 [/mm] $, $ [mm] b\in\Sigma_2 [/mm] $): $ [mm] \delta((q_2,b)):=\{\delta_2((q_2,b))\} [/mm] $
für jedes $ [mm] q_1\in Q_1 [/mm] $, $ [mm] b\in\Sigma_2 \backslash \Sigma1 [/mm] $): $ [mm] \delta((q_1,b)):=\{\delta_1((q_1,b))\} [/mm] $
für jedes $ [mm] q_2\in Q_2 [/mm] $, $ [mm] a\in\Sigma_1 [/mm] $): $ [mm] \delta((q_2,a)):=\{\delta_1((q_2,a))\} [/mm] $
für jedes $ [mm] q_1\in Q_1 [/mm] $, $ [mm] (\Sigma_1 \times \Sigma_2) \cup \{\epsilon\} [/mm] $): $ [mm] \delta((q_1, \epsilon)):=\{\delta_1((q_1,\epsilon))\} [/mm] $
für jedes $ [mm] q_2\in Q_2 [/mm] $, $ [mm] (\Sigma_1 \times \Sigma_2) \cup \{\epsilon\} [/mm] $): $ [mm] \delta((q_2, \epsilon)):=\{\delta_1((q_1,\epsilon))\} [/mm] $
Stimmt das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:06 Di 30.04.2013 | | Autor: | tobit09 |
> für jedes [mm]q_1\in Q_1 [/mm], [mm]a\in\Sigma_1 [/mm]):
> [mm]\delta((q_1,a)):=\{\delta_1((q_1,a))\}[/mm]
> für jedes [mm]q_2\in Q_2 [/mm], [mm]b\in\Sigma_2 [/mm]):
> [mm]\delta((q_2,b)):=\{\delta_2((q_2,b))\}[/mm]
> für jedes [mm]q_1\in Q_1 [/mm], [mm]b\in\Sigma_2 \backslash \Sigma1 [/mm]):
> [mm]\delta((q_1,b)):=\{\delta_1((q_1,b))\}[/mm]
Wie ich bereits schrieb: Für [mm] $b\notin\Sigma_1$ [/mm] ist [mm] $\delta_1((q_1,b))$ [/mm] überhaupt nicht definiert. Der Automat [mm] $M_1$ [/mm] kennt das Zeichen $b$ gar nicht, hat also auch keinen Nachfolgerzustand von [mm] $q_1$ [/mm] bei Einlesen von $b$; er liest nie $b$ ein.
> für jedes [mm]q_2\in Q_2 [/mm], [mm]a\in\Sigma_1 [/mm]):
> [mm]\delta((q_2,a)):=\{\delta_1((q_2,a))\}[/mm]
Für [mm] $q_2\in Q_2$ [/mm] ist [mm] $\delta_1((q_2,a))$ [/mm] nicht definiert. [mm] $M_1$ [/mm] kennt den Zustand [mm] $q_2$ [/mm] gar nicht. Somit kann seine Übergangsfunktion [mm] $\delta_1$ [/mm] auch keinen Nachfolgerzustand von [mm] $q_2$ [/mm] ermitteln.
> für jedes [mm]q_1\in Q_1 [/mm], [mm](\Sigma_1 \times \Sigma_2) \cup \{\epsilon\} [/mm]):
[mm] $(\Sigma_1\red{\cup}\Sigma_2)\cup\{\varepsilon\}$ [/mm] meinst du sicherlich.
Was soll mit dieser Menge sein?
Vermutlich meinst du einfach "für jedes [mm] $q_1\in Q_1$:".
[/mm]
> [mm]\delta((q_1, \epsilon)):=\{\delta_1((q_1,\epsilon))\}[/mm]
[mm] $M_1$ [/mm] ist ein DEA, kein [mm] $\varepsilon$-NEA. $\delta_1((q_1,\varepsilon))$ [/mm] macht also keinen Sinn.
> für
> jedes [mm]q_2\in Q_2 [/mm], [mm](\Sigma_1 \times \Sigma_2) \cup \{\epsilon\} [/mm]):
> [mm]\delta((q_2, \epsilon)):=\{\delta_1((q_1,\epsilon))\}[/mm]
Hier gilt Analoges.
Wildes herum-Raten hilft hier nicht weiter. Erst wenn du eine Vorstellung davon hast, welche Übergänge [mm] $M_3$ [/mm] haben soll, damit er genau die Wörter aus [mm] $L_1L_2$ [/mm] akzeptiert, kannst du dich an die formale Angabe dieser Übergänge machen. Überlege also vorher, welche Zustände in [mm] $M_3$ [/mm] ein Wort aus [mm] $L_1L_2$ [/mm] mit was für Arten von Übergängen durchlaufen soll.
Vielleicht hilft es dir, zunächst Beispiel-Diagramme von zwei DEAs [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] zu malen. Wie soll nun der Zustandsgraph von einem [mm] $\varepsilon$-NEA $M_3$ [/mm] aussehen, damit er genau die Wörter akzeptiert, die sich durch hintereinander-Schreiben je eines von [mm] $M_1$ [/mm] und eines von [mm] $M_2$ [/mm] akzeptierten Wortes ergeben?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:39 Di 30.04.2013 | | Autor: | bandchef |
Meinst du mit Beispieldiagramme einen Automaten? Sowas hatte ich hier schon mal gemalt: http://s14.directupload.net/images/130427/v5iayo8b.jpg
Ich hab irgendwie ein Problem mit der mathematischen Ausdrucksweise. Dass ich mit diesen beiden Übergangsfunktionen die jetzt mittlerweile stimmen, jeweils den Automat M1 und M2 beschreibe ist klar. Ich muss aber jetzt noch irgendwie einen mathematischen Ausdruck für mich an den Haaren herbeiziehen, der ausdrückt, dass ich von einem Zustand q1 von Automat M1 über ein [mm] $\epsilon$ [/mm] zu einem Zustand q2 vom Automat M2 komme.
Das ist jetzt mein Problem...
Wenn mein Bildchen stimmt, denn bräucht ich ja irgendwie sowas:
[mm] $q_1 \overset{\epsilon}{\rightarrow} q_2$ [/mm] für [mm] $q_1 \in Q_2, q_2 \in Q_2$
[/mm]
Aber das stimmt doch jetzt mathematisch nicht!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:27 Di 30.04.2013 | | Autor: | tobit09 |
> Meinst du mit Beispieldiagramme einen Automaten? Sowas hatte ich hier
> schon mal gemalt: http://s14.directupload.net/images/130427/v5iayo8b.jpg
Ich bin mir nicht sicher, ob es dir weiter hilft, wenn du zunächst separat Automaten [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] malst, die verschiedene Alphabete (z.B. [mm] $\Sigma_1=\{a,b\}$ [/mm] und [mm] $\Sigma_2=\{b,c\}$) [/mm] und jeweils mehrere Endzustände haben und danach daraus ein Zustandsdiagramm für [mm] $M_3$ [/mm] malst.
> Ich hab irgendwie ein Problem mit der mathematischen
> Ausdrucksweise. Dass ich mit diesen beiden
> Übergangsfunktionen die jetzt mittlerweile stimmen,
(Noch hast du keine Übergangsfunktion angegeben, sondern einen Teil der Definitionen getroffen, die für die Definition einer Übergangsfunktion nötig sind.)
> jeweils den Automat M1 und M2 beschreibe ist klar. Ich muss
> aber jetzt noch irgendwie einen mathematischen Ausdruck
> für mich an den Haaren herbeiziehen, der ausdrückt, dass
> ich von einem Zustand q1 von Automat M1 über ein [mm]\epsilon[/mm]
> zu einem Zustand q2 vom Automat M2 komme.
>
> Das ist jetzt mein Problem...
>
> Wenn mein Bildchen stimmt, denn bräucht ich ja irgendwie
> sowas:
>
> [mm]q_1 \overset{\epsilon}{\rightarrow} q_2[/mm] für [mm]q_1 \in Q_2, q_2 \in Q_2[/mm]
>
> Aber das stimmt doch jetzt mathematisch nicht!
Wenn [mm] $q_2$ [/mm] der einzige Nachfolgerzustand von [mm] $q_1$ [/mm] ist, der über ein [mm] $\varepsilon$ [/mm] erreicht werden kann, so entspricht dies der Festsetzung
[mm] $\delta_3((q_1,\varepsilon)):=\{q_2\}$.
[/mm]
Wenn man von allen Zuständen aus [mm] $Q_1$ [/mm] zu allen Zuständen aus [mm] $Q_2$ [/mm] mittels [mm] $\varepsilon$ [/mm] übergehen können soll, so entspricht dies der Festsetzung
[mm] $\delta_3((q,\varepsilon)):=Q_2$ [/mm] für alle [mm] $q\in Q_1$.
[/mm]
Wenn von einem Zustand $q$ aus z.B. gar kein [mm] $\varepsilon$-Übergang [/mm] vorgesehen ist, so entspricht dies der Festsetzung
[mm] $\delta_3((q,\varepsilon)):=\emptyset$ ($\emptyset=\{\}$ [/mm] bezeichnet die leere Menge)
[mm] $\delta_3((q,\varepsilon))$ [/mm] gibt immer genau die Menge der Nachfolgerzustände von q an, die man über ein [mm] $\varepsilon$ [/mm] erreichen können soll.
Um eine korrekte mathematische Wiedergabe zu finden, musst du zunächst genau wissen, von welchen Zuständen zu welchen Zuständen genau welche Übergänge möglich sein sollen.
[mm] $\varepsilon$-Übergänge [/mm] sind in der Tat nur von Zuständen von [mm] $M_1$ [/mm] zu Zuständen von [mm] $M_2$ [/mm] vorgesehen. Von Zuständen von [mm] $M_2$ [/mm] gehen gar keine [mm] $\varepsilon$-Übergänge [/mm] aus (beachte, dass [mm] $M_2$ [/mm] ja deterministisch war und somit keine [mm] $\varepsilon$-Übergänge [/mm] hatte). Also schon einmal
[mm] $\delta_3((q,\varepsilon)):=???$ [/mm] für alle [mm] $q\in Q_2$
[/mm]
Es muss [mm] $\varepsilon$-Übergänge [/mm] von Zuständen von [mm] $M_1$ [/mm] zu Zuständen von [mm] $M_2$ [/mm] geben, aber nicht von allen Zuständen [mm] $q_1\in Q_1$ [/mm] zu allen Zuständen [mm] $q_2\in Q_2$.
[/mm]
In deinem Bildchen geht z.B. richtigerweise kein [mm] $\varepsilon$-Pfeil [/mm] von [mm] $q_0$ [/mm] zu [mm] $q_2$ [/mm] oder von [mm] $q_1$ [/mm] zu [mm] $q_3$. [/mm] Was unterscheidet in diesem Beispiel [mm] $q_1$ [/mm] von [mm] $q_0$, [/mm] dass von [mm] $q_1$ [/mm] ein [mm] $\varepsilon$-Pfeil [/mm] ausgeht, aber von [mm] $q_0$ [/mm] nicht? Warum geht dieser [mm] $\varepsilon$-Pfeil [/mm] gerade zu [mm] $q_2$ [/mm] und nicht zu [mm] $q_3$?
[/mm]
Im allgemeinen Fall sollen also genau von welchen Zuständen zu welchen Zuständen [mm] $\varepsilon$-Übergänge [/mm] stattfinden?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:25 Mi 01.05.2013 | | Autor: | bandchef |
In deinem Bildchen geht z.B. richtigerweise kein [mm] $\varepsilon$-Pfeil [/mm] von [mm] $q_0$ [/mm] zu [mm] $q_2$ [/mm] oder von [mm] $q_1$ [/mm] zu [mm] $q_3$.
[/mm]
Ok. Dann hab ich wohl den Automaten für eine Konkatenation in diesem Beispiel richtig gemalt.
Was unterscheidet in diesem Beispiel [mm] $q_1$ [/mm] von [mm] $q_0$, [/mm] dass von [mm] $q_1$ [/mm] ein [mm] $\varepsilon$-Pfeil [/mm] ausgeht, aber von [mm] $q_0$ [/mm] nicht?
Der Unterschied in meinem Bildchen ist, dass [mm] $q_1$ [/mm] der akzeptierende Endzustand des DEAs M1 ist. Von [mm] $q_0$ [/mm] macht es auch keinen Sinn, da für die Konkatenation der Startzustand von [mm] $M_1$ [/mm] nicht gefragt ist.
Warum geht dieser [mm] $\varepsilon$-Pfeil [/mm] gerade zu [mm] $q_2$ [/mm] und nicht zu [mm] $q_3$? [/mm]
Weil der Endzustand von Automat [mm] $M_1$ [/mm] auf den Anfangszustand von DEA [mm] $M_2$ [/mm] gehen muss. Die beiden Automaten müssen ja hintereinander geschaltet werden um die Konkatenation abbilden zu können.
Im allgemeinen Fall sollen also genau von welchen Zuständen zu welchen Zuständen [mm] $\varepsilon$-Übergänge [/mm] stattfinden?
Da sollten dann wohl alle Endzustände von DEA [mm] $M_1$ [/mm] auf den einen Startzustand von DEA [mm] $M_2$ [/mm] mit einem [mm] $\epsilon$ [/mm] verbunden werden. Ich denke das ist dann wohl auch das was ich jetzt noch irgendwie mathematisch abbilden muss. Ich hab das jetzt mal so probiert:
$ [mm] M_1 [/mm] = [mm] (Q_1, \Sigma_1, \delta_1, q_0^1, F_1) [/mm] $
$ [mm] M_2 [/mm] = [mm] (Q_2, \Sigma_2, \delta_2, q_0^2, F_2) [/mm] $
$ [mm] M_3 [/mm] = [mm] (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \{\delta_1, \delta_2\}, \{q_0^1, q_0^2\}, F_1 \cup F_2) [/mm] $
$ [mm] \delta_3((q, \epsilon)) [/mm] := [mm] q_0^2$ [/mm] für $q [mm] \in F_1$
[/mm]
Hab ich jetzt hiermit die Aufgabe gelöst? Ich hab die DEAs [mm] $M_1$ [/mm] bis [mm] $M_3$ [/mm] formal definiert und hab für den DEA [mm] $M_3$ [/mm] auch die Übergangsfunktion [mm] $\delta_3$ [/mm] formal angegeben. Der Zustand q steht stellvertretend für alle akzeptierenden DEA [mm] $M_1$ [/mm] und dieser Zustand muss mit einem [mm] \epsilon [/mm] auf den Startzustand es DEAs [mm] $M_2$ [/mm] verbunden werden. Da es ja nur einen Startzustand gibt, hab ich nach dem "für" nur das q definiert, dass eben das q aus der Menge der akzeptierenden Zustände des DEA [mm] $M_1$, [/mm] also [mm] $F_1$ [/mm] kommt.
Ist das jetzt so richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:24 Do 02.05.2013 | | Autor: | tobit09 |
> In deinem Bildchen geht z.B. richtigerweise kein
> [mm]\varepsilon[/mm]-Pfeil von [mm]q_0[/mm] zu [mm]q_2[/mm] oder von [mm]q_1[/mm] zu [mm]q_3[/mm].
>
> Ok. Dann hab ich wohl den Automaten für eine Konkatenation
> in diesem Beispiel richtig gemalt.
Ja.
> Was unterscheidet in diesem Beispiel [mm]q_1[/mm] von [mm]q_0[/mm], dass von
> [mm]q_1[/mm] ein [mm]\varepsilon[/mm]-Pfeil ausgeht, aber von [mm]q_0[/mm] nicht?
>
> Der Unterschied in meinem Bildchen ist, dass [mm]q_1[/mm] der
> akzeptierende Endzustand des DEAs M1 ist.
Genau!
> Von [mm]q_0[/mm] macht es
> auch keinen Sinn, da für die Konkatenation der
> Startzustand von [mm]M_1[/mm] nicht gefragt ist.
Es sei denn, er ist gleichzeitig Endzustand.
> Warum geht dieser [mm]\varepsilon[/mm]-Pfeil gerade zu [mm]q_2[/mm] und nicht
> zu [mm]q_3[/mm]?
>
> Weil der Endzustand von Automat [mm]M_1[/mm] auf den Anfangszustand
> von DEA [mm]M_2[/mm] gehen muss. Die beiden Automaten müssen ja
> hintereinander geschaltet werden um die Konkatenation
> abbilden zu können.
Genau!
> Im allgemeinen Fall sollen also genau von welchen
> Zuständen zu welchen Zuständen [mm]\varepsilon[/mm]-Übergänge
> stattfinden?
>
> Da sollten dann wohl alle Endzustände von DEA [mm]M_1[/mm] auf den
> einen Startzustand von DEA [mm]M_2[/mm] mit einem [mm]\epsilon[/mm] verbunden
> werden.
Genau!
> Ich denke das ist dann wohl auch das was ich jetzt
> noch irgendwie mathematisch abbilden muss. Ich hab das
> jetzt mal so probiert:
>
> [mm]M_1 = (Q_1, \Sigma_1, \delta_1, q_0^1, F_1)[/mm]
> [mm]M_2 = (Q_2, \Sigma_2, \delta_2, q_0^2, F_2)[/mm]
> [mm]M_3 = (Q_1 \cup Q_2, \Sigma_1 \cup \Sigma_2, \{\delta_1, \delta_2\}, \{q_0^1, q_0^2\}, F_1 \cup F_2)[/mm]
Wir hatten schon einmal, dass Startzustand von [mm] $M_3$ [/mm] nur der Startzustand von [mm] $M_1$ [/mm] sein soll. Schließlich wollen wir ja mit einem Wort aus [mm] $L_1$ [/mm] starten. Ebenso sollen nur die Endzustände von [mm] $M_2$ [/mm] Endzustände von [mm] $M_3$ [/mm] werden.
[mm] $\{\delta_1,\delta_2\}$ [/mm] ist eine Menge von zwei Übergangsfunktionen, keine Übergangsfunktion für [mm] $M_3$. [/mm] Wir hatten schon einmal, was für eine Abbildung [mm] $\delta_3$ [/mm] sein muss.
> [mm]\delta_3((q, \epsilon)) := q_0^2[/mm] für [mm]q \in F_1[/mm]
Mit Mengenklammern um [mm] $q_0^2$ [/mm] herum passt es!
Dies ist aber nur ein kleiner Ausschnitt der Übergangsfunktion von [mm] $M_3$. [/mm] Wir hatten schon einmal, für welche Paare $(q,a)$ jeweils [mm] $\delta_3((q,a))$ [/mm] festzulegen ist.
> Hab ich jetzt hiermit die Aufgabe gelöst? Ich hab die DEAs
> [mm]M_1[/mm] bis [mm]M_3[/mm] formal definiert und hab für den DEA [mm]M_3[/mm]
[mm] $\varepsilon$-NEA $M_3$ [/mm] meinst du.
> auch
> die Übergangsfunktion [mm]\delta_3[/mm] formal angegeben.
Nein, das hast du nur teilweise.
> Der
> Zustand q steht stellvertretend für alle akzeptierenden
> DEA [mm]M_1[/mm] und dieser Zustand muss mit einem [mm]\epsilon[/mm] auf den
> Startzustand es DEAs [mm]M_2[/mm] verbunden werden. Da es ja nur
> einen Startzustand gibt, hab ich nach dem "für" nur das q
> definiert, dass eben das q aus der Menge der akzeptierenden
> Zustände des DEA [mm]M_1[/mm], also [mm]F_1[/mm] kommt.
Das wichtige ist: Für ALLE [mm] $q\in F_1$ [/mm] hast du diese Festlegung getroffen.
> Ist das jetzt so richtig?
Teilweise.
Denke daran: Wenn aus einem Zustand $q$ von [mm] $M_3$ [/mm] kein $a$-Übergang zu einem anderen Zustand vorgesehen ist, so musst du eben
[mm] $\delta_3((q,a)):=\{\}$
[/mm]
festlegen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:29 Fr 03.05.2013 | | Autor: | bandchef |
Danke für deine ausgiebige und tolle Hilfe! 
|
|
|
|
