0 Daumen
62 Aufrufe

Frage: Aus gegebener Grammatik in Chomsky Normalform die nicht-leere Suffixsprache bilden

Hallo, ich stehe gerade vor einer Aufgabe, wo ich leider etwas auf dem Schlauch stehe. Gegeben ist eine Grammatik $$G = (V, \sum, P, S) $$ in CNF, also hat jede Produktion die Form X -> Y Z oder X -> a (Y,Z sind Nicht Terminale, a ist ein Terminal). Nun soll eine Grammatik G' ermittelt werden, welche die Nicht-leere Suffixsprache von G erzeugt, also: $$L(G') = \{ v | uv \in L(G) \land v \neq \epsilon \}$$

Mein erster Ansatz war, jede Produktion der Form X -> Y Z zu X -> Y Z | Z "anzupassen", leider scheint das aber nicht richtig zu sein, da ich immer mit längerem Probieren ein Gegenbeispiel finde.

Ich bin dankbar für jeden Tipp!

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community