Theoretische Informatik - Kontextfreie Grammatik in Chomsky Normalform |
| 05.07.2009, 17:14 | Futzel | Auf diesen Beitrag antworten » |
| Theoretische Informatik - Kontextfreie Grammatik in Chomsky Normalform 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,...... |
||
| 05.07.2009, 17:20 | 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 |
||
| 05.07.2009, 17:45 | 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. |
||
| 05.07.2009, 18:03 | 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" |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
