Почти съм сигурен, че всъщност имам такъв, но има 42 правила за конструиране и не обобщава добре. Как мога да го направя с по-малко строителни правила?
Езикът е {a,b}*, където броят на a е пет пъти по-голям от броя на b.
Знам, че за език {a^n (concatenate) b^m; m = 5n} просто ще бъде
S = aSbbbbb | λ
Но когато героите могат да бъдат в произволен ред, аз съм изгубен.
Първо, забележете, че ако едно изречение има 5 пъти повече знаци от другото, то винаги ще изглежда нещо като aaabaabaaaaa. Така че едно изречение може да бъде aaaaab или aaabaa. Друго наблюдение е, че всеки път, когато добавим b, трябва да добавим пет a знака.
Следната граматика наистина има пет пъти повече a знака от b знака:
S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb
Започваме с S, което може да бъде празно (което отговаря на изискването) или A.
Правилото за A произвежда поне 5 a знака и B. Сега за B можем или да поставим b и да спрем там (като изберем празния низ за S), или като започнем отново (като изберем A за S). Това гарантира, че винаги поставяме 5 пъти повече a символа от b знака.
И накрая, тази граматика може лесно да се обобщи до граматика, която трябва да съдържа n пъти повече знаци от едното, отколкото другото (чрез директно разширяване на правило A).
baaaaaaaaaab. Коригирах правилото за S, за да го направя възможно: S = AS = AAS = AA = BaaaaaA = BaaaaaaaaaaB = bSaaaaaaaaaaB = bSaaaaaaaaaabS = bSaaaaaaaaaab = baaaaaaaaaab.
- person Simeon Visser; 22.03.2012
