| |
| Autor |
 Kontextfreie Grammatik in Chomsky Normalform |
|
jaytwistle
Neu 
Dabei seit: 06.02.2023
Mitteilungen: 2
 |  Themenstart: 2023-02-06
|
Guten Abend,
ich habe folgende Aufgabe:
Kontextfreie Grammatik:
S -> ySx | CA
A -> y | S
B -> xz | z | AB | C
C -> yx | B | Epsilon als leere Menge
Ich habe dann diese Grammatik schrittweise zur Chomsky Normalform konvertiert:
S -> VyX1 | CA
S' -> VyX1 | CA
A -> y | VyX1 | CA
B -> VxVz | z | AB | VyVx | y | VyX1 | CA
C -> VyVx | VxVz | z | AB | y | VyX1 | CA
X1 -> S'x
Vx -> x
Vy -> y
Vz -> z
Ist meine Lösung so korrekt?
|
 Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1418
Wohnort: Kiel, Deutschland
 | Beitrag No.1, eingetragen 2023-02-07
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Hallo jaytwistle, und willkommen auf dem Matheplaneten.
Das ist mit ziemlicher Sicherheit nicht korrekt.
1. Warum sind die rechten Seiten bei \(S\) und bei \(S'\) identisch?
2. Was hat die 1 zu bedeuten?
3. Schreibe \(V_x\) anstelle von Vx (und nutze außerdem das \(\varepsilon\)), dann ist das alles leichter zu lesen.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
jaytwistle
Neu
Dabei seit: 06.02.2023
Mitteilungen: 2
| Beitrag No.2, vom Themenstarter, eingetragen 2023-02-07
|
Vielen Dank für die Antwort.
Ich beginne nun mit dem ersten Schritt:
1. Eliminiere Regeln mit S auf der rechten Seite:
Deswegen wird S' eingeführt:
S -> S'
S' -> yS'x | CA
A -> y | S'
B -> xz |z | AB | C
C -> yx | B | Ɛ
2. Eliminiere jede Regel der Form A -> Ɛ:
S -> S'
S' -> yS'x | CA | A
A -> y | S'
B -> xz | z | AB | C | A
C -> yx | B
Ist bis hier alles korrekt?
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1418
Wohnort: Kiel, Deutschland
| Beitrag No.3, eingetragen 2023-02-07
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-02-07 10:17 - jaytwistle in Beitrag No. 2)
Ich beginne nun mit dem ersten Schritt:
1. Eliminiere Regeln mit S auf der rechten Seite:
Deswegen wird S' eingeführt:
S -> S'
S' -> yS'x | CA
A -> y | S'
B -> xz |z | AB | C
C -> yx | B | Ɛ
\quoteoff
Damit hast du nichts gewonnen.
Jetzt hast du zu Beginn eine Regel \(S \to S'\), und \(S\) taucht in keiner anderen Regel auf.
Damit kannst du die Regel \(S \to S'\) auch wieder streichen.
Danach sieht deine Grammatik exakt so aus wie am Anfang, nur dass das Startsymbol nicht mehr \(S\) heißt, sondern \(S'\).
Schreibe hier einmal auf, welche Schritte in welcher Reihenfolge du prinzipiell ausführen willst.
Ich bin der Meinung, dass wir hier kein separates Startsymbol \(S'\) brauchen.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
| jaytwistle hat die Antworten auf ihre/seine Frage gesehen. | | jaytwistle wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-03-27 00:20 U <
Wie unterstütze ich den Matheplaneten mit Geld?
