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

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

  1. a*b | a

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

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


grammar context-free-grammar
person user776530    schedule 12.09.2011    source источник
comment
Ваш «ответ» для № 1 не может заканчиваться просто a, поэтому я думаю, что вы, возможно, захотите переработать его.   -  person jbranchaud    schedule 13.09.2011

Ответы (2)


arrow_upward
1
arrow_downward

Язык; (а*б | б*а)*

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]
person RJFalconer    schedule 12.09.2011

arrow_upward
2
arrow_downward

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

Намекать:

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

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

person Vivin Paliath    schedule 12.09.2011