Kellerautomaten und reguläre Sprachen |
| 26.06.2016, 00:39 | Auf diesen Beitrag antworten » |
| nenam | Kellerautomaten und reguläre Sprachen Hallo, ich bin sehr verzweifelt und hänge an einem Übungsbeispiel, die 100% so ähnlich zur Klausur nächste Woche kommen wird. Ich hoffe ihr könnt mir helfen. Sei L eine kontextfreie formale Sprache über dem Alphabet T u {c} mit c kein Element von T wie folgt definiert: L = {h(w)^R cw| w element aus T*}; wobei gilt, dass h(x) = cx für alle x element aus T . (c) Geben Sie einen Kellerautomaten M an, und zwar als Rewrite- System M = (V; Q; T u {c} ;R;A)), der L akzeptiert, wobei V = {c; p; q; r;Z0;Z2} u T, Q = {p; q; r}, A = {(Z0p;Z2)}. (d) Die Famile der regulären Sprachen ist gegenüber beliebigen gsm- Abbildungen abgeschlossen. Zeigen Sie unter Verwendung dieser Abschlusseigenschaft, dass L nicht regulär sein kann, indem Sie eine geeignete gsm M mit maximal 4 Zuständen (der vierte Zustand ist der Endzustand) konstruieren, die L auf die bekannte nicht-reguläre Sprache {a^nb^n|n <=0} abbildet. Geben Sie die gsm M sowohl graphisch als auch mit einer formalen Beschreibung (beachten Sie, dass in diesem Fall nur drei Zustände erforderlich sind) an. |
|
|
|
| 26.06.2016, 08:03 | Auf diesen Beitrag antworten » |
| ed209 | Hi Woran hakt es? Kannst du mit eigenen Worten informell wiedergeben aus was fuer Woertern L besteht? Gruss, ED |
| 26.06.2016, 14:03 | Auf diesen Beitrag antworten » |
| nenam | Die Angabe wurde allgemein erfasst. Ich habe es so verstanden: c ist der Trennwort. Da Homomorphismus gegeben ist und auf dem reverse angewendet wird, habe ich es so an einem Bsp angewendet: Beispielwort: wort tcrcocwc cwort wäre die Ausgabe. Grammatik: Produktion mit Greibachnormalform: G(L) = (N u T u {c} ; T u {c} ; P; S) P = {S -> xCSX; S ->c; C -> c; X->x |x ist element T} Bei mir hängt es besonders an dem Verständnis. Bei d) habe ich überhaupt keinen Ansatz. |
| 27.06.2016, 19:31 | Auf diesen Beitrag antworten » |
| nenam | (c) Geben Sie einen Kellerautomaten M an, und zwar als Rewrite- System M = (V; Q; T u {c} ;R;A)), der L akzeptiert, wobei V = {c; p; q; r;Z0;Z2} u T, Q = {p; q; r}, A = {(Z0p;Z2)} Ich habe versucht den Kellerautomaten zu erstellen. Hier ist meine Lösung: X wird als Kellersymbol verwendet. p,x,Z0 -> q,XZ0 p,x,X -> q,XX p,c,X -> r,X q,c,X -> p,X r,x,X -> r, Leerwort r,Z2,Epsilon -> r,Z0 r,Z2,Z0 -> Lambda Ich würde gerne wissen, ob das so passt? |
| Anzeige | |
|
|
|
| 28.05.2018, 01:11 | Auf diesen Beitrag antworten » |
| Lisa97 | RE: Kellerautomaten und reguläre Sprachen Hallo nenam, hast du die Aufgabe letztendlich gelöst und hast du noch die Lösungen? Ich habe ein sehr ähnliches Beispiel und habe auch Schwierigkeiten 
|
|
|
