Grundl. Endliche Automaten (1) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 17:22 Do 16.02.2006 | | Autor: | mathiash |
| Aufgabe | (1) Definiere die Begriffe DEA (deterministischer endlicher Automat, auch zT EA genannt) und NEA (nichtdeterministischer endlicher Automat.
(2) Definiere die Menge [mm] \{0,1\}^{\star} [/mm] sowie den Begriff der Berechnung eines DEA/NEA über einer Eingabe [mm] v\in\{0,1\}^{\star}.
[/mm]
(3) Definiere die von einem DEA/NEA A akzeptierte Sprache L(A).
(4) Zeige: Zu jedem NEA A gibt es einen äquivalenten DEA B, d.h. mit L(A)=L(B).
(5) Definiere die Klasse [mm] REG_{\{0,1\}} [/mm] der regulären Sprachen über dem Alphabet [mm] \{0,1\}.
[/mm]
(6) Zeige durch Konstruktion geeigneter NEA, dass [mm] REG_{\{0,1\}} [/mm] abgeschlossen unter Komplement, Schnitt, Vereinigung und symmetrischer Differenz ist.
(7) Zeige: Es gibt Sprachen [mm] L\subseteq\{0,1\}^{\star}, [/mm] die durch keinen NEA erkannt werden (also nicht-reguläre Sprachen). |
Hallo (zusammen),
diese Fragen sind offensichtlich speziell fuer diejenige(n) zusammengestellt, die sich
auf Pruefungen ueber dieses Thema gezielt vorbereiten.
Frag(t) ruhig nach, man sollte bei allen Schwierigkeiten Chancen nicht ungenutzt lassen.
Mathias
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:20 Do 16.02.2006 | | Autor: | Bastiane |
Hallo Mathias!
Sind das nicht ein bisschen viele Aufgaben auf einmal? 
> (1) Definiere die Begriffe DEA (deterministischer endlicher
> Automat, auch zT EA genannt) und NEA
> (nichtdeterministischer endlicher Automat.
Ein EA über dem Alphabet [mm] \summe [/mm] ist ein Vier-Tupel [mm] \cal{A} [/mm] = [mm] (S,M,s_0,F) [/mm] wobei:
S eine endliche Menge von Zuständen,
[mm] M:S\times\summe\to [/mm] S die Übergangsfunktion,
[mm] $s_0\in [/mm] S$ der Startzustand und
[mm] $F\subseteq [/mm] S$ die Menge der Endzustände
sind.
Ein NEA über dem Alphabet [mm] \summe [/mm] ist ein Vier-Tupel [mm] \cal{A} [/mm] = [mm] (S,M,S_0,F) [/mm] wobei:
S eine endliche Menge von Zuständen,
[mm] M:S\times\summe\to\cal{P}(S) [/mm] die Übergangsfunktion,
[mm] $S_0\in \cal{P}(S)$ [/mm] die Menge der Startzustände und
[mm] $F\subseteq [/mm] S$ die Menge der Endzustände
sind.
> (2) Definiere die Menge [mm]\{0,1\}^{\star}[/mm] sowie den Begriff
> der Berechnung eines DEA/NEA über einer Eingabe
> [mm]v\in\{0,1\}^{\star}.[/mm]
[mm] \{0,1\}^{\star}=\bigcup_{n\in\N_0}\{0,1\}^n [/mm] ? Meintest du nicht, da gäbe es noch eine bessere Variante? Aber diese hier habe ich im Skript gefunden...
Die Berechnung kann ich nicht in Kurzform. Im Skript wird angefangen mit v: n [mm] \to\summe [/mm] usw.. Aber kann man das v nicht irgendwie weglassen?
> (3) Definiere die von einem DEA/NEA A akzeptierte
> Sprache L(A).
[mm] L(A)=\{v|\exists\mbox{akzeptierende Berechnung }\rho_v \mbox{ über v}\}
[/mm]
> (4) Zeige: Zu jedem NEA A gibt es einen äquivalenten DEA
> B, d.h. mit L(A)=L(B).
Das macht man mit der Potenzautomatenkonstruktion...
> (5) Definiere die Klasse [mm]REG_{\{0,1\}}[/mm] der regulären
> Sprachen über dem Alphabet [mm]\{0,1\}.[/mm]
[mm] REG_{\{0,1\}}=\{A|\exists NEA \cal{A} mit A=L(\cal{A})\}
[/mm]
Ha, jetzt weiß ich auch, wo die komischen Zeichen aus dem Skript herkamen... Aber was bitte schön ist hier dran falsch? Es scheint irgendwie an "cal" zu liegen, damit hatte ich schön öfter Probleme...
> (6) Zeige durch Konstruktion geeigneter NEA, dass
> [mm]REG_{\{0,1\}}[/mm] abgeschlossen unter Komplement, Schnitt,
> Vereinigung und symmetrischer Differenz ist.
Sei [mm] A=(S,M,s_0,F) [/mm] der zum gegebenen NEA zugehörige EA (Potenzautomat). Dann konstruiere ich für das Komplement einen Automaten A', sodass [mm] \overline{L(A)}=L(A'):
[/mm]
[mm] A'=(S,M,s_0,S\backslash [/mm] F) mit [mm] S,M,s_0,F [/mm] wie bei A.
Nun habe ich im Kopf, dass nur entweder Schnitt oder Vereinigung einfach waren, würde aber beides folgendermaßen machen:
[mm] A=(S_1,M_1,S_{0,1},F) [/mm] und [mm] B=(S_2,M_2,S_{0,2},F) [/mm] gegeben
C mit [mm] L(C)=L(A)\cap [/mm] L(B):
[mm] C=(S_1\times S_2, [/mm] M', [mm] (s_{0,1},s_{0,2}),F') [/mm] mit [mm] s_{0,i}\in S_{0,i} [/mm] für i=1,2
[mm] M'((s_1,s_2),\sigma)=(M_1(s_1,\sigma),M_2(s_2,\sigma))
[/mm]
[mm] F'=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\in F_2\}
[/mm]
und für die Vereinigung dann alles genauso, nur als Endzustandsmenge:
[mm] F''=\{(s_1,s_2)|s_1\in F_1 \vee s_2\in F_2\}
[/mm]
Und für die symmetrische Differenz:
[mm] F'''=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\notin F_2\vee s_1\notin F_1 \wedge s_2\in F_2\}
[/mm]
Gibt es da irgendein Problem oder war das nur bei [mm] \omega-Sprachen [/mm] problematisch? Und geht das hier eigentlich mit einem NEA oder muss ich vorher einen DEA draus machen?
> (7) Zeige: Es gibt Sprachen [mm]L\subseteq\{0,1\}^{\star},[/mm] die
> durch keinen NEA erkannt werden (also nicht-reguläre
> Sprachen).
Wie macht man das? Hast du ein Stichwort?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
> Hallo Mathias!
>
> Sind das nicht ein bisschen viele Aufgaben auf einmal?
Das ist erst der Anfang. Wir sind noch in der Umkleide, das Aufwaermtraining
kommt noch.
>
> > (1) Definiere die Begriffe DEA (deterministischer endlicher
> > Automat, auch zT EA genannt) und NEA
> > (nichtdeterministischer endlicher Automat.
>
> Ein EA über dem Alphabet [mm]\summe[/mm] ist ein Vier-Tupel [mm]\cal{A}[/mm]
> = [mm](S,M,s_0,F)[/mm] wobei:
> S eine endliche Menge von Zuständen,
> [mm]M:S\times\summe\to[/mm] S die Übergangsfunktion,
> [mm]s_0\in S[/mm] der Startzustand und
> [mm]F\subseteq S[/mm] die Menge der Endzustände
> sind.
>
> Ein NEA über dem Alphabet [mm]\summe[/mm] ist ein Vier-Tupel [mm]\cal{A}[/mm]
> = [mm](S,M,S_0,F)[/mm] wobei:
> S eine endliche Menge von Zuständen,
> [mm]M:S\times\summe\to\cal{P}(S)[/mm] die Übergangsfunktion,
> [mm]S_0\in \cal{P}(S)[/mm] die Menge der Startzustände und
> [mm]F\subseteq S[/mm] die Menge der Endzustände
> sind.
>
Ok.
> > (2) Definiere die Menge [mm]\{0,1\}^{\star}[/mm] sowie den Begriff
> > der Berechnung eines DEA/NEA über einer Eingabe
> > [mm]v\in\{0,1\}^{\star}.[/mm]
>
> [mm]\{0,1\}^{\star}=\bigcup_{n\in\N_0}\{0,1\}^n[/mm] ? Meintest du
> nicht, da gäbe es noch eine bessere Variante? Aber diese
> hier habe ich im Skript gefunden...
>
[mm] \Sigma^*=\{v\: |\: \exists n\in\omega\: \: v\colon n\to\Sigma\}
[/mm]
wobei [mm] n=\{0,1,\ldots , n-1\}
[/mm]
(mengentheor. Konstruktion der natuerlichen Zahlen).
Strings sind also Abbildungen.
> Die Berechnung kann ich nicht in Kurzform. Im Skript wird
> angefangen mit v: n [mm]\to\summe[/mm] usw.. Aber kann man das v
> nicht irgendwie weglassen?
>
Nö, denn v ist die Eingabe, und ohne Eingabe berechnet der Automat auch nichts.
> > (3) Definiere die von einem DEA/NEA A akzeptierte
> > Sprache L(A).
>
> [mm]L(A)=\{v|\exists\mbox{akzeptierende Berechnung }\rho_v \mbox{ über v}\}[/mm]
>
Jou. Oder besser: Joah !
> > (4) Zeige: Zu jedem NEA A gibt es einen äquivalenten DEA
> > B, d.h. mit L(A)=L(B).
>
> Das macht man mit der Potenzautomatenkonstruktion...
>
Ja und, wo steht die hier ? Die musst Du sofort und zuegig hinschreiben koennen.
> > (5) Definiere die Klasse [mm]REG_{\{0,1\}}[/mm] der regulären
> > Sprachen über dem Alphabet [mm]\{0,1\}.[/mm]
>
> [mm]REG_{\{0,1\}}=\{A|\exists NEA \cal{A} mit A=L(\cal{A})\}[/mm]
>
Probier mal [mm] {\cal A} [/mm] ,
das war die Loesung fuers Skript.
Inhaltlich ok.
> Ha, jetzt weiß ich auch, wo die komischen Zeichen aus dem
> Skript herkamen... Aber was bitte schön ist hier dran
> falsch? Es scheint irgendwie an "cal" zu liegen, damit
> hatte ich schön öfter Probleme...
>
> > (6) Zeige durch Konstruktion geeigneter NEA, dass
> > [mm]REG_{\{0,1\}}[/mm] abgeschlossen unter Komplement, Schnitt,
> > Vereinigung und symmetrischer Differenz ist.
>
> Sei [mm]A=(S,M,s_0,F)[/mm] der zum gegebenen NEA zugehörige EA
> (Potenzautomat). Dann konstruiere ich für das Komplement
> einen Automaten A', sodass [mm]\overline{L(A)}=L(A'):[/mm]
> [mm]A'=(S,M,s_0,S\backslash[/mm] F) mit [mm]S,M,s_0,F[/mm] wie bei A
Ok.
> Nun habe ich im Kopf, dass nur entweder Schnitt oder
> Vereinigung einfach waren, würde aber beides folgendermaßen
> machen:
> [mm]A=(S_1,M_1,S_{0,1},F)[/mm] und [mm]B=(S_2,M_2,S_{0,2},F)[/mm] gegeben
> C mit [mm]L(C)=L(A)\cap[/mm] L(B):
> [mm]C=(S_1\times S_2,[/mm] M', [mm](s_{0,1},s_{0,2}),F')[/mm] mit [mm]s_{0,i}\in S_{0,i}[/mm]
> für i=1,2
> [mm]M'((s_1,s_2),\sigma)=(M_1(s_1,\sigma),M_2(s_2,\sigma))[/mm]
> [mm]F'=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\in F_2\}[/mm]
> und für die
> Vereinigung dann alles genauso, nur als Endzustandsmenge:
> [mm]F''=\{(s_1,s_2)|s_1\in F_1 \vee s_2\in F_2\}[/mm]
>
Beides ok fuer EA. Ja, was funktioniert denn nun fuer NEA nicht ???
Nun, fuer NEA solltest Du zuerst die Uebergangsfunktion anders definieren, gell ?
Dann schauen wir weiter.
> Und für die symmetrische Differenz:
> [mm]F'''=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\notin F_2\vee s_1\notin F_1 \wedge s_2\in F_2\}[/mm]
>
> Gibt es da irgendein Problem oder war das nur bei
> [mm]\omega-Sprachen[/mm] problematisch? Und geht das hier eigentlich
> mit einem NEA oder muss ich vorher einen DEA draus machen?
>
Ueberleg doch mal: Wenn Du ein Paar von Berechnungen der beiden NEA hast und davon eine akz. und
die andere verwirft, dann ist das doch sicherlich Garant dafuer, dass der String in der einen Sprache - korrespondierend zur akz. ber. - drin liegt. Aber kann man auch mit Sicherheit sagen, dass er in der anderen nicht liegt ?
> > (7) Zeige: Es gibt Sprachen [mm]L\subseteq\{0,1\}^{\star},[/mm] die
> > durch keinen NEA erkannt werden (also nicht-reguläre
> > Sprachen).
>
> Wie macht man das? Hast du ein Stichwort?
>
Viele. Und andererseits Sprachlosigkeit. Aber zu den Stichwoertern was auf anderem Wege.
> Viele Grüße
> Bastiane
>
>
Viele Gruesse,
Mathias
PS Was ist dem Strang zu RE und mit dem zur Berechenbarkeit ?
Und wie lang hast Du fuer diese Aufgaben hier gebraucht ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:09 Sa 18.02.2006 | | Autor: | Bastiane |
Lieber Mathias!
Bin gerade die Aufgaben nochmal durchgegangen. 
> > > (2) Definiere die Menge [mm]\{0,1\}^{\star}[/mm] sowie den Begriff
> > > der Berechnung eines DEA/NEA über einer Eingabe
> > > [mm]v\in\{0,1\}^{\star}.[/mm]
> > Die Berechnung kann ich nicht in Kurzform. Im Skript wird
> > angefangen mit v: n [mm]\to\summe[/mm] usw.. Aber kann man das v
> > nicht irgendwie weglassen?
> >
>
> Nö, denn v ist die Eingabe, und ohne Eingabe berechnet der
> Automat auch nichts.
Ja, eigentlich klar. ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]") War wohl vor allem zu faul zum Schreiben gestern...
Also, sei [mm] \cal{A} [/mm] ein DEA und [mm] v:n\to\summe [/mm] ein Wort, dann heißt die Abbildung [mm] \rho_v:n+1\to [/mm] S mit
(i) [mm] \rho_v(0)=s_0 [/mm] und
(ii) [mm] \rho_v(i+1)=M(\rho_v(i),v(i)) [/mm] für [mm] i\in [/mm] n
die [mm] \cal{A}\mbox{-Berechnung über v}
[/mm]
Bei einem NEA ändert sich hierbei nur folgendes:
(i) [mm] \rho_v(0)\in S_0 [/mm] und
(ii) [mm] \rho_v(i+1)\in M(\rho_v(i),v(i)) [/mm] für [mm] i\in [/mm] n
Aber sag mir mal, warum das im Skript beim NEA nicht mehr [mm] \rho_v [/mm] sondern nur noch [mm] \rho [/mm] heißt? Hat das irgendeinen Grund?
> > > (3) Definiere die von einem DEA/NEA A akzeptierte
> > > Sprache L(A).
> >
> > [mm]L(A)=\{v|\exists\mbox{akzeptierende Berechnung }\rho_v \mbox{ über v}\}[/mm]
>
> >
>
> Jou. Oder besser: Joah !
> > > (4) Zeige: Zu jedem NEA A gibt es einen äquivalenten DEA
> > > B, d.h. mit L(A)=L(B).
> >
> > Das macht man mit der Potenzautomatenkonstruktion...
> Ja und, wo steht die hier ? Die musst Du sofort und zuegig
> hinschreiben koennen.
Joah - da war ich gestern auch zu faul zu. Also jetzt:
Sei [mm] \cal{A} [/mm] = [mm] (S,M,S_0,F) [/mm] ein NEA. Dann konstruiere ich den zugehörigen EA [mm] \cal{B} [/mm] = [mm] (S',M',s_0',F') [/mm] folgendermaßen:
[mm] S'=\cal{P}(S)
[/mm]
[mm] M'(A,\sigma)=\bigcup_{s\in A}(s,\sigma) [/mm] für [mm] A\in\cal{P}(S) [/mm] und [mm] \sigma\in\summe
[/mm]
[mm] s_0'=S_0
[/mm]
[mm] F'=\{A\in\cal{P(S)}|A\cap F\not=\emptyset\}
[/mm]
> > > (6) Zeige durch Konstruktion geeigneter NEA, dass
> > > [mm]REG_{\{0,1\}}[/mm] abgeschlossen unter Komplement, Schnitt,
> > > Vereinigung und symmetrischer Differenz ist.
> >
> > Sei [mm]A=(S,M,s_0,F)[/mm] der zum gegebenen NEA zugehörige EA
> > (Potenzautomat). Dann konstruiere ich für das Komplement
> > einen Automaten A', sodass [mm]\overline{L(A)}=L(A'):[/mm]
> > [mm]A'=(S,M,s_0,S\backslash[/mm] F) mit [mm]S,M,s_0,F[/mm] wie bei A
>
> Ok.
>
> > Nun habe ich im Kopf, dass nur entweder Schnitt oder
> > Vereinigung einfach waren, würde aber beides folgendermaßen
> > machen:
> > [mm]A=(S_1,M_1,S_{0,1},F)[/mm] und [mm]B=(S_2,M_2,S_{0,2},F)[/mm]
> gegeben
> > C mit [mm]L(C)=L(A)\cap[/mm] L(B):
> > [mm]C=(S_1\times S_2,[/mm] M', [mm](s_{0,1},s_{0,2}),F')[/mm] mit
> [mm]s_{0,i}\in S_{0,i}[/mm]
> > für i=1,2
> > [mm]M'((s_1,s_2),\sigma)=(M_1(s_1,\sigma),M_2(s_2,\sigma))[/mm]
> > [mm]F'=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\in F_2\}[/mm]
> > und
> für die
> > Vereinigung dann alles genauso, nur als Endzustandsmenge:
> > [mm]F''=\{(s_1,s_2)|s_1\in F_1 \vee s_2\in F_2\}[/mm]
> >
>
> Beides ok fuer EA. Ja, was funktioniert denn nun fuer NEA
> nicht ???
>
> Nun, fuer NEA solltest Du zuerst die Uebergangsfunktion
> anders definieren, gell ?
> Dann schauen wir weiter.
Äh - zu welchem Teil der Aufgabe soll ich die Übergangsfunktion anders definieren?
> > Und für die symmetrische Differenz:
> > [mm]F'''=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\notin F_2\vee s_1\notin F_1 \wedge s_2\in F_2\}[/mm]
>
> >
> > Gibt es da irgendein Problem oder war das nur bei
> > [mm]\omega-Sprachen[/mm] problematisch? Und geht das hier eigentlich
> > mit einem NEA oder muss ich vorher einen DEA draus machen?
> >
>
> Ueberleg doch mal: Wenn Du ein Paar von Berechnungen der
> beiden NEA hast und davon eine akz. und
> die andere verwirft, dann ist das doch sicherlich Garant
> dafuer, dass der String in der einen Sprache -
> korrespondierend zur akz. ber. - drin liegt. Aber kann man
> auch mit Sicherheit sagen, dass er in der anderen nicht
> liegt ?
Liegt das Problem dabei, dass ich von einem NEA ausgegangen bin? Denn da kann es ja noch einen anderen Weg (oder auch mehrere andere) geben, sodass das Wort dann trotzdem in der Sprache liegt, auch wenn ich in diesem Fall nicht in einem Endzustand lande. Ist das richtig? Aber wenn ich mir vorher einen passenden EA konstruiere müsste das doch wieder gehen, oder?
> > > (7) Zeige: Es gibt Sprachen [mm]L\subseteq\{0,1\}^{\star},[/mm] die
> > > durch keinen NEA erkannt werden (also nicht-reguläre
> > > Sprachen).
> >
> > Wie macht man das? Hast du ein Stichwort?
> >
>
> Viele. Und andererseits Sprachlosigkeit. Aber zu den
> Stichwoertern was auf anderem Wege.
Mmh - die hatten wir immer noch nicht besprochen, oder?
> PS Was ist dem Strang zu RE und mit dem zur Berechenbarkeit
> ?
Da hatte ich gestern keine Lust mehr zu. Und jetzt auch nicht.
> Und wie lang hast Du fuer diese Aufgaben hier gebraucht ?
Also, gestern hatte ich ca eine halbe Stunde im Skript rumgeblättert und zwischendurch auf Schmierpapier gekrakelt, und dann habe ich bestimmt nochmal genauso lange gebraucht, um das Ganze hier aufzuschreiben.
Jetzt habe ich das eben nochmal nachgearbeitet und irgendwie war mir da fast alles klar, und hier habe ich es jetzt auswendig aufgeschrieben, dann allerdings meistens nochmal verglichen. Ich hoffe nicht, dass mir da noch ein Fehler unterlaufen ist...
Viele Grüße
Christiane
![[winken]](/images/smileys/winken.gif "[winken]")
|
|
|
| |
|
> Lieber Mathias!
>
> Bin gerade die Aufgaben nochmal durchgegangen.
Löblich.
>
> > > > (2) Definiere die Menge [mm]\{0,1\}^{\star}[/mm] sowie den Begriff
> > > > der Berechnung eines DEA/NEA über einer Eingabe
> > > > [mm]v\in\{0,1\}^{\star}.[/mm]
>
> > > Die Berechnung kann ich nicht in Kurzform. Im Skript wird
> > > angefangen mit v: n [mm]\to\summe[/mm] usw.. Aber kann man das v
> > > nicht irgendwie weglassen?
> > >
> >
> > Nö, denn v ist die Eingabe, und ohne Eingabe berechnet der
> > Automat auch nichts.
>
> Ja, eigentlich klar. War wohl vor allem zu faul
> zum Schreiben gestern...
> Also, sei [mm]\cal{A}[/mm] ein DEA und [mm]v:n\to\summe[/mm] ein Wort, dann
> heißt die Abbildung [mm]\rho_v:n+1\to[/mm] S mit
> (i) [mm]\rho_v(0)=s_0[/mm] und
> (ii) [mm]\rho_v(i+1)=M(\rho_v(i),v(i))[/mm] für [mm]i\in[/mm] n
> die [mm]\cal{A}\mbox{-Berechnung über v}[/mm]
>
> Bei einem NEA ändert sich hierbei nur folgendes:
> (i) [mm]\rho_v(0)\in S_0[/mm] und
> (ii) [mm]\rho_v(i+1)\in M(\rho_v(i),v(i))[/mm] für [mm]i\in[/mm] n
>
Ok.
> Aber sag mir mal, warum das im Skript beim NEA nicht mehr
> [mm]\rho_v[/mm] sondern nur noch [mm]\rho[/mm] heißt? Hat das irgendeinen
> Grund?
Sparen von Schreibarbeit.
>
> > > > (3) Definiere die von einem DEA/NEA A akzeptierte
> > > > Sprache L(A).
> > >
> > > [mm]L(A)=\{v|\exists\mbox{akzeptierende Berechnung }\rho_v \mbox{ über v}\}[/mm]
>
> >
> > >
> >
> > Jou. Oder besser: Joah !
>
>
>
> > > > (4) Zeige: Zu jedem NEA A gibt es einen äquivalenten DEA
> > > > B, d.h. mit L(A)=L(B).
> > >
> > > Das macht man mit der Potenzautomatenkonstruktion...
> > Ja und, wo steht die hier ? Die musst Du sofort und
> zuegig
> > hinschreiben koennen.
>
> Joah - da war ich gestern auch zu faul zu. Also jetzt:
> Sei [mm]\cal{A}[/mm] = [mm](S,M,S_0,F)[/mm] ein NEA. Dann konstruiere ich
> den zugehörigen EA [mm]\cal{B}[/mm] = [mm](S',M',s_0',F')[/mm]
> folgendermaßen:
> [mm]S'=\cal{P}(S)[/mm]
> [mm]M'(A,\sigma)=\bigcup_{s\in A}(s,\sigma)[/mm] für [mm]A\in\cal{P}(S)[/mm]
> und [mm]\sigma\in\summe[/mm]
> [mm]s_0'=S_0[/mm]
> [mm]F'=\{A\in\cal{P(S)}|A\cap F\not=\emptyset\}[/mm]
>
Wow !
> > > > (6) Zeige durch Konstruktion geeigneter NEA, dass
> > > > [mm]REG_{\{0,1\}}[/mm] abgeschlossen unter Komplement, Schnitt,
> > > > Vereinigung und symmetrischer Differenz ist.
> > >
> > > Sei [mm]A=(S,M,s_0,F)[/mm] der zum gegebenen NEA zugehörige EA
> > > (Potenzautomat). Dann konstruiere ich für das Komplement
> > > einen Automaten A', sodass [mm]\overline{L(A)}=L(A'):[/mm]
> > > [mm]A'=(S,M,s_0,S\backslash[/mm] F) mit [mm]S,M,s_0,F[/mm] wie bei A
> >
> > Ok.
> >
> > > Nun habe ich im Kopf, dass nur entweder Schnitt oder
> > > Vereinigung einfach waren, würde aber beides folgendermaßen
> > > machen:
> > > [mm]A=(S_1,M_1,S_{0,1},F)[/mm] und [mm]B=(S_2,M_2,S_{0,2},F)[/mm]
> > gegeben
> > > C mit [mm]L(C)=L(A)\cap[/mm] L(B):
> > > [mm]C=(S_1\times S_2,[/mm] M', [mm](s_{0,1},s_{0,2}),F')[/mm] mit
> > [mm]s_{0,i}\in S_{0,i}[/mm]
> > > für i=1,2
> > >
> [mm]M'((s_1,s_2),\sigma)=(M_1(s_1,\sigma),M_2(s_2,\sigma))[/mm]
> > > [mm]F'=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\in F_2\}[/mm]
> > >
> und
> > für die
> > > Vereinigung dann alles genauso, nur als Endzustandsmenge:
> > > [mm]F''=\{(s_1,s_2)|s_1\in F_1 \vee s_2\in F_2\}[/mm]
> > >
> >
> > Beides ok fuer EA. Ja, was funktioniert denn nun fuer NEA
> > nicht ???
> >
> > Nun, fuer NEA solltest Du zuerst die Uebergangsfunktion
> > anders definieren, gell ?
> > Dann schauen wir weiter.
>
> Äh - zu welchem Teil der Aufgabe soll ich die
> Übergangsfunktion anders definieren?
>
Wenn Du Kreuzprodukt-Automaten zu NEA A,B basteln willst mit
[mm] A=(S_A,M_A,S_{0,A},F_A)
[/mm]
[mm] B=(S_B,M_B,S_{0,B},F_B)
[/mm]
so nimmst Du tatsaechlich [mm] S=S_A\times S_B, S_0=S_{0,A}\times S_{0,B}, [/mm] musst dann aber auch formal drauf
achten, dass
[mm] M\colon S\to [/mm] P(S)
abbildet, also
[mm] M\colon S_A\times S_B:\:\to\:\: P(S_A\times S_B)
[/mm]
[mm] M((s,s'),\sigma)\:\: =\:\: M_A(s,\sigma)\times M_B(s',\sigma),
[/mm]
nicht wahr ?
> > > Und für die symmetrische Differenz:
> > > [mm]F'''=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\notin F_2\vee s_1\notin F_1 \wedge s_2\in F_2\}[/mm]
>
> >
> > >
> > > Gibt es da irgendein Problem oder war das nur bei
> > > [mm]\omega-Sprachen[/mm] problematisch? Und geht das hier eigentlich
> > > mit einem NEA oder muss ich vorher einen DEA draus machen?
> > >
> >
> > Ueberleg doch mal: Wenn Du ein Paar von Berechnungen der
> > beiden NEA hast und davon eine akz. und
> > die andere verwirft, dann ist das doch sicherlich
> Garant
> > dafuer, dass der String in der einen Sprache -
> > korrespondierend zur akz. ber. - drin liegt. Aber kann man
> > auch mit Sicherheit sagen, dass er in der anderen nicht
> > liegt ?
>
> Liegt das Problem dabei, dass ich von einem NEA ausgegangen
> bin? Denn da kann es ja noch einen anderen Weg (oder auch
> mehrere andere) geben, sodass das Wort dann trotzdem in der
> Sprache liegt, auch wenn ich in diesem Fall nicht in einem
> Endzustand lande. Ist das richtig? Aber wenn ich mir vorher
> einen passenden EA konstruiere müsste das doch wieder
> gehen, oder?
>
Ja. Aber Dir sollte auch wirklich klar sein, warum es bei NEA schieflaufen kann. Grund:
Wenn Du mit Deiner Konstr. bei zwei NEA eine Eingabe hast, die in beiden Sprachen drin ist, aber
fuer den einen NEA eine verwerfende Berechnung existiert, so fuehrt diese gepaart mit einer akzeptierenden
des anderen NEA bei Dir zur Existenz einer akzeptierenden Berechnung, wohingegen das Wort nicht in der
symmetrischen Differenz drin ist und daher fuer einen korrekt konstruierten NEA keine akz. berechnung existieren darf.
Klar ?
> > > > (7) Zeige: Es gibt Sprachen [mm]L\subseteq\{0,1\}^{\star},[/mm] die
> > > > durch keinen NEA erkannt werden (also nicht-reguläre
> > > > Sprachen).
> > >
> > > Wie macht man das? Hast du ein Stichwort?
> > >
> >
> > Viele. Und andererseits Sprachlosigkeit. Aber zu den
> > Stichwoertern was auf anderem Wege.
>
> Mmh - die hatten wir immer noch nicht besprochen, oder?
>
DOCH !!! (Die Frage ist nur: Wann ?)
Im Vertrauen: Themen, die an anderem Ort hauptsächlich zu diesem Zwecke
besprochen wurden und dann doch auch hier, sind mit der Grund, warum wir uns hier
überhaupt darüber unterhalten können.
> > PS Was ist dem Strang zu RE und mit dem zur Berechenbarkeit
> > ?
>
> Da hatte ich gestern keine Lust mehr zu. Und jetzt auch
> nicht.
>
Tzzzzz.... ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Das beste am Menu läßt Du stehen.....
> > Und wie lang hast Du fuer diese Aufgaben hier gebraucht ?
> Also, gestern hatte ich ca eine halbe Stunde im Skript
> rumgeblättert und zwischendurch auf Schmierpapier
> gekrakelt, und dann habe ich bestimmt nochmal genauso lange
> gebraucht, um das Ganze hier aufzuschreiben.
> Jetzt habe ich das eben nochmal nachgearbeitet und
> irgendwie war mir da fast alles klar, und hier habe ich es
> jetzt auswendig aufgeschrieben, dann allerdings meistens
> nochmal verglichen. Ich hoffe nicht, dass mir da noch ein
> Fehler unterlaufen ist...
>
> Viele Grüße
> Christiane
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:33 Di 21.02.2006 | | Autor: | Bastiane |
Lieber Mathias!
> > Aber sag mir mal, warum das im Skript beim NEA nicht mehr
> > [mm]\rho_v[/mm] sondern nur noch [mm]\rho[/mm] heißt? Hat das irgendeinen
> > Grund?
>
> Sparen von Schreibarbeit.
![[totlach]](/images/smileys/totlach.gif "[totlach]") Aber warum dann bei einem EA mit dem v???
> > > > > (6) Zeige durch Konstruktion geeigneter NEA, dass
> > > > > [mm]REG_{\{0,1\}}[/mm] abgeschlossen unter Komplement, Schnitt,
> > > > > Vereinigung und symmetrischer Differenz ist.
> > > >
> > > > Sei [mm]A=(S,M,s_0,F)[/mm] der zum gegebenen NEA zugehörige EA
> > > > (Potenzautomat). Dann konstruiere ich für das Komplement
> > > > einen Automaten A', sodass [mm]\overline{L(A)}=L(A'):[/mm]
> > > > [mm]A'=(S,M,s_0,S\backslash[/mm] F) mit [mm]S,M,s_0,F[/mm] wie bei
> A
> > >
> > > Ok.
> > >
> > > > Nun habe ich im Kopf, dass nur entweder Schnitt oder
> > > > Vereinigung einfach waren, würde aber beides folgendermaßen
> > > > machen:
> > > > [mm]A=(S_1,M_1,S_{0,1},F)[/mm] und [mm]B=(S_2,M_2,S_{0,2},F)[/mm]
> > > gegeben
> > > > C mit [mm]L(C)=L(A)\cap[/mm] L(B):
> > > > [mm]C=(S_1\times S_2,[/mm] M', [mm](s_{0,1},s_{0,2}),F')[/mm] mit
> > > [mm]s_{0,i}\in S_{0,i}[/mm]
> > > > für i=1,2
> > > >
> > [mm]M'((s_1,s_2),\sigma)=(M_1(s_1,\sigma),M_2(s_2,\sigma))[/mm]
> > > > [mm]F'=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\in F_2\}[/mm]
> >
> > >
> > und
> > > für die
> > > > Vereinigung dann alles genauso, nur als Endzustandsmenge:
> > > > [mm]F''=\{(s_1,s_2)|s_1\in F_1 \vee s_2\in F_2\}[/mm]
> >
> > >
> > >
> > > Beides ok fuer EA. Ja, was funktioniert denn nun fuer NEA
> > > nicht ???
> > >
> > > Nun, fuer NEA solltest Du zuerst die Uebergangsfunktion
> > > anders definieren, gell ?
> > > Dann schauen wir weiter.
> >
> > Äh - zu welchem Teil der Aufgabe soll ich die
> > Übergangsfunktion anders definieren?
> >
>
> Wenn Du Kreuzprodukt-Automaten zu NEA A,B basteln willst
> mit
>
> [mm]A=(S_A,M_A,S_{0,A},F_A)[/mm]
> [mm]B=(S_B,M_B,S_{0,B},F_B)[/mm]
>
> so nimmst Du tatsaechlich [mm]S=S_A\times S_B, S_0=S_{0,A}\times S_{0,B},[/mm]
> musst dann aber auch formal drauf
> achten, dass
>
> [mm]M\colon S\to[/mm] P(S)
>
> abbildet, also
>
> [mm]M\colon S_A\times S_B:\:\to\:\: P(S_A\times S_B)[/mm]
Joah.
> [mm]M((s,s'),\sigma)\:\: =\:\: M_A(s,\sigma)\times M_B(s',\sigma),[/mm]
Aber das verstehe ich so spät heute irgendwie nicht mehr...
> nicht wahr ?
> > > > Und für die symmetrische Differenz:
> > > > [mm]F'''=\{(s_1,s_2)|s_1\in F_1 \wedge s_2\notin F_2\vee s_1\notin F_1 \wedge s_2\in F_2\}[/mm]
>
> >
> > >
> > > >
> > > > Gibt es da irgendein Problem oder war das nur bei
> > > > [mm]\omega-Sprachen[/mm] problematisch? Und geht das hier eigentlich
> > > > mit einem NEA oder muss ich vorher einen DEA draus machen?
> > > >
> > >
> > > Ueberleg doch mal: Wenn Du ein Paar von Berechnungen der
> > > beiden NEA hast und davon eine akz. und
> > > die andere verwirft, dann ist das doch sicherlich
> > Garant
> > > dafuer, dass der String in der einen Sprache -
> > > korrespondierend zur akz. ber. - drin liegt. Aber kann man
> > > auch mit Sicherheit sagen, dass er in der anderen nicht
> > > liegt ?
> >
> > Liegt das Problem dabei, dass ich von einem NEA ausgegangen
> > bin? Denn da kann es ja noch einen anderen Weg (oder auch
> > mehrere andere) geben, sodass das Wort dann trotzdem in der
> > Sprache liegt, auch wenn ich in diesem Fall nicht in einem
> > Endzustand lande. Ist das richtig? Aber wenn ich mir vorher
> > einen passenden EA konstruiere müsste das doch wieder
> > gehen, oder?
> >
>
> Ja. Aber Dir sollte auch wirklich klar sein, warum es bei
> NEA schieflaufen kann. Grund:
>
> Wenn Du mit Deiner Konstr. bei zwei NEA eine Eingabe hast,
> die in beiden Sprachen drin ist, aber
> fuer den einen NEA eine verwerfende Berechnung existiert,
> so fuehrt diese gepaart mit einer akzeptierenden
> des anderen NEA bei Dir zur Existenz einer akzeptierenden
> Berechnung, wohingegen das Wort nicht in der
> symmetrischen Differenz drin ist und daher fuer einen
> korrekt konstruierten NEA keine akz. berechnung existieren
> darf.
>
> Klar ?
Ich glaub', das war mir schon klar, aber wir sollten vielleicht doch irgendwann nochmal drüber sprechen. Damit ich weiß, ob ich das auch vernünftig erklären kann.
> > > > > (7) Zeige: Es gibt Sprachen [mm]L\subseteq\{0,1\}^{\star},[/mm] die
> > > > > durch keinen NEA erkannt werden (also nicht-reguläre
> > > > > Sprachen).
> > > >
> > > > Wie macht man das? Hast du ein Stichwort?
> > > >
> > >
> > > Viele. Und andererseits Sprachlosigkeit. Aber zu den
> > > Stichwoertern was auf anderem Wege.
> >
> > Mmh - die hatten wir immer noch nicht besprochen, oder?
> >
>
> DOCH !!! (Die Frage ist nur: Wann ?)
Äh - auch in den letzten paar Tagen? Oder irgendwann vor einem Monat mal?
> Im Vertrauen: Themen, die an anderem Ort hauptsächlich zu
> diesem Zwecke
> besprochen wurden und dann doch auch hier, sind mit der
> Grund, warum wir uns hier
> überhaupt darüber unterhalten können.
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]") Was soll das heißen? Da bekomme ich irgendwie einen Knoten ins Gehirn. ![[haee]](/images/smileys/haee.gif "[haee]")
> > > PS Was ist dem Strang zu RE und mit dem zur Berechenbarkeit
> > > ?
> >
> > Da hatte ich gestern keine Lust mehr zu. Und jetzt auch
> > nicht.
> >
>
> Tzzzzz....
>
> Das beste am Menu läßt Du stehen.....
Nee - ich bin nur immer noch zu blöd dazu. Ich kann zwar mit etwas nachdenken die meisten Defintionen jetzt aufschreiben, aber vorstellen kann ich mir dadrunter immer noch nix. ![[wein]](/images/smileys/wein.gif "[wein]")
Viele Grüße
Bastiane
|
|
|
|
