Контекстно-бесплатный дизайн грамматики

Question

Я узнаю о контекстно-свободных грамматиках и до сих пор понимаю их, но эта проблема как бы заставляет мою голову вращаться.

У меня есть следующие правила:

S --> aSb | bB | epsilon
B --> bbB | bB | epsilon

И я почти уверен, что они неверны.Я понимаю, как бы я сделал просто i <= j вместо реального языка, но идею сделать j <= 3i мне действительно трудно понять, и я не совсем понимаю, как мне это представить в CFG. </p>

Я уже читал некоторые вопросы и темы о разработке CFG, но они не помогли мне со стратегией определения ответа.

Заранее спасибо за вашу помощь!

Answer 1

Для любого a в строке необходимо иметь 1, 2 или 3 b s в строке.

b s должны следовать за a s.

Вы можете иметь ноль a с.

S = A S B | e
A = a
B = b | bb | bbb

Ноль a с подразумевает отсутствие b с.

Один a допускает 1, 2 или 3 b с.

Через рекурсию через S вы можете иметь любое количество a с.

Answer 2

Ваше решение действительно неверно, потому что условие j <= 3i не соблюдается. </p>

Решение, которое ближе к вашим намерениям, чем решение от Björn, и которое использует меньше нетерминалов:

S -> aSb | aSbb | aSbbb | epsilon