Reguläre Sprachen 1 < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 08:22 Di 31.01.2006 | | Autor: | mathiash |
| Aufgabe | Zeige: Falls [mm] L\subseteq\{0,1\}^{\star} [/mm] regulär ist, so auch die Sprache
[mm] \sqrt{L} :=\{x\in\{0,1\}^{\star}|\exists y\in\{0,1\}^{\star}\: [ \: |y|=|x|^2\:\wedge\: xy\in L\: ]\:\}. [/mm] |
Hallo zusammen,
dies ist eine schöne Übungsaufgabe aus dem Buch von Hopcroft und Ullman.
Auf Wunsch kann ich gern die Lösung erklären.
Viele Grüße,
Mathias
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:27 Di 31.01.2006 | | Autor: | mathiash |
Hallo zusammen,
wenn man die Lösung zu der Aufgabe kennt, kann man leicht folgende Erweiterung bearbeiten:
Wieder sei [mm] L\subseteq\{0,1\}^{\star} [/mm] regulär, und es sei p(x) ein Polynom in [mm] \IZ[x]
[/mm]
mit nicht-negativen Koeffizienten (also [mm] p(x)\in \IN_0[x]).
[/mm]
Zeige:
[mm] L':=\{x\: |\: \exists \: y\in\{0,1\}^{\star}\; [ |y|=p(|x|)\: \wedge\: xy\in L\: ]\:\}
[/mm]
ist regulär.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:45 Di 31.01.2006 | | Autor: | mathiash |
Hallo zusammen,
jetzt kann man allgemein fragen: Für welche Funktionen [mm] f\colon\IN\to\IN [/mm] (sagen wir: monoton steigend und in endl. viele Schritten aus den konst. fkt. via Addition, Multiplikation und
Exponentiation sowie Identität zus.gesetzt, so dass man also ''eine Formel'' fuer f hat)
ist zu jedem gegebenen regulärem [mm] L\subseteq\{0,1\}^{\star}
[/mm]
die Sprache [mm] L_f [/mm] regulär, wobei
[mm] L_f=\{x\: |\: \exists y\: [\: |y|=f(|x|)\: \wedge\: xy\in L\: ]\: \} [/mm] gilt ?
Gruss,
Mathias
|
|
|
|
