Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
50 Aufrufe

Hallo,

die Lösung zur Aufgabe 29 c) ist folgende:

G=(N,T,P,S)

N={S,A}

T={0,1}

P={ S -> 0A | 1S1,

A -> 0S |1A | 0 }

Mir ist bewusst wie man bei der Produktion auf das "Unterstrichene" kommt: Dort bekommt doch der Knoten S2 theoretisch die Bezeichnung S und dem Knoten S1 wird die Bezeichnung A zugeordnet? Und somit kann man alles weitere aus dem Endlichen Automaten ablesen.

Wie kommt man aber von dem Endlichen Automaten auf die fett markierten Zahlen 1 und 0 in der Produktion?

Vielen Dank im Voraus!

in Band I, Kapitel 4 von uuiya uuiya Lernwillige(r) (680 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort
Hallo,

du schreibst schon ganz richtig, dass S2 dem S und S1 dem A entspricht. Das Wort muss aber irgendwann enden (wenn das Wort in S2 ist/landet), ohne die fettgedruckten wären alle Worte unendlich lang und damit die Sprache falsch. Das Wort endet entweder mit einer 1 (dann muss es vorher im Zustand S/S2(/S0) gewesen sein) oder es endet mit einer 0, dass heißt, es muss vorher im Zustand A/S1 gewesen sein und die letzte 0 sorgt wieder für eine gerade Anzahl.

Der Knoten S0 ist in S integriert (kommt eine 1 bleibt man im Zustand oder das Wort ist bereits zu Ende, oder es kommt eine 0 und man wechselt in A. S-->lambda geht nicht, da S0 kein Endzustand ist).

Ich hoffe es ist nun klarer, wenn nicht schreibe einfach nochmal.

Viele Grüße und viel Erfolg beim Lernen

Anne (Tutorin)
von uvlwv uvlwv Eins-Komma-Null-Anwärter(in) (5.2k Punkte)  
ausgewählt von uuiya uuiya
0 0
Hallo,

ja ergibt alles Sinn. Dankeschön!
Probiert man generell den Knoten S0 in einen anderen zu integrieren?


Es gibt ja keine richtige Vorgehensweise oder Algorithmus um eine Grammatik zu erzeugen. Ich probiere meist mir anhand eines Endlichen Automaten die richtige Grammatik herzuleiten.
Ist das generell empfehlenswert oder gibt es noch andere "Tricks"/Vorgehensweisen die du eher empfehlen würdest?

Viele Grüße
0 0
Sich die Grammatik anhand des Endlichen Automaten herzuleiten ist ein guter Weg. Je nachdem kann man sich auch überlegen, welche Wörter der Automat allgemein zulässt (in dieser Aufgabe z.B. eine gerade Anzahl von 0en) und dann zu überlegen, wie man das mit einer Grammatik schafft (hier mit 2 Zuständen, die die Anzahl der 0en zeigt, ob sie gerade oder ungerade ist).

Allgemein kann man nicht sagen, dass S0 in einen anderen Zustand integriert werden soll. In dieser Aufgabe ergibt es Sinn, da man S0 nur benötigt, damit lambda nicht zur Sprache gehört, aber danach kommt man nie wieder zum Zustand S0. Ist S0 ein Endzustand oder führen Pfeile zum Zustand S0 kann man ihn nicht einfach integrieren. Es kommt also auf den Automaten an.

Insgesamt ist der beste Weg einfach zu üben (was du ja offensichtlich schon machst). Dann sieht man hoffentlich schneller ein Schema hinter dem Automaten und kann die Aufgabe gut lösen.
Vorgehensweise wie in VL?
...