Context Free Grammar Ausgabe

Question

Für den Anfang ist dies eine Hausaufgabe Frage. Ich habe eine Idee, aber ich bin immer noch nicht in der Lage, die richtige Antwort zu bekommen. Ich bin nicht für die Antwort zu fragen ich nur um Hilfe bitten werde, die Frage zu beantworten.

Ich versuche zur Zeit eine kontextfreie Grammatik für die Sprache

zu schreiben

a(iterated i times)db(iterated j times),  for i and j>=0,  and j = 2 * i.

Also im Grunde gibt es doppelt so viele ist als bs und a d zwischen dem 2. Beispiel:

d,  adbb,  aadbbbb,  …… 

Dies ist über das, was ich habe, ich habe nicht viel ... Ich verstehe das Konzept dieser CFG ist Ich bin nur nicht sicher, über die Logik für diese Frage. Ich bin nicht sicher, ob ich auch die richtige Richtung gehe ...

S -> AdB
A -> EMPTY
A -> aAB
B -> DD

Danke.

Answer 1

Ich denke, ich werde Hinweise beginnen, indem er sagte, dass Sie nur zwei Aussagen müssen diese lösen. Ich würde lieber einige Ihrer Arbeit (auch in der falschen Richtung!) Sehen, wenn ich dir nicht mehr geben, though.

Bearbeiten

Vielen Dank für die Buchung, was du hast. Hier ein paar Übungen gedacht, die Sie hoffentlich in der richtigen Richtung bekommen:

  

Schreiben Sie eine Grammatik, die zum Ausdruck bringt ein ⁿ b ⁿ für n> 0 (ab, aabb, aaabbb, ...)

Wikipedia Artikel über CFG der hat etwas Hilfe zu diesem Thema, wenn Sie noch nicht weiterkommen.

  

Schreiben Sie eine Grammatik, die zum Ausdruck bringt ein ⁿ db ⁿ für n> 0 (adb, aadbb, aaadbbb, ...)

Wenn Sie diese letzte zu bekommen, werden Sie die triviale hinaus sehen Ihre Grammatik zu erhalten.

Answer 2

Wenn Sie eine Sprache, die Sie wie folgt auflisten können, wobei jede Zeichenfolge in einem Teil der folgenden Zeichenkette, seine ziemlich trivial, eine einfache rekursive Grammatik zu schreiben. Sie müssen eine Regel die erste (kürzeste) Zeichenfolge zu machen, und eine Regel jede längere Zeichenfolge aus dem vorherigen Zeichenfolge zu machen.