Theoretische Informatik - Kontextfreie Grammatik in Chomsky Normalform

Neue Frage »

Futzel Auf diesen Beitrag antworten »
Theoretische Informatik - Kontextfreie Grammatik in Chomsky Normalform
Hi,

ich weiß nicht, ob es hier her passt, aber ich hab da eine Frage zu dem Thema Theoretische Informatik.

Folgende Sprachen sind definiert:

L1 = {b a^n c | n>=1}
L2 = {a^n bb a^n | n>=1}
L3 = { a^n b^n c^n | n>=1}

Geben Sie an, ob es eine kontextfreie-Grammatik in Chomsky Normalform gibt.
Eine Ja/Nein Antwort mit Begründung reicht.

Wie genau bekomme ich das raus?

L1 wäre z.B bac,baac,baaac....

L2 wäre z.B abba,aabbaa,aaabbbaaa....

L3 wäre z.B abc,aabbcc,aaabbbccc,......
kiste Auf diesen Beitrag antworten »

L1 ist regulär, da ist es fast schon trivial. Für L2 kann man leicht nen Kellerautomat angeben und L3 ist nicht mehr kontextfrei, Beweis mit Pumpinglemma
 
 
Futzel Auf diesen Beitrag antworten »

Wenn ich deine Antwort richtig interpretiere:

Dann ist:

L1 -> gibt kontextfrei Grammatik in Chomsky Normalform

Woran erkennst du das L1 regulär ist?


L2 -> gibt kontextfrei Grammatik in Chomsky Normalform

L3 -> gibt keine kontextfrei Grammatik in Chomsky Normalform



Zu den Ja/Nein Anworten. Ich glaube nicht das sich der Prof in der Klausur damit zufrieden geben wird, zusagen, bei L2 kann man einen Kellerautomaten konsturieren oder bei L3 könnte man das mit der Pumpinglemma zeigen.
Dazu wüde auch die Zeit nicht reicht das auszuprobieren.

Du musst doch auch irgendwo dran erkannt haben, das dies damit geht.
kiste Auf diesen Beitrag antworten »

Ja das geht mit Erfahrung, sprich viel Übung.
Bei L1 hab ich sofort den DFA gesehen und bei L2 sofort den Kellerautomaten.
L3 kannte ich bereits, das ist eine "Standardsprache"
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »