Проблема контекстно-свободной грамматики

Question

Для начала, это домашнее задание. У меня есть идея, но я все еще не могу получить правильный ответ. Я не прошу ответа, я просто прошу помощи, чтобы ответить на вопрос.

В настоящее время я пытаюсь написать контекстную грамматику для языка

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

Таким образом, между 2. и b в два раза больше, чем b и a. Например:

d,  adbb,  aadbbbb,  …… 

Вот то, что у меня есть, у меня не так много ... Я понимаю концепцию этих CFG, я просто не уверен в логике этого вопроса. Я не уверен, если я даже иду в правильном направлении ...

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

Спасибо.

Answer 1

Всякий раз, когда у вас есть язык, вы можете перечислить вот так, где каждая строка в подстроке следующей строки довольно просто написать простую рекурсивную грамматику.Вам нужно правило для создания первой (самой короткой) строки и правило для создания каждой более длинной строки из предыдущей строки.

Answer 2

Полагаю, я начну с подсказок, сказав, что вам нужно всего лишь 2 утверждения, чтобы решить эту проблему. Я бы предпочел увидеть некоторые из ваших работ (даже в неправильном направлении!), Если я хочу дать вам больше.

EDIT

Спасибо за публикацию того, что у вас есть. Вот пара мысленных упражнений, которые, мы надеемся, помогут вам двигаться в правильном направлении:

Напишите грамматику, выражающую a ⁿ b ⁿ для n> 0 (ab, aabb, aaabbb, ...)

Статья Википедии о CFG поможет вам в этом, если вы все еще застряли.

Напишите грамматику, которая выражает ⁿ дБ ⁿ для n> 0 (adb, aadbb, aaadbbb, ...)

Когда вы получите последний, вы увидите тривиальное дополнение к вашей грамматике.