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

Kontextfrei vs Kontextsensitiv

+1 Punkt
1,262 Aufrufe

Was ist denn allgemein der Unterschied zwischen einer kontextfreien Sprache (Typ-2) und kontextsensitiven Sprache (Typ-1)?

Bei Typ-1 darf man doch keine lamda-Übergang haben und bei Typ-2 schon, oder?

Aber dann könnte man ja mit einer Typ-1 Sprache die Sprache einfach definieren als mit einer Typ-2 Sprache...? (Zumindest wenn das der einzige Unterschied sein sollte)

 

 

Gefragt 22, Okt 2014 in KON-AI von uxcyx uxcyx Tutor(in) (104,810 Punkte)  

Eine Antwort

0 Punkte

Hallo.

Das ist teilweise richtig. Eine Typ-1-Grammatik heißt auch monotone Grammatik, da die Wörter nicht kürzer werden dürfen. Zudem darf kein λ-Übergang stattfinden, außer Sλ, wenn S sonst auf keiner rechten Seite auftritt. (S kann also nur als erste Regel ausgeführt werden).

Für den zweiten Teil deiner Frage gilt, dass jede Sprache vom Typ i auch vom Typ i-1, für i=1,2,3 ist.

Liebe Grüße,

Leonard (Tutor)

Beantwortet 22, Okt 2014 von uxcyx uxcyx Tutor(in) (104,810 Punkte)  
...