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

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

Описание языка

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

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

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

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

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


context-free-grammar automata-theory context-free-language
person B. Klein    schedule 06.03.2019    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Для любого a в строке у вас должно быть 1, 2 или 3 b в строке.

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

У вас может быть ноль as.

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

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

Один a позволяет использовать 1, 2 или 3 bs.

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

person Björn Höhrmann    schedule 06.03.2019

arrow_upward
0
arrow_downward

Ваше решение действительно неверно, так как не выполняется условие j ‹= 3i.

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

S -> aSb | aSbb | aSbbb | epsilon
person Peter Leupold    schedule 07.03.2019