Informatiker Board | Theoretische Informatik | Hilfe zu Grammatik

Informatiker Board » Themengebiete » Theoretische Informatik » Hilfe zu Grammatik » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 3 Beiträge
unleashed656	Danke, perfekt erklärt
Karlito	Hallo unleashed656, schauen wir uns als erstes die zu erzeugende Sprache an: Die Sprache enthält mindestens das Wort ab Die Wörter sind immer eine Folge von a gefolgt von einer Folge von b Die Anzahl der b muss mindestens genauso groß sein wie die Anzahl der a Es dürfen maximal zwei mal so viele b sein wie a Entwerfen wir also eine Grammatik. Es soll eine kontextfreie Grammatik sein. D.h. auf der linken Seite der Produktionen dürfen nur einzelne Nichtterminale stehen, wohingegen auf der rechten Seite der Produktionen beliebige Abfolgen von Terminal- und Nichtterminalsymbolen sowie $[latex] \varepsilon [/latex]$ stehen dürfen. Wir wissen, dass die Anzahl der b von der Anzahl der a Abhängig ist, aber in gewisser Weise flexibel. Also erzeugen wir uns erst einmal mit n >=1, wobei B ein Nichtterminal ist und passen nachher B so an, dass die Bedinung, wie viele b es geben darf zutrifft. $[latex]<br /> S \rightarrow aSB ~\|~ aB<br /> [/latex]$ Wir wissen ja, dass die Anzahl b mindestens genau so groß sein darf wie die Anzahl a. Wenn wir also alle B durch b ersetzen würden, so hätten wir genau so viele b wie a. Wenn wir das B durch bb ersetzen, dann hätten wie genau doppelt so viele b wie a. somit hätten wir mit der Produktion $[latex] B \rightarrow b ~\|~ bb [/latex]$ alle möglichen Anzahlen b zwischen n und 2n abgedeckt. Vollständig wären die Produktionsregeln also folgende: $[latex]<br /> S & \rightarrow & aSB ~\|~ aB<br /> B & \rightarrow & b ~\|~ bb<br /> [/latex]$ Gruß, Karlito
unleashed656	Hilfe zu Grammatik Hallo ich habe eine Sprache gegeben zu der ich nun eine kontextfreie Grammatik erstellen muss, nur leider komme ich nicht wirklich drauf. Die Sprache: L= {w {a, b}*\|w = a^n b^m mit 1 <= n <= m <= 2n} Ich habe schwierigkeiten mit der Bedingung 1<=n<=m<=2n. Wie kann ich die Grammatik bilden? Danke schonmal für eure Hilfe.