Reguläre Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass die folgenden Sprachen regulär sind, indem Sie deterministische endliche Automaten angeben, welche diese erkennen.
a)
[mm] $L_1 [/mm] = [mm] \{ w \in \Sigma_{\text{Bool}}^{\star} | w \text{ endet auf 01 } \}$
[/mm]
b)
[mm] $L_2 [/mm] = [mm] \{ 1^n0^m | n,m \in \mathbb N \wedge n+m \% 2 = 0 \}$
[/mm]
c)
[mm] $L_3 [/mm] = [mm] \{ w \in \Sigma_{\text{Bool}}^{\star} | w \text{enthält 11 genau 2 mal}\}$
[/mm]
Vorsicht: In 111 ist 11 auch zweimal enthalten!
d)
[mm] $L_4 [/mm] = [mm] \{ w \in \Sigma_{\text{Bool}}^{\star} | Zahlwert(w^R) > 2 \} [/mm] |
Hi Leute!
Ich hab hier dann mal einige DEA's entwickelt die hoffentlich stimmen. Vielleicht könntet ihr überprüfen ob die passen! Ich lad die DEA's als Bild hoch!
Allerdings habe ich zu b) gleich mal eine Frage. Diese Sprache zu der ich einen Automaten zeichnen soll, kann doch gar nicht regulär sein, oder? Weshalb ich dementsprechend auch gar keinen Automaten angeben kann, oder?
Genauso zur Aufgabe d). Wie versteht sich diese Sprache? Ich muss doch hier einen Automaten zeichnen, der mir den Zahlwert eines Binärwortes der echt größer 2 sein muss, erkennt. Nur wie entwickelt man das? Meiner Ansicht nach muss in diesem Wort auf jeden Fall das (Teil-)Wort "11" vorkommen. Dabei ist es normalerweise egal an welcher Stelle dieses steht. Auch wenn das Wort "alleine" kommt ist die Sprache erfüllt, da 11, auch von hinten gelesen, echt größer 2 ist. Stimmt doch so, oder?
Hier mal der Link zu den Automaten für a) und c): http://s1.directupload.net/file/d/2915/hwfqa2xe_jpg.htm
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 So 10.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
