Kellerautomat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:19 Do 02.01.2014 | | Autor: | DrRiese |
| Aufgabe | Zeigen Sie, dass jeder nichtdeterministische Kellerautomat [mm] M=(Z,\Sigma,\Gamma,\delta,z_{0},\#,E) [/mm] in einen äquivalenten Kellerautomaten [mm] M'=(Z',\Sigma',\Gamma',\delta',z_{0}',\#,E') [/mm] umgeformt werden kann und die [mm] \delta' [/mm] Übergänge von der Form
[mm] (z',\gamma) \in \delta'(z,a,A) [/mm] mit [mm] \gamma \le [/mm] 2
sind. Die Maschine M' kann in jedem Übergang also höchstens zwei Zeichen auf den Keller schreiben. |
Hallo, darf mich mit der theoretischen Informatik befassen 
Könnte man das in etwa folgendermaßen machen?
Wenn wir einen Übergang haben, in dem wir mehr als zwei Elemente im Keller ablegen müssten, teilen wir einfach den Übergang in mehrere auf, so dass nur höchstens zwei Elemente pro Teilübergang abgelegt werden.
Nur ich weiss noch nicht so richtig, wie man das korrekt formalisieren könnte...
Würde mich sehr über Hilfe freuen
LG,
DrRiese
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:49 Do 02.01.2014 | | Autor: | felixf |
Moin!
> Zeigen Sie, dass jeder nichtdeterministische Kellerautomat
> [mm]M=(Z,\Sigma,\Gamma,\delta,z_{0},\#,E)[/mm] in einen
> äquivalenten Kellerautomaten
> [mm]M'=(Z',\Sigma',\Gamma',\delta',z_{0}',\#,E')[/mm] umgeformt
> werden kann und die [mm]\delta'[/mm] Übergänge von der Form
>
> [mm](z',\gamma) \in \delta'(z,a,A)[/mm] mit [mm]\gamma \le[/mm] 2
>
> sind. Die Maschine M' kann in jedem Übergang also
> höchstens zwei Zeichen auf den Keller schreiben.
> Hallo, darf mich mit der theoretischen Informatik befassen
>
>
> Könnte man das in etwa folgendermaßen machen?
>
> Wenn wir einen Übergang haben, in dem wir mehr als zwei
> Elemente im Keller ablegen müssten, teilen wir einfach den
> Übergang in mehrere auf, so dass nur höchstens zwei
> Elemente pro Teilübergang abgelegt werden.
Ja, so in etwa. Es ist im Prinzip genau das gleiche wie hier. Wenn du dort eine schoene Methode hast, wie du die neuen Regeln einfach hinschreiben kannst, dann kannst du es hier auch.
Deswegen wuerde ich sagen, loes erstmal die andere Aufgabe richtig (also formal korrekt), bevor du anfaengst diese hier formal korrekt aufzuschreiben.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:29 Di 07.01.2014 | | Autor: | felixf |
Moin,
> habe hierzu eine Frage: Muss man hier also das [mm]\delta[/mm] in
> mehrere [mm]\delta'[/mm] aufsplitten mit [mm]|\gamma| \le[/mm] 2?
ja, sozusagen :) Ist wie bei den Grammatiken: ein Temporaerobjekt auf den Stack packen, und im naechsten Schritt durch ein neues Symbol und weiteres Temporaerobjekt ersetzen, und immer so weiter, bis das was an Symbolen drauf sollte auch da ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:43 Di 07.01.2014 | | Autor: | DrRiese |
Hi,
also in etwa so?
sei [mm] \gamma [/mm] = [mm] v_{1}v_{2}*...*v_{n}
[/mm]
also [mm] (z',\gamma) \in \delta(z,a,A), |\gamma| [/mm] > 2, dann
[mm] (z',v_{1}v_{2}) \in \delta_{1}'(z,a,A)
[/mm]
[mm] (z',v_{3}v_{4}) \in \delta_{2}'(z,a,A)
[/mm]
[mm] \vdots
[/mm]
[mm] (z',v_{n-1}v_{n}) \in \delta_{n/2}'(z,a,A)
[/mm]
Wäre es so vom Prinzip her?
LG,
DrRiese
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 09.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:21 So 12.01.2014 | | Autor: | DrRiese |
Keinen Tipp? :-(
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 14.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
