Kellerautomaten < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
$A = [mm] \left(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\right)$ [/mm] heißt Kellerautomat, wenn
$Q:$ endliche Zustandsmenge,
[mm] $\Sigma:$ endliches [/mm] Eingabealphabet,
[mm] $\Gamma:$ endliches [/mm] Stackalphabet,
[m]\delta: Q \times \left(\Sigma \cup \{\epsilon\}\right) \times \Gamma \rightarrow K \subseteq \left(Q \times \Gamma^\*\right):[/m] eine Übergangsfunktion,
[mm] $q_0 \in [/mm] Q:$ Anfangszustand,
[mm] $Z_0 \in \Gamma:$ ein [/mm] spezielles Stack-Symbol, und
$F [mm] \subset [/mm] Q:$ Menge der Endzustände ist
Allerdings finde ich in meinem Informatik II-Skript kein Beispiel für die Verwendung eines solchen Automaten. Deshalb wollte ich euch fragen, ob ihr mir Verwendungsbeispiele und vielleicht auch ein paar Aufgaben für einen solchen Automaten geben könntet.
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:52 So 19.09.2004 | | Autor: | felixs |
hallo karl
so spontan faellt mir dazu nur ein dass man mit keller automaten deterministisch kontextfreie sprachen entscheiden und auch parser fuer ebendiese bauen kann (wenn ich hier mal nichts verwechsle).
aufgaben mit automaten sehen im allgemeinen so aus dass man einen automaten fuer eine grammatik bauen, einen automaten minimieren, vereinigungs oder schnitt automaten bauen soll.
manchmal braucht man die teile auch fuer beweise whatsoever...
am besten du laesst die finger davon, bis du es wirklich brauchst, weil das (soweit ich mich erinnere) meistens unkompliziert (allerdings sehr muehsam!) ist...
gruss
--felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:59 So 19.09.2004 | | Autor: | Karl_Pech |
Hallo Felix,
> am besten du laesst die finger davon, bis du es wirklich
> brauchst, weil das (soweit ich mich erinnere) meistens
> unkompliziert (allerdings sehr muehsam!) ist...
Ich würde ja gerne die "Finger davon lassen" nur leider schreibe ich am 1.10 eine Klausur, wo genau dieses Thema vorkommen könnte. Wir hatten bis jetzt allerdings nur Aufgaben zu deterministischen Automaten gehabt, aber nicht zu solchen erweiterten Kellerautomaten. Und jetzt frage ich mich, ob er den auch eine Aufgabe zu solchen Automaten stellen könnte.
Danke für deine Antwort!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:06 Mo 11.10.2004 | | Autor: | Micha |
Hallo Karl Pech!
Da du selbst angegeben hast, am 1.10. eine Klausur darüber zu schreiben, denke ich, dass wir die Frage zurücksetzen können.
Gruß Micha 
|
|
|
|
