Übungsblatt 7

Question 1

Wenn L eine Sprache mit index(RL) = unendlich ist, dann ist L kontextfrei?

Answer 1

Falsch, weil für alle nicht-regulären Sprachen L auch index(RL) = unendlich gilt, aber nicht jede nicht-reguläre Sprache ist eine kontextfreie Sprache

Question 2

Wenn L eine nicht-kontextfreie Sprache ist, dann ist index(RL) = unendlich?

Answer 2

Wahr, weil jede Sprache, die nicht-kontextfrei ist, auch nicht-regulär ist und somit index(RL) = unendlich gilt

Question 3

Wenn G eine Grammatik in CNF ist, dann ist L(G) kontextfrei und nicht-regulär?

Answer 3

Falsch

Question 4

Es existieren kontextfreie Sprachen A und B so, dass A Schnitt B auch kontextfrei ist?

Answer 4

Wahr