NFA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:44 Di 05.04.2011 | | Autor: | Parkan |
| Aufgabe | 1. Geben Sie einen NFA A1 an, der die folgende Sprache akzeptiert:
[mm] L1:=\{w\in\{0, . . . , 3\}\cdot| w \text{ enthaelt irgendeine Ziffer mindestens dreimal direkt hintereinander}\} [/mm] |
Hallo
Leider ist mir trotz Script und Buch nicht ganz ersichtlich wie ich dies Lösen kann. Hier ist mein Ansatz...
[mm] A1=(\{0,1\},\{z0,z1\}\delta,\{z0\},\{z1\})
[/mm]
[mm] L1=\{w\in\{0,1,2,3\}\cdot | w = \{w_{1} . . .w_{n} , w_{i} \in \{(0,1,2,3)\}, w_{i}=w_{i+1}=w_{i+2}, 1 \leq i\leq n , n\geq 0\}\}
[/mm]
Danke für jede Hilfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:48 Mi 06.04.2011 | | Autor: | felixf |
Moin,
> 1. Geben Sie einen NFA A1 an, der die folgende Sprache
> akzeptiert:
> [mm]L1:=\{w\in\{0, . . . , 3\}\cdot| w \text{ enthaelt irgendeine Ziffer mindestens dreimal direkt hintereinander}\}[/mm]
>
>
> Hallo
> Leider ist mir trotz Script und Buch nicht ganz
> ersichtlich wie ich dies Lösen kann. Hier ist mein
> Ansatz...
> [mm]A1=(\{0,1\},\{z0,z1\}\delta,\{z0\},\{z1\})[/mm]
Glaubst du wirklich, dass du mit zwei Zustaenden zurechtkommst?
> [mm]L1=\{w\in\{0,1,2,3\}\cdot | w = \{w_{1} . . .w_{n} , w_{i} \in \{(0,1,2,3)\}, w_{i}=w_{i+1}=w_{i+2}, 1 \leq i\leq n , n\geq 0\}\}[/mm]
Das ist sehr uneindeutig aufgeschrieben, normalerweise meint man mit dieser Notation, dass die Woerter immer aus dem gleichen Buchstaben bestehen (da ein impliztes [mm] $\forall$ [/mm] hinzukommt). Du willst aber nicht [mm] $\forall$, [/mm] sondern [mm] $\exists$.
[/mm]
Schau dir mal in diesem Thread das Bild an; der zweite Automat dort ist nichtdeterministisch, und erkennt Woerter, die $a b$ oder $b a$ enthalten. Diesen Automat kannst du jetzt etwas veraendern (indem du zwei Zustaende einfuegst, einen oben und einen unten, und anstelle $a$ und $b$ $0$ und $1$ verwendest), damit er alle Woerter erkennt, die $0 0 0$ oder $1 1 1$ enthalten.
Wenn du das hast, sollte es fuer dich nicht so schwer sein ihn zu erweitern, dass er alle Woerter erkennt, die $0 0 0$, $1 1 1$, $2 2 2$ oder $3 3 3$ enthalten.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:39 Mo 11.04.2011 | | Autor: | Parkan |
Leider ist es mir immer noch nicht ganz klar. Ich habe das jetzt folgendermassen geändert.
[mm]A_{1} = ((0,1,2,3),(Z_{0}...Z_{4}),\delta,(Z_{0}),(Z_{4}))[/mm]
Aussehen sollte das so.
[Z0]--0-->[Z1]
[Z1]--0-->[Z2]
[Z2]--0-->[Z3]
[Z3]--0,1,2,3-->[Z4]
[Z3]--0,1,2,3-->[Z3]
Das Problem ist das hier nur die 0 dreimal wiederholt wird und nicht "irgendeine Zahl"
Der Automat aus deinem Link konnte mir da auch nicht helfen.
Ich habe noch ein Ansatz wo ich 13 Zustände habe. Dabei geht von Z0 jeweils ein pfeil zu 4 Verschiedenen Zuständen mit 0 oder 1 oder 2 oder 3. Von diesen geht es dann mit der jeweiligen Zahl weiter nach 3 mal vereinigen sich alle Zustände im Endzustand. Diesen Automaten kann ich zwar aufzeichnen aber ich weis nicht wie ich den formal richtig aufschreiben kann.
Gruß
Janina
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mi 13.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
