Kellerautomat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:01 Do 26.11.2009 | | Autor: | SaSu |
| Aufgabe | Entscheiden Sie, ob die folgenden Aussagen wahr oder falsch sind, und begründen Sie dies stichhaltig.
[...]
b) Zu jeder kontextfreien Sprache [mm] \mathcal{L} [/mm] gibt es einen Kellerautomaten [mm] \mathcal{K} [/mm] = [mm] (\Sigma, \mathcal{Q}, \Gamma, \to, q_{0}, Z_{0}, \mathcal{F}) [/mm] mit [mm] \mathcal{L}(\mathcal{K}) [/mm] = [mm] \mathcal{L} [/mm] und [mm] |\mathcal{F}| [/mm] = 1.
c) Zu jeder kontextfreien Sprache [mm] \mathcal{L} [/mm] gibt es einen Kellerautomaten [mm] \mathcal{K} [/mm] = [mm] (\Sigma, \mathcal{Q}, \Gamma, \to, q_{0}, Z_{0}, \mathcal{F}) [/mm] mit [mm] \mathcal{L}(\mathcal{K}) [/mm] = [mm] \mathcal{L} [/mm] und [mm] |\Gamma| [/mm] = 1. |
- Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Eine Teilaufgabe konnten wir bereits lösen, bei diesen beiden kommen wir jedoch leider nicht weiter, bzw. haben nur Ansätze bei denen wir uns nicht ganz sicher sind.
Wäre nett, wenn uns jemand helfen könnte.
|
|
| |
|
Hallo SaSu und herzlich ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]") ,
> Entscheiden Sie, ob die folgenden Aussagen wahr oder falsch
> sind, und begründen Sie dies stichhaltig.
>
> [...]
>
> b) Zu jeder kontextfreien Sprache [mm]\mathcal{L}[/mm] gibt es einen
> Kellerautomaten [mm]\mathcal{K}[/mm] = [mm](\Sigma, \mathcal{Q}, \Gamma, \to, q_{0}, Z_{0}, \mathcal{F})[/mm]
> mit [mm]\mathcal{L}(\mathcal{K})[/mm] = [mm]\mathcal{L}[/mm] und
> [mm]|\mathcal{F}|[/mm] = 1.
>
> c) Zu jeder kontextfreien Sprache [mm]\mathcal{L}[/mm] gibt es einen
> Kellerautomaten [mm]\mathcal{K}[/mm] = [mm](\Sigma, \mathcal{Q}, \Gamma, \to, q_{0}, Z_{0}, \mathcal{F})[/mm]
> mit [mm]\mathcal{L}(\mathcal{K})[/mm] = [mm]\mathcal{L}[/mm] und [mm]|\Gamma|[/mm] =
> 1.
> - Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Eine Teilaufgabe konnten wir bereits lösen, bei diesen
> beiden kommen wir jedoch leider nicht weiter, bzw. haben
> nur Ansätze bei denen wir uns nicht ganz sicher sind.
Na, dann postet doch mal eure Ansätze und Ideen, daraus kann man bestimmt was machen.
Außerdem ist das Vorstellen eigener Ansätze immer gern gesehen.
Also schreibt mal, was ihr euch gedacht habt, dann wird das bestimmt was ...
>
> Wäre nett, wenn uns jemand helfen könnte.
Liebe Grüße
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:30 Do 26.11.2009 | | Autor: | mangaka |
Ich gehöre mit zur Gruppe^^
zu b)
Wir haben angenommen, dass der KA zur Vereinigung von zwei kontextfreien Sprachen zwei Endzustände besitzen müsste, so wie bei epsilon-NEAs.
Aber ich denke, dass das nicht wirklich zutrifft.
zu c)
Hier denken wir, dass man nicht jede kontextfreie Sprache nur mit einem Kellersymbol repräsentieren kann.
Man benutzt ja das oberste Symbol auf dem Stack für gewisse Entscheidungen, z.B was als nächstes gepoppt wird oder wie der nächste Zustand lautet.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 So 29.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
