Найти грамматику для следующего языка

Question

Найти грамматику для следующего языка:

1. a * b |a

2. (a * b | b * a) *

Я думаю, что у меня есть ответ для 1 (S -> aS | b) но я довольно запутался во втором.Любая помощь будет принята с благодарностью.

Answer 1

Думайте о всем выражении (a*b | b*a)* как о нетерминале, а затем рассматривайте каждый элемент (т. Е. a*b - это один, а b*a - другой) внутри как отдельные нетерминалы.

Совет:

S -> ε | ST
T -> [rule for a*b] | [rule for b*a]

T - это то, что находится внутри скобки.

Answer 2

Язык; (a * b | b * a) *

S -> SA | episilon

A здесь представляет (a * b | b * a)

A -> B
A -> C

B представляет (a * b)

B -> [Insert rule here]

C представляет (b * a)

C -> [Insert rule here]