# Übungsblatt Automaten-Theorie



## Seneca (1. Nov 2010)

Hallo Community 

Ich bräuchte Hilfe zu folgendem Übungsblatt, speziell zur ersten Aufgabe, bin nämlich im Thema Grammatik nicht so bewandert ???:L

Danke für eure Hilfe


----------



## Marcinek (1. Nov 2010)

Und was ist deine Frage?


----------



## fastjack (1. Nov 2010)

Was soll man sagen, das sind die "Grundlagen der theoretischen Informatik" (bei Amazon gibt es ein passendes Buch dazu mit demselben Titel). Automatentheorie ist genau das richtige für kalte Winterabende und Wochenenden. Du sollst halt Ausprobieren, Beweisen und Automaten malen (Zustände als Kreise und die dann mit Übergängen verbinden). Knobelei und ein Hauch Voodoo 

Wenn Du mit dem Thema nicht so bewandert bist, würde ich mir auf jeden Fall das Buch holen.

P.S.: Es gibt ein Matheforum (Matheplanet oder so), da gibt es spezielle Unterforen zur theoretischen Informatik.


----------



## XHelp (1. Nov 2010)

Wenn wir schon bei der Buchempfehlungen sind, würde ich dir eher "Theoretische Informatik - kurzgefasst" vom Schöning empfehlen. Aber ich denke nicht, dass man sich ein Buch über TI kaufen solte, nur um DFA/NFA zu verstehen. Dazu gibt es bestimmt genügen Artikel im Internet.

Falls du konkrete Fragen zu den Aufgaben hast, oder deine Lösung abgleichen willst, kannst du die ja stellen. Aber ich denke nicht, dass dir wer die Aufgaben einfach so rechnen wird. Zumal die Aufgaben nicht all zu schwer sind.


----------



## Seneca (9. Nov 2010)

Hallo, ich bräuchte nochmal Hilfe bei folgendem Arbeitsblatt 

Speziell die Aufgabe 2b, ist folgendes da richtig:

X={a,b} N={S,V}

S->bS
S->aS
S->aV
S->bV
V->a

Wenn nicht, was genau ist falsch? 

Und dann noch Hilfe bei dem Automaten, wie hat der auszusehen?


S0 - b - S1 - a - S2 - b - S3 - a - S4(endzustand) 
|
S5(Pfeil a und endzustand)

So ungefähr?

Danke schonmal vielmals für eure Hilfe, die Buchtipps beherzige ich :toll:


----------



## ARadauer (9. Nov 2010)

was spiegelt sich da in dem Foto? Ist das ein Geist?
Wenn es Möpse wären, hättest du deine Antwort warscheinlich schon ;-)


----------



## Seneca (9. Nov 2010)

Das sind Hände die eine Kamera halten 

Aber wenn's hilft: Ja, sind Möpse, schön und prall


----------



## Marcinek (9. Nov 2010)

Lol.

Deine Lösung für 2b soll einfach 1a abgeschrieben sein?

Sehe ich auf 100 km, dass die auch zich andere Wörter erzeugt.


----------



## Seneca (9. Nov 2010)

Okay, ich sehe das auf 10cm Nähe nicht, aber okay, bin da auch nicht so bewandert 
Könntest du mir bitte ein wenig unter die Arme greifen? Und achja, ist folgender Automat richtig bei der 1?


----------



## SlaterB (9. Nov 2010)

2b ist eine Sprache die irgendein konkretes Wort enthalten soll,
wieso bauchst du dann nicht direkt eine Gramatik-Regel a la
S -> Sabab
ein?

zu deinem Vorschlag
S->bS
S->aS
S->aV
S->bV
V->a
kann man nicht sagen das irgendwas bestimmtes falsch ist, es ist einfach nur ohne jede Ähnlichkeit zur Aufgabe

was soll der Werken-Lehrer sagen, wenn das Kind eine Hundehütte statt des geforderten Vogelhauses baut?

der Automat dagegen geht in die richtige Richtung, gut 
falls man an den Übergang auch abab schreiben kann reichen weniger Knoten


----------



## Marcinek (9. Nov 2010)

Oha: Eine Frage, die man ernst nehmen kann.

Ja das ist korrekt. 

Falls unter endlicher Sutomat auch ein nichtdeterministischer endlicher Automat fällt.


----------



## XHelp (9. Nov 2010)

Naja, sofern es ein DFA sein muss, fehlt dir noch ein Fangzustand. Du kannst ja auch in S ein "b" einlesen.
Deine Lösung für 2b ist falsch. Damit kannst du z.B. 
	
	
	
	





```
aaba
```
 erzeugen


----------



## Marcinek (9. Nov 2010)

XHelp hat gesagt.:


> Naja, sofern es ein DFA sein muss, fehlt dir noch ein Fangzustand. Du kannst ja auch in S ein "b" einlesen.
> Deine Lösung für 2b ist falsch. Damit kannst du z.B.
> 
> 
> ...



Wenn es ein DFA sein soll, dann muss der zwischen Knoten da weg und kein neuer hin


----------



## Seneca (9. Nov 2010)

SlaterB hat gesagt.:


> 2b ist eine Sprache die irgendein konkretes Wort enthalten soll,
> wieso bauchst du dann nicht direkt eine Gramatik-Regel a la
> S -> Sabab
> ein?



War mit bis dato nicht bewusst, dass das überhaupt möglich ist 

Wie hat das denn konkret zu laufen, vllt. 'ne Anfangshilfe? 

@Marcinek

Ich glaube das ist so.


----------



## XHelp (9. Nov 2010)

Marcinek hat gesagt.:


> Wenn es ein DFA sein soll, dann muss der zwischen Knoten da weg und kein neuer hin



Hast recht, hab nicht aufmerksam geguckt.


----------



## Marcinek (9. Nov 2010)

Bei 1b)

Um die Sprache zu klassifizieren musst du alle möglichen Wörter angeben.

a hoch x bedeutet, dass sich a x mal wiederholen kann. Dann kann man sagen, dass x > 0; x >= 0 oder x = 2* iwas anderes..

Meine Lösung für 2b war müll!


----------



## XHelp (9. Nov 2010)

Marcinek hat gesagt.:


> Also bei 2b hast du genau 2 Worte
> 
> Ergo kommt da sowas bei Raus
> 
> ...



Öhm, nö? bbbbbbbbbbbbbbbababbbbbbbb ist in der Sprache bbabab ist in der Sprache bbbbbaaaabbbbbb ist in der Sprache usw... Das Wort muss "aaaa" oder "baba" enthalten und nicht nur daraus bestehen.


----------



## Seneca (9. Nov 2010)

@xHelp

Danke, genau das ist mein Problem, es gibt einfach sauviele Wörter die das enthalten und ich habe null Ahnung wie man das einschränkt ???:L


----------



## XHelp (9. Nov 2010)

SlaterB hat dir doch schon die richtige Richtung bezeigt. Mit der Gramatik muss du folgendes erzeugen können:
_haufenirgendwas1_*aaaa*_haufenirgendwas2_
_haufenirgendwas1_*baba*_haufenirgendwas2_
Wobei haufenirgendwas auch leer sein kann.


----------



## Marcinek (9. Nov 2010)

XHelp hat gesagt.:


> Öhm, nö? bbbbbbbbbbbbbbbababbbbbbbb ist in der Sprache bbabab ist in der Sprache bbbbbaaaabbbbbb ist in der Sprache usw... Das Wort muss "aaaa" oder "baba" enthalten und nicht nur daraus bestehen.



 Ich hasse TI.



Seneca hat gesagt.:


> @xHelp
> 
> Danke, genau das ist mein Problem, es gibt einfach sauviele Wörter die das enthalten und ich habe null Ahnung wie man das einschränkt ???:L



Du musst dir sowas überlegen

Du hast ein Prefix, der aus a uns bs bestehen kann und ein Suffix, der egal ist

Also PREFIX aaaa oder ababa SUFFIX

Dann musst du das iwie in Regeln fassen

S -> PREFIX aaaa SUFFIX 

S -> ...

Und dann PREFIX -> a PREFIX und PREFIX -> b PREFIX und PREFIX -> a | b | epsilon

Dann kannst du dir überlegen, dass PREFIX = SUFFIX ist und entsprechend umbenennen.

Feddich


----------



## XHelp (9. Nov 2010)

Marcinek hat gesagt.:


> Dann musst du das iwie in Regeln fassen
> S -> PREFIX aaaa SUFFIX
> S -> ...
> Und dann PREFIX -> a PREFIX und PREFIX -> b PREFIX und PREFIX -> a | b | epsilon
> Dann kannst du dir überlegen, dass PREFIX = SUFFIX ist und entsprechend umbenennen.



Generell ja - auf die Aufgabe bezogen - nein.
Es muss eine reguläre Grammatik rauskommen, da gibt es bestimmt Vorgaben:
Zugelassen ist:

```
X -> aY
//oder
X -> Ya
X -> a
X -> epsilon
```
Die epsilon-Regen muss hier Definitiv zum Einsatz kommen, da PREFIX und SUFFIX auch leer sein können.

Es lohnt sich also zunächst einmal ein DFA zu basteln, dann fällt auch das Aufstellen der Grammatik leicher.


----------



## Seneca (9. Nov 2010)

Okay, danke es wird klarer, noch eine kleine Frage 

Aufgabe 1a, wieso ist die Sprache regulär? Bei einer regulären Grammatik dürfen nur Regeln der Form "ab" oder "ba" auftauchen?


----------



## XHelp (9. Nov 2010)

Weil es eine reguläre Grammatik ist (entspricht den Anforderungen), oder:
"Die Sprache lässt sich auch durch ein regulären Ausdruck angeben: 
	
	
	
	





```
a+b+
```
 und reguläre Ausdrücke beschreiben immer eine reguläre Sprache"


----------



## Seneca (9. Nov 2010)

Okay, danke.

Jetzt kann mir bitte einer sagen, wie die Grammatik für Aufgabe 2b aussieht? Vielleicht muss ichs gesehen haben um es zu verstehen? 

S -> ababS
S ->aaaaS

Also das hier


----------



## Marcinek (9. Nov 2010)

Diese Gramatik ist falsch. Siehe posting von XHelp 

Es wurden bereits Lösungsansätze geschrieben...

Mal erstmal einen Automaten auf.


----------



## Seneca (9. Nov 2010)

Hab ich hier vorliegen, aber die Grammatiksache macht mich nervlich fertig 

Also wer kann mir bitte helfen?  Nur den Anfang? Die ersten zwei? Bitte.


----------



## XHelp (9. Nov 2010)

```
G=({S,A,B,C,D},{a,b},P,S), wobei P=
{
S -> aS
S -> bS
S -> aA
A -> aB
B -> aC
C -> aD
D -> aD
D -> bD
D -> epsilon
}
```
Das wäre (spontan gesagt) eine reguläre Grammatik, dir dir _haufenirgendwas_*aaaa*_haufenirgendwas_ erzeugt.
Ansonsten: zeig mal den DFA, dann kann ich genauer sagen, was ich meinte.


----------

