Построить грамматику для следующих языков

Question

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

Построить грамматик для {* (а * ба * ба *)} следующих языков L =

Answer 1

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

S := e 
S := SL 

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

Теперь наш язык это то, что начинается с любым числом a с, с последующим b, а затем любым числом a с, с последующим b, а затем любым числом a с. Мы можем сначала определить, "любое число a S":

A := e 
A := Aa 

И тогда определение L проста:

L := AbAbA 

Полная грамматика поэтому:

S := e 
S := SL 
L := AbAbA 
A := e 
A := Aa