Grundl. Endl. Autom. (3) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 17:11 Mo 20.02.2006 | | Autor: | mathiash |
| Aufgabe | (1) Definiere zu einem NEA A die [mm] \omega-Sprache L^{\omega}(A).
[/mm]
(2) Definiere die Begriffe TEA und MEA und zu gegebenem TEA A und MEA B
die Sprachen [mm] L^{\omega}(A) [/mm] und [mm] L^{\omega}(B).
[/mm]
(3) Zeige: Zu jedem MEA A gibt es einen MEA B mit [mm] L^{\omega}(B)=\Sigma^{\omega}\setminus L^{\omega}(A).
[/mm]
(4) Zeige: Falls [mm] B_1 [/mm] und [mm] B_2 [/mm] TEA sind, so gibt es einen TEA B mit
[mm] L^{\omega}(B)=L^{\omega}(B_1)\cup L^{\omega}(B_2).
[/mm]
(5) Zeige: Zu jedem TEA B gibt es einen MEA A mit [mm] L^{\omega}(A)=L^{\omega}(B).
[/mm]
(6) Zeige: Zu jedem MEA A gibt es einen TEA B mit [mm] L^{\omega}(B)=L^{\omega}(A). [/mm] |
Hallo zusammen,
dies ist ein kleines Abendprogramm für ganz spezielle Nachtschwärmer.
Viel Spass,
Mathias
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:23 Di 21.02.2006 | | Autor: | Bastiane |
Lieber Mathias!
Da ich gerade an den Berechenbarkeitssachen mal wieder verzweifelt bin, habe ich mir den Rest nicht mehr angeguckt. Hier jetzt also ohne es mir nochmal angeschaut zu haben:
> (1) Definiere zu einem NEA A die [mm]\omega-Sprache L^{\omega}(A).[/mm]
[mm] L^{\omega}(A)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}
[/mm]
wobei eine Berechnung [mm] \rho_v [/mm] akzeptierend heißt, wenn gilt [mm] In(\rho_v)\cap F\not=\emptyset
[/mm]
Sagt man das so?
> (2) Definiere die Begriffe TEA und MEA und zu gegebenem TEA
> A und MEA B
> die Sprachen [mm]L^{\omega}(A)[/mm] und [mm]L^{\omega}(B).[/mm]
TEA [mm] \mathcal{A}=(S,M,s_0,T)
[/mm]
mit [mm] S,M,s_0 [/mm] wie bei EA und [mm] T\subset(\mathcal{P}(S)\times\mathcal{P}(S))^m [/mm] mit m Größe der Tafel, meist geschrieben als: [mm] T=(L_i,U_i) [/mm] für [mm] 1\le i\le [/mm] m
MEA [mm] \mathcal{B}=(S,M,s_0,F)
[/mm]
mit [mm] S,M,s_0 [/mm] wie oben und [mm] F\subseteq\mathcal{P}(S)
[/mm]
[mm] L^{\omega}(A)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}
[/mm]
mit [mm] \rho_v [/mm] eine akzeptierende [mm] \omega\mbox{-Berechnung über v} [/mm] wenn gilt: [mm] In(\rho_v)\in [/mm] F
[mm] L^{\omega}(B)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}
[/mm]
mit [mm] \rho_v [/mm] eine akzeptierende [mm] \omega\mbox{-Berechnung über v} [/mm] wenn gilt: [mm] In(\rho_v)\cap L_i=\emptyset [/mm] und [mm] In(\rho_v)\cap U_i\not=\emptyset \forall [/mm] i
> (3) Zeige: Zu jedem MEA A gibt es einen MEA B mit
> [mm]L^{\omega}(B)=\Sigma^{\omega}\setminus L^{\omega}(A).[/mm]
Sei A ein MEA wie oben definiert, dann konstruiere MEA B: [mm] B=(S,M,s_0,\mathcal{P}(S)\backslash [/mm] F)
Ich glaub', das war so einfach, oder?
> (4) Zeige: Falls [mm]B_1[/mm] und [mm]B_2[/mm] TEA sind, so gibt es einen TEA
> B mit
> [mm]L^{\omega}(B)=L^{\omega}(B_1)\cup L^{\omega}(B_2).[/mm]
Seien [mm] B_i=(S_i,M_i,s_{0,i},T_i) [/mm] zwei TEAs, dann konstruiere B sodass [mm] L^{\omega}(B)=L^{\omega}(B_1)\cup L^{\omega}(B_2):
[/mm]
[mm] S=S_1\times S_2
[/mm]
[mm] M(s,\sigma)=(M_1(s,\sigma),M_2(s,\sigma))
[/mm]
[mm] s_0=(s_{0,1},s_{0,2})
[/mm]
[mm] B=\{(L_{1i}\times S_2,U_{1i}\times S_2)|(L_{1i},U_{1i})\in T_1\}\cup\{(S_1\times L_{2i}, S_1\times L_{2i})|(L_{2i},U_{2i})\in T_2\}
[/mm]
> (5) Zeige: Zu jedem TEA B gibt es einen MEA A mit
> [mm]L^{\omega}(A)=L^{\omega}(B).[/mm]
>
> (6) Zeige: Zu jedem MEA A gibt es einen TEA B mit
> [mm]L^{\omega}(B)=L^{\omega}(A).[/mm]
> Hallo zusammen,
>
> dies ist ein kleines Abendprogramm für ganz spezielle
> Nachtschwärmer.
Den Rest mache ich jetzt nicht mehr - ich muss ja noch die Baier-Sachen lesen... Das ist noch nachtschwärmerisch genug...
Bis bald
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
P.S.: Hoffentlich habe ich mich hier nirgendwo vertippt... Aber ich muss das alles wohl doch noch zwanzigtausend mal machen, bis ich das wirklich kann...
|
|
|
| |
|
Liebe Christiane,
zu den 20.000: Jetzt nur noch 19.999 mal ... 
> > (1) Definiere zu einem NEA A die [mm]\omega-Sprache L^{\omega}(A).[/mm]
>
> [mm]L^{\omega}(A)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}[/mm]
>
> wobei eine Berechnung [mm]\rho_v[/mm] akzeptierend heißt, wenn gilt
> [mm]In(\rho_v)\cap F\not=\emptyset[/mm]
> Sagt man das so?
Ja, alles ok.
>
> > (2) Definiere die Begriffe TEA und MEA und zu gegebenem TEA
> > A und MEA B
> > die Sprachen [mm]L^{\omega}(A)[/mm] und [mm]L^{\omega}(B).[/mm]
>
> TEA [mm]\mathcal{A}=(S,M,s_0,T)[/mm]
> mit [mm]S,M,s_0[/mm] wie bei EA und
> [mm]T\subset(\mathcal{P}(S)\times\mathcal{P}(S))^m[/mm] mit m Größe
> der Tafel, meist geschrieben als: [mm]T=(L_i,U_i)[/mm] für [mm]1\le i\le[/mm]
> m
>
Fast perfekt:
[mm] T=\{(L_i,U_i)\: |\: i=1,\ldots , m\} [/mm] (eine Menge von Paaren [mm] (L_i,U_i))
[/mm]
> MEA [mm]\mathcal{B}=(S,M,s_0,F)[/mm]
> mit [mm]S,M,s_0[/mm] wie oben und [mm]F\subseteq\mathcal{P}(S)[/mm]
>
> [mm]L^{\omega}(A)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}[/mm]
>
> mit [mm]\rho_v[/mm] eine akzeptierende [mm]\omega\mbox{-Berechnung über v}[/mm]
> wenn gilt: [mm]In(\rho_v)\in[/mm] F
>
Ja, richtig.
> [mm]L^{\omega}(B)=\{v:\omega\to\summe|\exists \mbox{ akzeptierende } \omega\mbox{-Berechnung über v}\}[/mm]
>
> mit [mm]\rho_v[/mm] eine akzeptierende [mm]\omega\mbox{-Berechnung über v}[/mm]
> wenn gilt: [mm]In(\rho_v)\cap L_i=\emptyset[/mm] und [mm]In(\rho_v)\cap U_i\not=\emptyset \forall[/mm]
> i
>
Nein. Sondern: Es gibt ein [mm] i\in\{1,\ldots m\} [/mm] so dass ....... (nicht notwendig fuer alle !!!!)
> > (3) Zeige: Zu jedem MEA A gibt es einen MEA B mit
> > [mm]L^{\omega}(B)=\Sigma^{\omega}\setminus L^{\omega}(A).[/mm]
>
> Sei A ein MEA wie oben definiert, dann konstruiere MEA B:
> [mm]B=(S,M,s_0,\mathcal{P}(S)\backslash[/mm] F)
>
> Ich glaub', das war so einfach, oder?
>
Ja, absolut richtig !
> > (4) Zeige: Falls [mm]B_1[/mm] und [mm]B_2[/mm] TEA sind, so gibt es einen TEA
> > B mit
> > [mm]L^{\omega}(B)=L^{\omega}(B_1)\cup L^{\omega}(B_2).[/mm]
>
> Seien [mm]B_i=(S_i,M_i,s_{0,i},T_i)[/mm] zwei TEAs, dann konstruiere
> B sodass [mm]L^{\omega}(B)=L^{\omega}(B_1)\cup L^{\omega}(B_2):[/mm]
>
> [mm]S=S_1\times S_2[/mm]
> [mm]M(s,\sigma)=(M_1(s,\sigma),M_2(s,\sigma))[/mm]
> [mm]s_0=(s_{0,1},s_{0,2})[/mm]
> [mm]B=\{(L_{1i}\times S_2,U_{1i}\times S_2)|(L_{1i},U_{1i})\in T_1\}\cup\{(S_1\times L_{2i}, S_1\times L_{2i})|(L_{2i},U_{2i})\in T_2\}[/mm]
>
Ja, ganz genau.
> > (5) Zeige: Zu jedem TEA B gibt es einen MEA A mit
> > [mm]L^{\omega}(A)=L^{\omega}(B).[/mm]
> >
> > (6) Zeige: Zu jedem MEA A gibt es einen TEA B mit
> > [mm]L^{\omega}(B)=L^{\omega}(A).[/mm]
> > Hallo zusammen,
> >
> > dies ist ein kleines Abendprogramm für ganz spezielle
> > Nachtschwärmer.
>
> Den Rest mache ich jetzt nicht mehr - ich muss ja noch die
> Baier-Sachen lesen... Das ist noch nachtschwärmerisch
> genug...
>
Also das hier war von nach 23 Uhr, dann hast Du ja tatsaechlich noch einiges vor.
> Bis bald
> Bastiane
>
>
> P.S.: Hoffentlich habe ich mich hier nirgendwo vertippt...
> Aber ich muss das alles wohl doch noch zwanzigtausend mal
> machen, bis ich das wirklich kann...
>
Dazu s.o.
Klappt doch aber alles schon ziemlich gut.
Bis bald,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:42 Mi 22.02.2006 | | Autor: | Bastiane |
Lieber Mathias!
> zu den 20.000: Jetzt nur noch 19.999 mal ...
Oje - willst du die alle mitzählen? Dann muss ich die Prüfung aber verschieben... Übrigens glaube ich, dass du mich doch mehr als die Hälfte das abfragen musst, irgendwie trödel ich dabei alleine doch immer rum. Ich weiß gar nicht, warum...
> > > (2) Definiere die Begriffe TEA und MEA und zu gegebenem TEA
> > > A und MEA B
> > > die Sprachen [mm]L^{\omega}(A)[/mm] und [mm]L^{\omega}(B).[/mm]
> >
> > TEA [mm]\mathcal{A}=(S,M,s_0,T)[/mm]
> > mit [mm]S,M,s_0[/mm] wie bei EA und
> > [mm]T\subset(\mathcal{P}(S)\times\mathcal{P}(S))^m[/mm] mit m Größe
> > der Tafel, meist geschrieben als: [mm]T=(L_i,U_i)[/mm] für [mm]1\le i\le[/mm]
> > m
> >
>
> Fast perfekt:
> [mm]T=\{(L_i,U_i)\: |\: i=1,\ldots , m\}[/mm] (eine Menge
> von Paaren [mm](L_i,U_i))[/mm]
Ohja - das macht ja sonst gar keinen Sinn. Aber den angeblichen Fehler hast du hier wohl übersehen, aber im Skript steht wirklich: [mm] T\subseteq(\mathcal{P}(S)\times\mathcal{P}(S))^m...
[/mm]
> > > (5) Zeige: Zu jedem TEA B gibt es einen MEA A mit
> > > [mm]L^{\omega}(A)=L^{\omega}(B).[/mm]
Das war ja die einfachere Richtung... 
Gegeben sei der TEA [mm] B=(S,M,s_0,T) [/mm] und gesucht der äquivalente MEA [mm] A=(S',M',s_0',F'). [/mm] Das mache ich so:
S'=S
M'=M (kann ich das in Kurzform so schreiben?)
[mm] s_0'=s_0
[/mm]
[mm] F'=\bigcup_{i=1}^m\{Q|Q\subseteq S', Q\cap L_i=\emptyset \mbox{ und } Q\cap U_i\not=\emptyset\}
[/mm]
Wir hatten es vorhin etwas anders aufgeschrieben, aber so müsste es doch auch stimmen!?
> > > (6) Zeige: Zu jedem MEA A gibt es einen TEA B mit
> > > [mm]L^{\omega}(B)=L^{\omega}(A).[/mm]
Na, das kann ich vielleicht nächste Woche dann...
Viele Grüße
Bastiane
|
|
|
| |
|
Hallo und guten Morgen, Bastiane !
>
> > > > (2) Definiere die Begriffe TEA und MEA und zu gegebenem TEA
> > > > A und MEA B
> > > > die Sprachen [mm]L^{\omega}(A)[/mm] und
> [mm]L^{\omega}(B).[/mm]
> > >
> > > TEA [mm]\mathcal{A}=(S,M,s_0,T)[/mm]
> > > mit [mm]S,M,s_0[/mm] wie bei EA und
> > > [mm]T\subset(\mathcal{P}(S)\times\mathcal{P}(S))^m[/mm] mit m Größe
> > > der Tafel, meist geschrieben als: [mm]T=(L_i,U_i)[/mm] für [mm]1\le i\le[/mm]
> > > m
> > >
> >
> > Fast perfekt:
> > [mm]T=\{(L_i,U_i)\: |\: i=1,\ldots , m\}[/mm] (eine Menge
> > von Paaren [mm](L_i,U_i))[/mm]
>
> Ohja - das macht ja sonst gar keinen Sinn. Aber den
> angeblichen Fehler hast du hier wohl übersehen, aber im
> Skript steht wirklich:
> [mm]T\subseteq(\mathcal{P}(S)\times\mathcal{P}(S))^m...[/mm]
>
Ich sollte mal eine Fehlerliste anlegen, die waere nicht ganz kurz.
> > > > (5) Zeige: Zu jedem TEA B gibt es einen MEA A mit
> > > > [mm]L^{\omega}(A)=L^{\omega}(B).[/mm]
>
> Das war ja die einfachere Richtung...
Das sie Dir einfach vorkommt, zeigt nur, wie gut Du bist.
> Gegeben sei der TEA [mm]B=(S,M,s_0,T)[/mm] und gesucht der
> äquivalente MEA [mm]A=(S',M',s_0',F').[/mm] Das mache ich so:
> S'=S
> M'=M (kann ich das in Kurzform so schreiben?)
> [mm]s_0'=s_0[/mm]
> [mm]F'=\bigcup_{i=1}^m\{Q|Q\subseteq S', Q\cap L_i=\emptyset \mbox{ und } Q\cap U_i\not=\emptyset\}[/mm]
>
> Wir hatten es vorhin etwas anders aufgeschrieben, aber so
> müsste es doch auch stimmen!?
>
Joah !
> > > > (6) Zeige: Zu jedem MEA A gibt es einen TEA B mit
> > > > [mm]L^{\omega}(B)=L^{\omega}(A).[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Na, das kann ich vielleicht nächste Woche dann...
>
Stichwort: Fuer jeden Macro-Endzustand einen Zaehler, also
S_{neu} = P(Q_1)\times \ldots \times P(Q_k}\: \times\: S
Kannst Du mit diesem Hinweis aus dem Gedaechtnis den Rest konstruieren ?
> Viele Grüße
> Bastiane
>
>
Herzlichst,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:58 Do 23.02.2006 | | Autor: | Bastiane |
> Hallo und guten Morgen, Bastiane !
Gleichfalls - auch wenn dies dann wohl schon der nächste Morgen ist...
> > Ohja - das macht ja sonst gar keinen Sinn. Aber den
> > angeblichen Fehler hast du hier wohl übersehen, aber im
> > Skript steht wirklich:
> > [mm]T\subseteq(\mathcal{P}(S)\times\mathcal{P}(S))^m...[/mm]
> >
>
> Ich sollte mal eine Fehlerliste anlegen, die waere nicht
> ganz kurz.
Das heißt, das m da ist wirklich zu viel, ja? Soll ich das obige denn überhaupt schreiben oder lieber einfach nur [mm] T=\{(L_i,U_i)|L_i,U_i\subseteq S\} [/mm] oder so wie du es geschrieben hattest...
> > > > > (5) Zeige: Zu jedem TEA B gibt es einen MEA A mit
> > > > > [mm]L^{\omega}(A)=L^{\omega}(B).[/mm]
> >
> > Das war ja die einfachere Richtung...
>
> Das sie Dir einfach vorkommt, zeigt nur, wie gut Du bist.
Ich sagte nicht "einfach", sondern nur "einfacher"! Aber nach zehnmal machen, finde ichs wohl dann auch fast schon "einfach".
> > Wir hatten es vorhin etwas anders aufgeschrieben, aber so
> > müsste es doch auch stimmen!?
> >
>
> Joah !
![[grins]](/images/smileys/grins.gif "[grins]") ![[biggrin]](/images/smileys/biggrin.gif "[biggrin]")
> > > > > (6) Zeige: Zu jedem MEA A gibt es einen TEA B mit
> > > > > [mm]L^{\omega}(B)=L^{\omega}(A).[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}"
> müssen immer paarweise auftreten, es wurde aber ein Teil
> ohne Entsprechung gefunden (siehe rote Markierung)
>
>
> >
> > Na, das kann ich vielleicht nächste Woche dann...
> >
>
> Stichwort: Fuer jeden Macro-Endzustand einen Zaehler, also
>
> S_{neu} = P(Q_1)\times \ldots \times P(Q_k}\: \times\: S
>
> Kannst Du mit diesem Hinweis aus dem Gedaechtnis den Rest
> konstruieren ?
Vielleicht, aber heute nacht nicht mehr. ![[baeh]](/images/smileys/baeh.gif "[baeh]") Übrigens siehst du hier mal, wofür die Vorschau sinnvoll wäre.
> Herzlichst,
Da fehlt wohl noch der passende Smiliey, was?
Bis dann
Christiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:10 Fr 24.02.2006 | | Autor: | mathiash |
Liebe Bastiane,
Vorschau ist doch was fuer Mädchen, richtig ? ![[huepf]](/images/smileys/huepf.gif "[huepf]")
Herzliche Grüsse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:08 Di 28.02.2006 | | Autor: | Marc |
Hallo zusammen!
> Übrigens: wieso schreibst du immer noch kein "ü" aber ein
> "ä"? Ist das etwa auf der Tastatur drauf?
Umlaute lassen sich hier im Forum auf Gnometechs Wunsch hin auch in LaTeX-Notation erreichen, allerdings mit einem vorangestellten \
ä
ö
ü
Ä
Ö
Ü
ß
(siehe Quelltext)
# Marc
|
|
|
|
