От мен се иска да покажа, че наборът от песни от формата ABA^R е без контекст (където A^R е обърнато A). Не знам как да покажа, че езикът е без контекст.
Не сме изучавали конкретно как да покажем, че един език е без контекст, така че да не може да бъде твърде сложен. Единственото нещо, за което се сещам, е да направя граматика без контекст за езика, но наистина не знам дали това е достатъчно, за да покаже, че е без контекст или как бих направил граматика за набор от песни.
Ако приемем, че A и B са набор от низове и са свободни от контекст, тогава има граматики без контекст за език A и B, да речем G_A и G_B. Можете да получите безконтекстната граматика за език A^R от G_A доста лесно. Просто обърнете дясната страна на граматичните правила и готово, имате граматиката за A^R.
Ако началната променлива на G_A е S_A, G_B е S_B и G_A^R е S_A', тогава крайната граматика ще бъде комбинацията от тези граматики (всяка променлива от трите граматики трябва да бъде именувана уникално) с новата начална променлива и новата правило, посочващо
S -> S_A S_B S_A'
push down automata. Но какво имаш предвид подA^RеAобратно. Може ли да бъдеш по-точен - person nu11p01n73R schedule 26.09.2014