Reguläre Sprachen 2 < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 09:00 Di 31.01.2006 | | Autor: | mathiash |
| Aufgabe | Es sei [mm]A[/mm] ein nichtdeterministischer endlicher Automat (ohne [mm]\epsilon\texttt{--"Uberg"ange}[/mm] !!!) über dem Alphabet [mm]\{0,1\}[/mm].
Zeige: Fur jedes [mm]k\in\IN[/mm] ist die Sprache
[mm]L_k(A)=\left\{x\in\{0,1\}^{\star}\: |\: \exists\texttt{ mindestens }k\texttt{ verschiedene akz. Berechnungen von }A\texttt{ bei Eingabe }x\right\}[/mm]
regulär.
Dabei ist eine Berechnung von [mm]A[/mm] über Eingabe [mm]x[/mm] eine Folge von [mm]\left|x\right|+1[/mm] Zuständen des Automaten, so dass der erste ein Startzustand ist und für [mm]i=1,\dotsc,\left|x\right|[/mm] (wir fangen bei [mm]i=0[/mm] an zu zählen) der [mm]i\texttt{--te}[/mm] Zustand vom [mm](i-1)\texttt{--ten}[/mm] aus bei Lesen des Zeichens [mm]x_{i-1}[/mm] erreicht werden kann. Akzeptierend heißt die Berechnung, falls der letzte Zustand der Folge ein akzeptierender Zustand ist. |
Hallo zusammen,
diese Aufgabe hatte ich mir mal vor zwei Jahren selber ausgedacht - mag sein, daß sie trotzdem schon irgendwo anders vorher aufgetaucht ist, ich erhebe nicht formal Urheberrechte auf sie.
Viele Grüße,
Mathias
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:03 Di 31.01.2006 | | Autor: | mathiash |
Hallo zusammen,
was passiert, wenn wir in obiger Aufgabe zum Beispiel k durch n oder [mm] n^2 [/mm] ersetzen, wobei
n die Länge der Eingabe ist ?
Gruss,
Mathias
|
|
|
|
