Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Hilfe zu Grammatik

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Hilfe zu Grammatik

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

unleashed656
Grünschnabel

Dabei seit: 12.03.2015
Beiträge: 7

Hilfe zu Grammatik

Zitatantwort auf diesen Beitrag erstellen

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von unleashed656: 12.03.2015 11:21.

12.03.2015 11:20

Nehmen Sie unleashed656 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 [latex]a^nB^n[/latex]

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] S \rightarrow aSB ~|~ aB [/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] S & \rightarrow & aSB ~|~ aB B & \rightarrow & b ~|~ bb [/latex]$

Gruß,

Karlito

12.03.2015 11:53

Nehmen Sie Karlito in Ihre Freundesliste auf

unleashed656
Grünschnabel

Dabei seit: 12.03.2015
Beiträge: 7

Danke, perfekt erklärt Daumen hoch

12.03.2015 12:12

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Hilfe zu Grammatik