0 Daumen
687 Aufrufe


Hallo ich muss die Aufgabe hier lösen und hab da auch schon meine Antworten angekreuzt. Ich bin bloß nicht sehr sicher und würde gern mal euer Feedback dazu haben oder worauf ich achten sollte.

Es ist eine Multipli Choice Aufgabe:


Definitionen Sei ( G=(V, \Sigma, P, S) \) eine \( b \) eine beliebige Grammatik. Welche der folgenden Aussagen sind korrekt?


Wählen Sie eine oder mehrere Antworten:


 a Auf der linken Seite einer Regel muss mindestens eine Variable stehen.
 b. Die von G erzeugte Sprache ist \( L(G)=\left\{x \in \Sigma^{*} | S \Rightarrow a x\right\} \)
 c. Falls G eine reguläre Grammatik ist, dann gibt es eine zu \( G \) äquivalente reguläre Grammatik G' die keine Regeln der Form   \( A \rightarrow a, a \neq \varepsilon, \) enthalt.
d. Jede reguläre Sprache wird von einer kontextfreien Grammatik erzeugt.
e. Eine Grammatik in Chomsky-Normalform darf Regeln der Form \( A \rightarrow a B \) enthalten.
f. Jede Grammatik in Chomsky-Normalform ist auch eine kontextsensitive Grammatik.
g. Jede kontextfreie Sprache ist auch eine kontextsensitive Sprache.

h. Jede reguläre Grammatik ist eindeutig.
i. Eine Grammatik besitzt genau eine Startvariable.
j. Eine Grammatik darf unendlich viele Regeln enthalten.
k. Sei \( L \) eine kontextfreie Sprache mit \( \varepsilon \notin L \), dann gibt es eine Grammatik in Chomsky-Normalform, die L erzeugt.
l. Auf der rechten Seite einer Regel muss mindestens eine Variable stehen.
m. Es gibt kontextfreie Sprachen, die nicht regulär sind.
n. Die von G erzeugte Sprache ist \( L(G)=\left\{x \in \Sigma^{*} | S \Rightarrow \dot{a} x\right\} \)

o. Jede kontextfreie Grammatik ist auch eine kontextsensitive Grammatik.


Also meine Antworten wären : c, e, g, i, j, j, k, l  und n


Falls ihr Vorschläge oder Erklärungen zu den einzelnen Antworten habt, wäre ich euch sehr verbunden.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community