Дайте официальный грамматик G, который удовлетворяет L (G) = L

Question

Привет, у меня есть следующий вопрос, заданный мне в прошлой экзаменационной статье. Я понимаю решение (вроде?), Но задаюсь вопросом, знает ли кто-нибудь, как это решение фактически создано (или другое упрощенное решение).

Дайте формальную грамматику G, которая удовлетворяет L (G) = L ...

L := {w member of {a,b}* | n does not exist in N : w = (ab)^n} 

ответ на:

G : ({A,B,S},{a,b},P,S) with 
P := { 
     S-> a | empty | bA | aB | aaA 
     A-> aA| bA | empty 
     B-> aB | bB | a | aaA | bbA } 

Спасибо

Answer 1

Старый вопрос, но это могло бы помочь другие тем не менее.

Язык, который вы даете, - это набор всех слов, которые не могут быть записаны как (возможно, пустая) конкатенация строки ab; то есть все слова, кроме тех, что указаны в (ab)*.

То, что запрашиваемый язык является дополнением к более простому языку, - это путь, который мы рассмотрим, чтобы найти грамматику. Во-первых, мы можем написать DFA для языка (ab)*:

Q s Q' 
q0 a q1 
q0 b q2 
q1 a q2 
q1 b q0 
q2 a q2 
q2 b q2 

Исходное состояние, q0, является единственным принятие государством. q2 - мертвое состояние.

Чтобы получить DFA для нужного языка, мы можем просто обменять принимающие и не принимающие состояния этого DFA. То есть, чтобы принять язык, содержащий строки, которые не могут быть записаны как (ab)^n для любого натурального номера n, мы просто делаем q1 и q2 Принимаем вместо q0.

Получить грамматику из DFA очень просто. Нетерминальные символы соответствуют состояниям DFA. Переходы в DFA становятся постановками в грамматике. Если у вас есть переход от состояния q к q' на символ s в вашем DFA и нетерминальные символы A и B, соответствуют q и q', Вы получаете продукцию A := sB в вашей грамматике. Если q является принимающим состоянием в вашем DFA, а A соответствует q, то у вас также есть продукция A := e, где e - пустая строка. Если вы не хотите пустых производств (кроме, возможно, S := e), то вы также можете обрабатывать принимающие состояния путем дублирования производств. Это один из способов сделать строительство; есть и другие, которые так же хороши.

Для нашего случая:

S ~ q0 
A ~ q1 
B ~ q2 

S := aA  f(q0, a) = q1 
S := bB  f(q0, b) = q2 
A := aB  f(q1, a) = q2 
A := bA  f(q1, b) = q0 
B := aB  f(q2, a) = q2 
B := bB  f(q2, b) = q2 
A := e  q1 is accepting 
B := e  q2 is accepting 

Теперь мы можем написать EBNF, комбинируя линии:

S := aA | bB 
A := aB | bA | e 
B := aB | bB | e