Präfixsprachen - Index < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben Sie die Menge der Präfixsprachen, den Index und einen minimalen DFA für die Sprache über dem Alphabet {0, 1} an, die aus den Worten 1, 00, 001, 110 besteht. |
Hallo!
Ich bin leider noch nicht so fit auf dem Gebiet und finde in meinem Skript und im Internet auch keine guten Beispiele die mir bei der Aufgabe auf die Sprünge helfen.
Also ich weiß, dass die Präfixsprache gemäß der Nerode Relation wie folgt definiert ist:
Nerode Relation [mm] $\sim_L$ [/mm] auf [mm] $\Sigma^\*$
[/mm]
Präfixsprache: [mm] $L_x [/mm] = [mm] \{\enspace y\enspace|\enspace xy \in L\}$ [/mm] von L zu Präfix x
Wenn ich nun die Menge der Präfixsprachen bestimmen soll, so ist das doch nichts anderes als die Menge der Äquivalenzklassen zum Präfix x.
Also folgendermaßen [mm] $\{[x]_L|x\in \Sigma^\*\}$ [/mm] wobei die Sprache [mm] $L=\{1, 00, 011, 110\}$ [/mm] ist
Aber ich verstehe nicht genau wie ich die Menge der Präfixsprachen bestimmen soll.
Ich habe hier einen Ansatz, bei dem ich mich an die Nerode Relation gehalten habe, wobei ich denke das ich etwas falsch mache.
Meine Idee:
[mm] $L_\varepsilon \quad= [/mm] L = [mm] [\varepsilon]_L$ [/mm] <- hier die ganze Sprache L, da Epsilon ja Präfix jeden Wortes ist.
[mm] $L_1 \quad= \{\varepsilon, 10\} [/mm] = [mm] [1]_L$
[/mm]
[mm] $L_{11} \quad= \{0\} [/mm] = [mm] [11]_L$
[/mm]
[mm] $L_{110} \quad= \{\varepsilon\} [/mm] = [mm] [110]_L$
[/mm]
[mm] $L_{0} \quad= \{0, 01\} [/mm] = [mm] [0]_L$
[/mm]
[mm] $L_{00} \quad= \{\varepsilon, 1\} [/mm] = [mm] [00]_L$
[/mm]
[mm] $L_{001} \quad= \{\varepsilon\} [/mm] = [mm] [001]_L$
[/mm]
Wenn ich jetzt die mengenmäßig gleichen Äquivalenzklassen herausnehme sieht meine Menge der Präfixsprachen wie folgt aus:
[mm] $\{[\varepsilon]_L, [1]_L, [11]_L, [110]_L, [0]_L, [00]_L\}$
[/mm]
Das ist wahrscheinlich totaler Mist, oder?
Ich hoffe ihr könnt mir da helfen.
Vielen Dank schon mal!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:20 Di 18.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
