Automaten

[sashpta]

Hey
ich glaub ich bin hier in dem "Unterforum" falsch aber ich weiß nicht wo ichs sonst rein schreiben soll
Ich schreib morgen ne Arbeit in Info über Automaten (12. Klasse Informatik Q3), wir bekommen nen Automaten und müssen dazu die Sprache, Grammatik und Regeln aufschreiben. Das mit der Grammatik und den Regeln klappt auch ganz gut, auch das Zeichnen von nem Automaten,falls wir das alles gegeben haben. Aber wenn ich die Sprache herausfinden muss habe ich immer riesen Probleme :/
Der Lehrer meinte wir sollen uns am Besten erst ein paar "Wörter" schreiben um dann damit die Sprache herauszufinden. Aber ich komme trotzdem nie dadrauf.
Habt ihr vielleicht ein paar Tipps dafür? (Ja ich weiß ist super knapp aber ist mir eben erst eingefallen, dass ich hier ja mal fragen könnte )

wir müssen das halt so aufschreiben können (siehe Bild (L = Sprache, G = Grammatik, R = Regel)

Danke schon mal.
MFG

[sashpta]

Habe mir eben mal die Übungsaufgaben angeguckt.

Aufgaben(Anhang: Aufgaben.png)
Lösungen(Anhang: Lösungen.png)

Bei Aufgabe 1:
Warum ist G auf einmal das was vorher R war?
Woher weiß er was er da schreibt? Ich hab da keinen Durchblick und schon gar nicht wenn ich in die Lösungen gucke. :/
Warum steht da auf ein mal (in den Lösungen) ein T mit Index und Hochzahl?

Aufgabe 2:
Da steht ja "L = {a^m b^n a^n b^m ; m, n ∈ N}"
so das N steht schon mal dafür dass "n" eine natürliche Zahl sein muss, aber zählt das auch für das "m"?
wenn ja: warum gibt es dann "a^m" und "a^n" (das gleiche mit b) wenns doch eh das selbe ist?
das "a^n" heißt doch eigentlich nur, dass "a" mindestens ein mal vorkommen muss oder? -> a^0 = 1
und dass "a" endlich ist oder?
dann bei den Lösungen zur 2:
da steht ja
"S -> ∈|S1|S2"
wofür steht das ∈ hier?
man kann hier ja auswählen, ob man in S1 oder S2 rein geht (oder in ∈????)
dann "S1 -> aS1b|aS2b|ab"
hier kann man in "ab" gehen und ist fertig und schreibt "ab", oder
man geht in "aS1b", dann schreibt man ein "a" und geht dann in "S1" und schreibt dann ein b und kann weiter auswählen(oder?).
dann gibt's noch "S2 -> bS2a|ba"
wenn man in "ba" geht ist man wieder fertig schreib aber "ba", man kann aber auch in
"bS2a" gehen, dann schreibt man ein "b", geht in "S2" und dann schreibt man ein a.
jedoch kommt man aus "S2" nicht mehr raus, sobald man ein mal da drinen ist, außer man macht fertig (mit "ba")
Hab ich das so richtig verstanden?

Woher weiß ich haber jetzt, dass das die richtige Grammatik (oder Regel? Was ist das denn nun?) für die (oben angegebene) Sprache ist?


Ich blick hier echt kein bisschen mehr durch. :/ wir haben das das letzte Mal vor 4 Wochen gemacht und jetzt hat keiner mehr ne Ahnung wies geht. (mal abgesehen davon fanden wirs vorher schon übel schwer aber hatten wenigstens nen Ansatz )


Ich hoffe ihr könnt mir helfen.

MFG

[Xin]

Hey

Ich schreib morgen ne Arbeit in Info über Automaten (12. Klasse Informatik Q3), wir bekommen nen Automaten und müssen dazu die Sprache, Grammatik und Regeln aufschreiben.

In Anbetracht der fortgeschrittenen Uhrzeit und der Tatsache, dass Du den Text erst nach der Arbeit lesen würdest, schreibe ich jetzt keinen großen Text mehr.

Gucken wir uns kurz Aufgabe 1 an: Du hast das Wort aaabbbcc und willst wissen, ob es in der Sprache enthalten ist.
Wir starten (S) also. S können wir mit Xabc, XaAbc, abc oder aAbc ersetzen. Also tun wir das.
Als nächstes ersetzen wir alle "Großbuchstaben weiter: Xabc hat zwei Möglichkeiten: Xaabc oder aabc. Für XaAbc haben wir ebenso drei Möglichkeiten: Das ersetzen von X führt zu XaAbc und aaAbc. Tauschen wir bei XaAbc das A aus, so erhalten wir XabAc. Bei abc können wir nichts austauschen und bei aAbc lässt wieder Ab auftauchen und durch bA ersetzen: abAc.
Wir haben also die nächste Reihe möglicher Worte. Das gesuchte Wort ist noch nicht dabei.
Also lösen ersetzen wir in den neuen Worten wieder die "Großbuchstaben".

Hoffe, das hilft für die Arbeit noch. Weiteres morgen, falls es nach der Arbeit noch interessiert.

[sashpta]

Oke vielen Dank ich schreib erst um 15 Uhr hab also noch bisschen Zeit
Also eigentlich schreib ich einfach alle Wörter die ich kann und guck dann obs dabei ist oder?

Wie ist sas denn wenn ich z.B. Z1 ->aZ2b habe und Z2 ->C
Der schreibt dann das a, geht in Z1, wählt was aus schreibt der dann das B oder erst das C?

[Xin]

Oke vielen Dank ich schreib erst um 15 Uhr hab also noch bisschen Zeit
Also eigentlich schreib ich einfach alle Wörter die ich kann und guck dann obs dabei ist oder?

Genau, Du ersetzt in jeder Iteration jede Variable/Nichtterminalsymbol einmal. Daraus ergeben sich die Worte der nächsten Iteration. Steht Dein Wort drin, bist Du fertig. Falls nicht, machst Du eine neue Iteration.
Eine Regel wie "X -> Xa | epsilon" führt dazu, dass Du beliebig viele a an der Stelle hast. Wenn Dein Wort also aaabbcc ist, dann kannst Du "Xbc" bis aaabc, aber das wird sich nie auf aaabbcc expandieren, sofern sich da keine Regel aaaaaab -> Xbbcc" mehr ergibt.
Ansonsten: Wenn alle Worte nur noch aus Terminalsymbolen bestehen, ist definitiv schluss.

Wie ist sas denn wenn ich z.B. Z1 ->aZ2b habe und Z2 ->C
Der schreibt dann das a, geht in Z1, wählt was aus schreibt der dann das B oder erst das C?

Ich verstehe die Frage nicht (Kommasetzung rettet Leben - und hilft auch sonst ).

Was ist Dein Startwort? Oder womit möchtest Du vergleichen?
Welches B? (b != B). Du musst mit den Symbolen sehr exakt sein. Das hier ist Informatik, ein Computer denkt nicht, der macht einfach, was Du schreibst.

Wenn Dein Wort mit a beginnt, kannst Du nur Z1 als gültige Regel anwenden, wenn nach dem a auch die Regel Z2 gültig ist und ein b folgt. Nach dem a muss also C folgen. Ich vermute C sollte auch keine Regel sein, sondern c?
Wenn das a also gelesen wurde, muss Regel Z2 -> c gültig sein. Das funktioniert bei allen Worten, die mit ac beginnen. Regel Z1 ist gültig, wenn das Wort acb ist oder mit acb beginnt. Das Wort acba kannst Du also auf Z1a zusammen kürzen. Wenn Z1a sich mit Deinem Startwort erzeugen lässt, ist das Wort gültig.

[sashpta]

Ja sry habs am Handy geschrieben da hab ich nicht auf die Groß-und Kleinschreibung und die Kommas geachtet^^

Also ich meinte das komplett separat von der Aufgaben
Angenommen man hat die Zustände Z1 und Z2 gegeben und die Symbole a,b,c
Wenn man dann z.B.
Z1 -> aZ2b hat
Und Z2 -> cZ1|a hat
Und man bei Z1 anfängt
Dann wird ja
a geschrieben, dann ist man in Z2, und wählt dort was aus. Wenn man dort cZ1 auswählt hat man a c stehen und ist in Z1(hat aber b noch b vom Ersten). Dann wählt man in Z1 wieder aZ2b also hat man mitlerweile
a c a stehen und 2 mal b vom Z1.
Dann wählt man Z2 -> a und hat am Ende
a c a a b b
Stehen oder kommen die b's früher?

Und wie geht das bei Nr 2?

[Xin]

Angenommen man hat die Zustände Z1 und Z2 gegeben und die Symbole a,b,c
Wenn man dann z.B.
Z1 -> aZ2b hat
Und Z2 -> cZ1|a hat
Und man bei Z1 anfängt
Dann wird ja
a geschrieben, dann ist man in Z2, und wählt dort was aus. Wenn man dort cZ1 auswählt hat man a c stehen und ist in Z1(hat aber b noch b vom Ersten). Dann wählt man in Z1 wieder aZ2b also hat man mitlerweile
a c a stehen und 2 mal b vom Z1.
Dann wählt man Z2 -> a und hat am Ende
a c a a b b
Stehen oder kommen die b's früher?

Nein, die b's kommen hinter Z2, darum stehen sie ja auch hinter Z2. Stell es Dir wie Autos vor, die in einer Reihe parken.
Z1 -> Vorne steht audi, dann parken Z2 Autos und dahinter parkt ein bmw.
Z2 ist entweder ein audi oder es ist ein citroen, hinter dem wieder ein audi, dann Z2 Autos und ein BMW steht. Du hast Dich in Deinem Beispiel für einen Audi entschieden. Also steht da audi, citroen, audi audi, bmw, bmw. acaabb.

[Xin]

Und wie geht das bei Nr 2?

Die Sprache sagt, dass m viele a's kommen, dann n viele b, n viele a und anschließend wieder m viele b.
Also (audi audi) (bmw) (audi) (bmw bmw).

Die mittlere Sache ist einfach:
N -> ba | b N a -> vorne steht ein BMW, dahinter ein Audi. dazwischen könnten wieder ein BMW und ein Audi stehen.
Vielleicht gibt es aber auch gar nix zwischen Audi und BMWs (also der äußeren Anzahl von Autos, die mit m beschrieben wird):
N -> ba | b N a | Epsilon
Ähnlich sieht das für M aus:
M -> ab | a M b
Dazwischen könnten aber auch die N Regel gelten, also packen wir die dazu:
M -> ab | a M b | a N b
Wir haben aber auch die Möglichkeit, dass m 0 ist, aber N gültig ist.
M -> ab | a M b | a N b | Epsilon | N

Wir können den Start jetzt so definieren, dass er die m=0 und n=0 Fälle mitbehandelt.
S -> M | N | Epsilon
M -> ab | a M b | a N b
N -> ba | b N a

N Regelt die Autos in der Mitte, M die Autos außen, wo zusätzlich auch Autos dazwischen stehen können, S klärt die Fälle, falls m=0 ist oder m und n = 0 sind.

[sashpta]

Oke vielen Dank, was ist das N? Wo nimmst du das denn her?

[Xin]

Oke vielen Dank, was ist das N? Wo nimmst du das denn her?

N ist das Nichtterminal-Symbol, die Regel, die das a^n b^n beschreibt. In der Lösung heißt es S2.

Wie sit Deine Klausur gelaufen?