Grammatik für Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | 1. Gegeben sei das Alphabet [mm] \Sigma [/mm] = {a, b, c}.
(a) Geben Sie einen endlichen deterministischen Automaten A an, der alle Wörter aus [mm] \Sigma^{\*} [/mm] akzeptiert, die genau drei "a" enthalten.
(b) Zeichnen Sie den zugehörigen Transitionsgraphen!
(c) Stellen Sie die zugehörige Übergangstabelle auf!
(d) Beschreiben Sie die akzeptierte Sprache durch einen regulären Ausdruck!
[...]
3. Geben Sie eine Typ-3-Grammatik an, die die Sprache L aus Aufgabe 1 erzeugt! |
Ersteinmal einen schönen guten Tag an alle!
Ich habe folgendes Problem:
Ich befinde mich gerade in der Klausurvorbereitung und ich muss gerade feststellen, dass ich doch das ein oder andere im Stoff nicht ganz so verstanden habe.
Aufgabe 1 habe ich gelöst und würde mich freuen, wenn mir jemand sagen könnte ob das so "richtig" ist.
1a)
A = (Q, [mm] \Sigma, \delta, [/mm] A, F), mit
Q = [mm] \{q_{0}, q_{1}, q_{2}, q,_{3}, q_{exil}\}
[/mm]
[mm] \Sigma [/mm] = {a, b, c}
F = [mm] \{q_{3}\}
[/mm]
b) Gehe ich jetzt mal von aus, dass das korrekt ist.
c)
[mm] \vmat{
\delta & q_{0} & q_{1} & q_{2} & q_{3}& q_{exil}
\\ a & q_{1} & q_{2} & q_{3} & q_{exil}& q_{exil}
\\ b & q_{0} & q_{1} & q_{2} & q_{3}& q_{exil}
\\ c & q_{0} & q_{1} & q_{2} & q_{3}& q_{exil}
}
[/mm]
d) REG: [mm] (b+c)^{\*}a(b+c)^{\*}a(b+c)^{\*}a(b+c)^{\*}
[/mm]
Jetzt zu 3 und da hörts bei mir leider auf.
Ich habe das mit den Grammatik anscheinend nicht richtig verstanden.
Eine Typ-3-Grammatik heißt doch, das sie rechtslinear sein soll, sprich: Nichtterminalsymbole stehen immer rechts.
Wenn dem so ist bekomme ich es einfach nicht diese Grammtik zu formulieren.
Mein Versuch: G = (N, T ,R, S), mit
N = {A, S}
T = {a, b, c}
R: S -> AaAaAaA
A -> bA | cA
Das wäre aber ja nicht mehr rechtlinear...
Für Hilfe wäre ich sehr Dankbar!
Mit freundlichen Grüßen
DerderSichsichnennt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:45 Di 28.07.2009 | | Autor: | daN-R-G |
Hallo erstmal!
Da ich leider nicht viel Zeit habe, da ich morgen selber ne etwas haarige Klausur schreibe, sage ich einfach mal kurz und knapp, was mir so auffällt:
Zu a) Ohne die Übergangsfunktion zu definieren, hast du keinen endlichen Automaten erstellt. (Auch wenn du sie in b) und c) auf andere Art und weise theoretisch darstellst.)
Ich als Korrekteur würde zumindest ankreiden, dass das wichtigste fehlt ;)
Zudem, ums formal auch wirklich korrekt zu machen, müsstest du schon sagen, dass q0 dein Anfangszustand sein soll (sofern er das ist)
Zu b) Kann ich nicht beurteilen
Zu c) Leider keine Zeit, mir die Tabelle jetzt zu visualieren. Sorry :/
Zu d) Stimmt so!
Zu der Grammatik... mal überlegen. Mein Gedächnis ist momentan blockiert für alte Sachen ;)
Z.B. in die Richtung von
S -> aA | bS | cS
A -> aB | bA | cA
B -> aC | bB | cB
C -> bC | cC | b | c | [mm] \epsilon
[/mm]
So ungefähr könnte das aussehen. Es gibt immer viele Wege.
Aber Ja: Die Typ-3-Grammatik darf auf der rechten Seite nur ein Terminal bzw ein Terminal + Nichtterminal (manchmal auch Nichtterminal + Terminal) haben. Je nachdem, wie man es definiert.
Auf der linken Seite dürfen nur Nichtterminale stehen.
|
|
|
| |
|
Guten Morgen und ersteinmal Danke für deine Mühe!
zu 1a) Ok, Übergangsfunktion und Startzustand habe ich beide nicht mit aufgeführt, da die für mich klar waren. Aber du hast natürlich Recht die müssen mit dahin!
zu c) Schade ;)
zu 3) Puh, das ist mal ne Idee! Da wäre ich gestern glaub ich nie drauf gekommen!
Deine Antwort hat mir sehr geholfen, nochmals vielen Danke und viel Erfolg für deine Klausur ;)
MfG
DerdersichSichnennt
|
|
|
|
