Informatiker Board | Theoretische Informatik | Eine Kontextfreie Sprache zur CNF

Informatiker Board » Themengebiete » Theoretische Informatik » Eine Kontextfreie Sprache zur CNF » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge

Jupi

@Tobias

Besten Dank (7 Jahre später und immer noch aktuell)
Gott

foogi

Zitat:

Original von Tobias
......
Eliminieren von $[latex]A \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; \varepsilon[/latex]$

Eliminieren von $[latex]C \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; c[/latex]$

Nun führen wir für jedes Terminalsymbol [latex]a[/latex]

ein Nichtterminalsymbol [latex]X_a[/latex]

ein und ersetzen es überall dort, wo es gemischt mit Nichtterminalsymbolen vorkommt. Außerdem ergänzen wir die Regel $[latex]X_a \to a[/latex]$ .

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aAX_b \; | \; X_aX_b[/latex]$ hmm wieso hast du eigentlich ab ersetz? weil oben hast du ja erwähnt, das nur diejenigen ersetzt werden, die gemischt sind? oder hab ich das falsch verstanden?
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Regel $[latex]A \to X_aAX_b[/latex]$ besteht aus drei Nichtterminalen. Das umgehen wir, indem wir einfach eine neue Produktion $[latex]Y \to AX_b[/latex]$ ergänzen und dann substituieren: $[latex]A \to X_aY[/latex]$ . Dieses Verfahren kann man ggf. mehrfach anwenden.

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Produktion $[latex]S \to A[/latex]$ eliminieren wir, indem wir einfach die Produktionen von A zu S überleiten: $[latex]S \to X_aY | \; X_aX_b[/latex]$ .

Ebenso verfahren wir mit $[latex]S \to C[/latex]$ : $[latex]S \to X_cC \; | \; c[/latex]$

Wir erhalten also:
$[latex]S \to AC \; | \; X_aY | \; X_aX_b \; | \; X_cC \; | \; c \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Das sollte es sein (hoffe ich).

achja dann wollte ich noch wissen:
wir haben ja folgendes eliminiert:
- Löschregeln
- Nutzlose Symbole

haben wir hier im Beispiel keine Kettenregel gehabt?
Hast du vielleicht ein einfaches Beispiel für eine Kettenregel, und wie man diese entfernt?

Deine Erklärung finde ich sehr gut.. Augenzwinkern

Tobias

Ok, also zuerst machen wir deine Grammatik Epsilon-frei. Da du Epsilon ableiten kannst muss es auf jeden Fall die Produktion $[latex]S \to \varepsilon[/latex]$ geben. Diese ist aber in CNF meines Wissens erlaubt.

Man entfernt das Epsilon durch eine einfache Regel:
Wird ein Nichtterminal A auf Epsilon abgeleitet, so ergänzen wir überall, wo A auf der rechten Seite vorkommt eine Regel, die A nicht enthält.

Eliminieren von $[latex]A \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; \varepsilon[/latex]$

Eliminieren von $[latex]C \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; c[/latex]$

Nun führen wir für jedes Terminalsymbol [latex]a[/latex]

ein Nichtterminalsymbol [latex]X_a[/latex]

ein und ersetzen es überall dort, wo es gemischt mit Nichtterminalsymbolen vorkommt. Außerdem ergänzen wir die Regel $[latex]X_a \to a[/latex]$ .

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aAX_b \; | \; X_aX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Regel $[latex]A \to X_aAX_b[/latex]$ besteht aus drei Nichtterminalen. Das umgehen wir, indem wir einfach eine neue Produktion $[latex]Y \to AX_b[/latex]$ ergänzen und dann substituieren: $[latex]A \to X_aY[/latex]$ . Dieses Verfahren kann man ggf. mehrfach anwenden.

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Produktion $[latex]S \to A[/latex]$ eliminieren wir, indem wir einfach die Produktionen von A zu S überleiten: $[latex]S \to X_aY | \; X_aX_b[/latex]$ .

Ebenso verfahren wir mit $[latex]S \to C[/latex]$ : $[latex]S \to X_cC \; | \; c[/latex]$

Wir erhalten also:
$[latex]S \to AC \; | \; X_aY | \; X_aX_b \; | \; X_cC \; | \; c \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Das sollte es sein (hoffe ich).

foogi

Eine Kontextfreie Sprache zur CNF

hallo,

ich habe ein konteztfreie Grammatik, und ich möchte diese in ein Chomsky Normalform umwandeln.
Ich weiß das dies nicht schwer ist, doch habe ich kein ausführliches Beispiel gefunden.

ich habe also:

S--> AC
A--> aAb | epsilon

C--> cC | epsilon

Nun muss man ja die epsilon Regeln entfernen, Kettentregeln, und Hilfsregeln benutzten.
Wie würde das anhand diesem einfachen Beispiel funktionieren.

Eine Schrittweise erläuterung wäre sinnvoll, so das ich das nachvollziehen kann.

vielen Dank