Контекстно-свободная грамматика для языка, описывающего a, ab, abc, ac?

Я пытаюсь выяснить, что будет CFG для языка, описанного так:

  • только один а
  • 0 или более b
  • 0 или более c

Я пробовал это: S -> a | Sb | Sc

Или что-то типа того:

S -> a | B | C

B -> Bb

C -> Cc

но, похоже, это не работает. Есть ли другой/лучший способ описать этот язык с помощью CFG?


context-free-grammar context-free-language
person Corei7    schedule 25.03.2021    source источник
comment
Можете ли вы придумать регулярное выражение для этого языка? Есть один a. Что предшествует? Что будет после?   -  person rici    schedule 25.03.2021
comment
используйте регулярное выражение a{1}bc   -  person Golden Lion    schedule 25.03.2021

Ответы (1)


arrow_upward
1
arrow_downward

Грамматика для языка строк, в которых есть одна буква а и ничего больше, это просто

S -> a

Ваш язык отличается тем, что допускается ноль или более букв b и c. Они могут идти до или после одиночного а и могут идти в любом порядке. Грамматика для любого количества букв b и c в любом порядке — это

T -> bT | cT | e

Поскольку у нас может быть любое количество b и c по обе стороны от нашего единственного a, это предполагает, что мы можем добавить продукцию для нетерминального T к нашей продукции для S и изменить продукцию для S, чтобы получить a с T по обе стороны:

S -> TaT
T -> bT | cT | e

Эта грамматика должна работать. Доказательство правильности этой грамматики остается в качестве упражнения.

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

q0 -> bq0
q0 -> cq0
q0 -> aq1
q1 -> bq1
q1 -> cq1
q1 -> e
person Patrick87    schedule 26.03.2021