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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
129 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?

 

in KON-AA von uafjv uafjv Tutor(in) (168k Punkte)  
Bearbeitet von

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
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
von uafjv uafjv Tutor(in) (168k Punkte)  
Bearbeitet von
0 0
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.
0 0
$1S0 \rightarrow 1A$ ist NICHT kontextsensitiv und auch nicht monoton. $1S \rightarrow 1A$ ist kontextsensitiv, aber $S1 \rightarrow 1A$ ist nicht kontextsensitiv (aber monoton).
...