DEA aus Sprache L? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:46 Sa 10.12.2011 | | Autor: | bandchef |
| Aufgabe | Zeigen Sie, dass die folgende Sprache regulär ist, indem sie deterministische endliche Automaten angeben, welche dieses Sprache erkennen:
$L = [mm] \{1^n 0^m | n, m \in \mathbb N \wedge (n+m)mod2 = 0\}$ [/mm] |
Hi Leute!
Könnt ihr mir erklären wie man auf den DEA dazu kommt? Ich hab bisher bei Automatenkonstruktion mir immer erst den NEA durch Gehirnschmalz überlegt und dann durch Potenzmengenkonstruktion den DEA entworfen. Aber das "Gehirnschmalz" ist das Problem  Das hier ist schon eine ziemlich hart Nuss. Gibts da nicht auch irgendwelche Verfahren?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:39 So 11.12.2011 | | Autor: | sandp |
> Zeigen Sie, dass die folgende Sprache regulär ist, indem
> sie deterministische endliche Automaten angeben, welche
> dieses Sprache erkennen:
>
> [mm]L = \{1^n 0^m | n, m \in \mathbb N \wedge (n+m)mod2 = 0\}[/mm]
>
>
> Hi Leute!
>
> Könnt ihr mir erklären wie man auf den DEA dazu kommt?
> Ich hab bisher bei Automatenkonstruktion mir immer erst den
> NEA durch Gehirnschmalz überlegt und dann durch
> Potenzmengenkonstruktion den DEA entworfen. Aber das
> "Gehirnschmalz" ist das Problem Das hier ist schon eine
> ziemlich hart Nuss. Gibts da nicht auch irgendwelche
> Verfahren?
Hey,
soweit ich weiß gibt es keine konkreten Verfahren um aus einer Sprache den Automaten abzulesen. Einfach ein bisschen logisch denken, dann kann man den DEA schon zeichnen.
Du musst dir als erstes überlegn, was die Sprache sagt, hier sagt sie ja nur, dass die Anzahl der 0 addiert mit der Anzahl der 1 durch 2 teilbar sein muss.
Jetzt fängst du am besten an mit n,m = 0, das ist nicht schwer diesen DEA zu zeichnen, hat ja nur einen Zustand, dieser ist Start- und Endzustand.
Jetzt machst du weiter mit n,m = 1, was musst du hier anfügen?
wenn du das hast probier einen Zyklus zu bauen
Gruß
|
|
|
|
