Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

ist Musterlösung eine kontextsensitive Grammatik?

–1 Punkt
94 Aufrufe

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?

 

Gefragt 26, Nov 2014 in KON-AA von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 26, Nov 2014 von Lukas König

Eine Antwort

+1 Punkt
 
Beste Antwort
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
Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 26, Dez 2014 von Lukas König
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).
...