Übungsblatt Automaten-Theorie

S

Seneca

Mitglied
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 ;)
 

Anhänge

  • uebung_26_10.pdf
    108,4 KB · Aufrufe: 36
Zuletzt bearbeitet von einem Moderator:
fastjack

fastjack

Top Contributor
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.
 
X

XHelp

Top Contributor
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.
 
S

Seneca

Mitglied
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:
 
Zuletzt bearbeitet:
ARadauer

ARadauer

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

Marcinek

Gast
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.
 
S

Seneca

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

SlaterB

Gast
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
 
M

Marcinek

Gast
Oha: Eine Frage, die man ernst nehmen kann.

Ja das ist korrekt.

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

XHelp

Top Contributor
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.
Code: 
aaba
erzeugen
 
M

Marcinek

Gast
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.
Code: 
aaba
erzeugen
Zum Vergrößern anklicken....

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

Marcinek

Gast
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!
 
Zuletzt bearbeitet von einem Moderator:
S

Seneca

Mitglied
@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
 
X

XHelp

Top Contributor
SlaterB hat dir doch schon die richtige Richtung bezeigt. Mit der Gramatik muss du folgendes erzeugen können:
haufenirgendwas1aaaahaufenirgendwas2
haufenirgendwas1babahaufenirgendwas2
Wobei haufenirgendwas auch leer sein kann.
 
M

Marcinek

Gast
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.
Zum Vergrößern anklicken....

:eek: 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
Zum Vergrößern anklicken....

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
 
X

XHelp

Top Contributor
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.
Zum Vergrößern anklicken....

Generell ja - auf die Aufgabe bezogen - nein.
Es muss eine reguläre Grammatik rauskommen, da gibt es bestimmt Vorgaben:
Zugelassen ist:
Code: 
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.
 
S

Seneca

Mitglied
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?
 
X

XHelp

Top Contributor
Weil es eine reguläre Grammatik ist (entspricht den Anforderungen), oder:
"Die Sprache lässt sich auch durch ein regulären Ausdruck angeben:
Code: 
a+b+
und reguläre Ausdrücke beschreiben immer eine reguläre Sprache"
 
S

Seneca

Mitglied
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? :D

S -> ababS
S ->aaaaS

Also das hier o_O
 
M

Marcinek

Gast
Diese Gramatik ist falsch. Siehe posting von XHelp ;)

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

Mal erstmal einen Automaten auf.
 
S

Seneca

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

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

XHelp

Top Contributor
Code: 
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 haufenirgendwasaaaahaufenirgendwas erzeugt.
Ansonsten: zeig mal den DFA, dann kann ich genauer sagen, was ich meinte.
 

Aktuelle Jobs

Neue Themen


Oben