ist Musterlösung eine kontextsensitive Grammatik?

Question

ich dachte, dass eine Kontextfreie Grammatik nur ein Nonterminal Symbol auf der linken seite haben darf.

 

Meine Lösung ist so

G=(N,T,P,S) N=(S,A) T=(0,1)

S->Lambda|0S|1A

A->1A|1

 

Für mich sieht die Grammatik in der Musterlösung wie eine kontextsensitive Grammatik aus. Ich denke ich habe da was falsch verstanden bzw. was nicht richtig aus den Folien gelesen. Kann mir da jemand den Unterschied verraten?

 

Answer 1

Das ist genau richtig, eine kontextfreie Grammatik hat nur ein Nonterminalsymbol auf der linken Seite (so wie in der Musterlösung), genauer:

$N \times (N \cup T)^\star$

Eine kontextsensitive Grammatik kann auf der linken Seite noch einen Kontext haben

$\phi_1A\phi_2 \rightarrow \phi_1 \psi \phi_2$ mit $\phi_1,\phi_2, \psi \in (N\cup T)^\star, A \in N, \psi \neq \lambda$

Sie sollten bei Ihrer Grammatik auch noch $A \rightarrow \lambda$ einfügen, sonst erhalten Sie immer mindestens doppelt so viele einsen wie nullen, und können so nicht alle geforderten Wörter erzeugen. Beachten Sie bitte auch, dass Sie bei den Terminal- und Nonterminalmengen Mengenklammern verwenden und die Produktion ebenfalls so angeben.

Freundliche Grüße
Friederike Pfeiffer

Comments

Ah, ich glaube jetzt weiß ich mein Denk fehler. Mit der linken Seite ist die Seite gemeint, die vor den Pfeil steht, oder? Ich habe  immer nur die alles rechts von Pfeil betrachtet.

 

Das heiß:

S->AB|1A0

ist kontextfrei

und

 

1S0-> 1A

wäre kontextsensitiv.

 

Ist das so richtig?

und wäre

1S->1A bzw. S1->1A auch kontextsensitiv?
 
Danke schonmal!

EDIT: hat sich erledigt! Ich habe gute Beipiel auf der ersten Folien von der Turingmaschine  gefunden.

---

$1S0 \rightarrow 1A$ ist NICHT kontextsensitiv und auch nicht monoton. $1S \rightarrow 1A$ ist kontextsensitiv, aber $S1 \rightarrow 1A$ ist nicht kontextsensitiv (aber monoton).