Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:34 Di 29.06.2010 | | Autor: | rml_ |
| Aufgabe | Entwerfen Sie nichtdeterministischen endliche Automaten, welche folgende Sprachen erkennen:
(a) L1 = {w [mm] \in \sum_{Bool^*} [/mm] , 1010 ist kein teilwort von w}
Bool j 1010 ist kein Teilwort von wg
(b) L2 = {w [mm] \in \sum_{Bool} [/mm] , w = [mm] w^R [/mm] + [mm] \begin{vmatrix}
w
\end{vmatrix} \le [/mm] 3}
|
kann mir jemand erklären wie das funktioniert?
bei b, hab ich so probleme was heißt [mm] w^R? [/mm]
bei a muss ich ja nur einen automaten schreiben der alles erkennt außer 1010 oder?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:28 Di 29.06.2010 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Moin
> Entwerfen Sie nichtdeterministischen endliche Automaten,
> welche folgende Sprachen erkennen:
> (a) L1 = {w [mm]\in \sum_{Bool^*}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
, 1010 ist kein teilwort von
> w}
> Bool j 1010 ist kein Teilwort von wg
Findest du das sehr leserlich?
> (b) L2 = {w [mm]\in \sum_{Bool}[/mm] , w = [mm]w^R[/mm] + [mm]\begin{vmatrix}
w
\end{vmatrix} \le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
3}
>
> kann mir jemand erklären wie das funktioniert?
Wie was funktioniert? Wie man einen Automaten bastelt? Nun, wie das Wort sagt: basteln. Probier rum, uebeleg dir was passiert, ...
> bei b, hab ich so probleme was heißt [mm]w^R?[/mm]
Das ist das Wort $w$ rueckwaerts.
> bei a muss ich ja nur einen automaten schreiben der alles
> erkennt außer 1010 oder?
Nein. Er darf 11010 auch nicht erkennen. Er darf kein Wort erkennen, welches die Zeichenkette 1010 enthaelt. Das ist uebrigens genauso schwierig/einfach zu basteln wie ein Automat, der Woerter erkennt, die die Zeichenkette 1010 enthaelt.
LG Felix
|
|
|
|
