Блог

Я хочу найти CFG для этого a^n b^3m c d^m e f^2n с m, n gt; 0

Что у меня есть до сих пор

 S -gt; A B C A -gt; a A ff B -gt; bbb B d C -gt; c e  

Имеет ли это какой-то смысл?

Я думаю, что это грамматика:

 ; this rule generates "a" first and "ff" last S = a A ff  ; allow more "a" first and "ff" last A = S  ; between "a^n" and "f^2n" there will be "b^3m c d^m" followed by "e" A = B e  ; this rule generates "bbb" first and "d" last B = bbb C d  ; allow more "bbb" first and "d" last C = B  ; this rules generates "c" between "b^3m" and "d^m" C = c  

Ваша грамматика до сих пор позволяет c последовать за d тем, что нарушает правила.

Должно сработать следующее

 S = a S ff | a bbb B d e ff B = bbb B d | c  

Первое правило гарантирует, что для каждого a в начале есть два f в конце. Это приводит в исполнение, по крайней мере, одно a . Вторая половина обеспечивает соблюдение последовательности d e ff... .

Второе правило обеспечивает правильное количество b и d , а также то, что сингл c находится между b s и c s