deterministischer Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:13 Mi 07.03.2012 | | Autor: | HelpMan |
| Aufgabe | Konstruiere deterministische endliche Automaten fuer die folgende Sprache:
{w Element von {0,1}* | Es existiert ein i Element von {0,1}, so dass w mit i endet und count(i,w) mod2 = 0}
Die Automaten sollen als Zustandsgraphen angegeben werden.
Anmerkung: count(i,w) ist dabei die Funktion, welche die Zeichen i in w zaehlt. |
Stehe momentan etwas auf dem Dampfer, da ich nicht genau verstehe, ob mit der Existenz genau nur ein Element existieren soll oder mindestens eins, welches mit den Eigenschaften behaftet ist.
Desweiteren verstehe ich gerade nicht bei der Formulierung, ob alle anderen Woerter dennoch produzierbar sein muessen.
Habt ihr vielleicht einen Ansatz oder Tipp?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:33 Do 08.03.2012 | | Autor: | sandp |
hey,
> Konstruiere deterministische endliche Automaten fuer die
> folgende Sprache:
>
> {w Element von {0,1}* | Es existiert ein i Element von
> {0,1}, so dass w mit i endet und count(i,w) mod2 = 0}
>
> Die Automaten sollen als Zustandsgraphen angegeben werden.
> Anmerkung: count(i,w) ist dabei die Funktion, welche die
> Zeichen i in w zaehlt.
> Stehe momentan etwas auf dem Dampfer, da ich nicht genau
> verstehe, ob mit der Existenz genau nur ein Element
> existieren soll oder mindestens eins, welches mit den
> Eigenschaften behaftet ist.
>
Formal ausgedrückt würde die erste Bedingung ja so aussehen:
[mm] \exists [/mm] i [mm] \in [/mm] {0,1}
und da das Wort mit i enden muss, muss es ja mindestens einmal vorkommen, aber wenn es nur einmal vorkommt wäre dann die letzte Bedingung(count(i,w) mod2 = 0) erfüllt?
Wie sehen also die Wörter aus, die in dieser Sprache liegen?
> Desweiteren verstehe ich gerade nicht bei der Formulierung,
> ob alle anderen Woerter dennoch produzierbar sein muessen.
>
Was meinst du damit? "alle anderen Woerter" ?
Der Automat darf nur Wörter akzeptieren, die in der Sprache liegen.
> Habt ihr vielleicht einen Ansatz oder Tipp?
|
|
|
|
