BNF < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:19 Di 29.11.2005 | | Autor: | Bastiane |
Hallo!
Folgende wichtige Frage:
Ist diese Grammatik kontextfrei?
<S> ::= <U> | <E><N> | <N><E>
<U> ::= 0 | 1 |(00|01|10|11)<U>
<N> ::= 0 | 0<N>0 | 0<N>1 | 1<N>0 | 1<N>1
<E> ::= 1 | 0<E>0 | 0<E>1 | 1<E>0 | 1<E>1
Irgendwann hatte ich mir das mal so erklären lassen, dass ich verstanden habe, was kontextfrei bedeutet, leider habe ich da nur noch den Hauch einer Erinnerung dran, so dass ich das leider nicht mehr so ganz in Worte fassen kann. Es hat irgendwas damit zu tun, dass es nicht auf den "Kontext" ankommt, in dem die Nichtterminalsymbole stehen, aber mehr kann ich dazu leider nicht mehr sagen.
Aber nach dieser blassen Erinnerung würde ich sagen, dass diese Grammatik kontextfrei ist!?
Evtl. könnte mir jemand kurz ein Beispiel für eine nicht kontextfreie Grammatik geben?
Übrigens ist das keine Aufgabe, die ich lösen muss (also ob diese Grammatik da oben kontextfrei ist) - ich brauche also keine "mathematische" Begründung, sondern eine intuitive Erklärung oder evtl. sogar nur die Definition für kontextfrei oder ein Beispiel würden mir schon sehr helfen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:19 Di 29.11.2005 | | Autor: | Bastiane |
Hallo Karl!
> > Ist diese Grammatik kontextfrei?
> >
> > <S> ::= <U> | <E><N> | <N><E>
> > <U> ::= 0 | 1 |(00|01|10|11)<U>
> > <N> ::= 0 | 0<N>0 | 0<N>1 | 1<N>0 | 1<N>1
> > <E> ::= 1 | 0<E>0 | 0<E>1 | 1<E>0 | 1<E>1
>
>
> Ich denke diese Grammatik ist kontextfrei, weil alle
> Produktionen von Dieser links immer genau ein
> Nicht-Terminal enthalten! Würde die Grammatik den Kontext
> beachten, müßte sie links auch Terminale berücksichtigen;
> Tut sie aber nicht.
Danke für deine Antwort - jetzt weiß ich auch glaube ich wieder, was kontextfrei heißt. Also wenn es nicht so wäre, dann ständen - wie du ja gesagt hast - links von dem "::=" auch Terminalsymbole.
> [P.S. Das war ja mal eine kurze Antwort ... ![[happy]](/images/smileys/happy.gif "[happy]") . Oder
> wolltest Du noch wissen, was diese Grammatik macht? Auf den
> ersten Blick scheinen mir einige ihrer Produktion etwas
> "überflüssig" zu sein... . Aber wirklich gut kann ich das
> nach über einem Semester nicht mehr... ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]") ]
Nein, danke - deine Antwort war genau das, was ich wollte. Vielen Dank. 
Was die Grammatik macht (oder machen soll), kann ich dir sagen:
Sie "konstruiert" (oje - meine Terminologie...) die Sprache [mm] L_5=\{x\in\{0,1\}^{\star}| \mbox{x ist nicht von der Form yy für ein y}\in\{0,1\}^{\star}\}
[/mm]
Kann schon sein, dass einige der Produktionen überflüssig sind, aber es ist die Musterlösung, und da geht man schonmal einfach nach irgendeinem System vor und versucht nicht unbedingt, die allerkürzeste Variante zu erhalten.
Viele Grüße und nochmals danke für die schnelle Antwort.
Bastiane
P.S.: Ach ja, warum ich nach so etwas gefragt habe: einer der Studenten hat geschrieben, dass es für diese Sprache keine kontextfreie Grammatik gibt... Und jetzt kann ich guten Gewissens drunterschreiben: DOCH!
|
|
|
|
![[user]](/images/smileys/user.gif "[user]"){kind=small}
![[]](/images/popup.gif){kind=small}
Folgendes
Die haben das aber vermutlich absichtlich so gemacht, um die Aufgabe schwerer zu machen. ![[a]](/images/paperclip.gif "Dateianhänge"){kind=small}
[Bild Nr. 1 (fehlt/gelöscht)]
![[breakdance]](/images/smileys/breakdance.gif "[breakdance]"){kind=small}
