Entscheidungsproblem formalisi < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei [mm] \summe [/mm] ein Alphabet und k [mm] \ge [/mm] 1. Formalisieren Sie folgendes Entscheidungs-
problem: Sind bei dem eingegebenen Wort über [mm] \summe [/mm] das Präfix der Länge k und
das Suffix der Länge k gleich? Geben Sie das Problem in Mengenschreib-
weise und als Eingabe / Frage an.
Lösungshinweis: Der Parameter k ist nicht Teil der Eingabe. Genau genom-
men spezifizieren Sie also eine Familie von Entscheidungsproblemen, näm-
lich für jedes k ein anderes. |
Hallo.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Habe mir das als Lösung überlegt:
Mengenschreibweise:
[mm] M=\{ w | w = ava; |a| = k; k \ge 1; a,v,w \in \summe ^{\*} \}
[/mm]
Eingabe/Ausgabe:
Eingabe: [mm] w \in \summe ^{\*} [/mm]
Ausgabe: 1, falls [mm]w = ava[/mm], wobei [mm]a,v \in \summe ^{\*}[/mm] und [mm]|a|=k[/mm] wobei [mm]k \ge 1[/mm]
0, sonst
Kann man das so schreiben/stimmt das so? Oder hab ich die Aufgabe falsch verstanden?
Vielen Dank schonmal.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 23.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
