Definition kontextsensitiver Grammatiken, Umwandlung in NT

Question

Hallo,

ich verstehe das nicht.

Die Definition von kontextsensitiven Grammatiken ist doch ua.:

aXb --> aCb    , mit a, b aus (NT U T)* und C aus (NT U T)+

Warum muss ich dann erst alles in Nonterminalsymbole umwandeln? Dementsprechend dürfte ich doch NT- und T-Symbole mischen...

angenommen man muss nicht alles erst in Nonterminalsymbole umwandeln, warum ist folgende Produktion aus der Aufgabe falsch:

P: S --> S' I lamda

    S' --> aS'c I aB I ac

    B --> aBb I b

?

 

Comments

Die Art, wie Sie Grammatik-Produktionen angeben, ist ziemlich grausam, das kann doch keiner lesen! Am besten geht es, wenn Sie LaTeX-Formeln zwischen Dollarzeichen angeben, also etwa so: \$S \rightarrow ab | ac\$ führt zu $S \rightarrow ab | ac$.

Answer 1

Die Antwort aus der Frage, auf die Sie sich beziehen, ist falsch, siehe meinen Kommentar dort.

Die Produktion nach $\lambda$ ist falsch, weil explizit nach einer kontextsensitiven oder monotonen Grammatik gefragt war, und da $S$ auch auf einer rechten Seite vorkommt, ist das nicht erlaubt. (Nicht alle kontextfreien Grammatiken sind monoton, das sollten Sie im Kopf behalten.) Deshalb müssen wir die Grammatik auch noch lambdafrei machen.