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

Question

Я пытаюсь создать контекстно-свободную грамматику, которая генерирует все регулярные выражения над {a,b} хотя бы с одной звездой Клини. Что я сделал до сих пор это:

S ::= A + S | A
A ::= B . A | B
B ::= T | B* | (S)
T ::= a | b | eps

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

Answer 1

Проблема типична для конечных автоматов, в которых есть начальное состояние и состояние "прохождения". Решение состоит в том, чтобы иметь правые части, соответствующие каждому состоянию. Я буду использовать номер 2 для правил, которые представляют переходные состояния.

S  ::= S2

S2 ::= A + S2 | A2 + S1 | A2
A2 ::= B2 . A | B . A2 | B2
B2 ::= B* | (S2)

S1 ::= A + S1 | A
A  ::= B . A | B
B  ::= T | B* | (S1)
T  ::= a | b | eps

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