Грамматика. Пример 8.1

Пусть формальная грамматика задается последующим образом: T = {а, b} (т.е. огромное количество терминальных знаков — алфавит языка — состоит из 2-ух знаков — а и b); N = {S}, т.е. огромное количество нетерминальных знаков состоит из единственного знака S — он, естественно, оказывается выделенным; система подстановок пусть имеет последующий вид: S→ aSa, S→ bSb, S→ a, S→ b

Описанная грамматика порождает язык, состоящий из всех «слов-перевертышей» в алфавите {а, b}, имеющих нечетную длину, т.е. слов, которые слева вправо читаются также, как справа влево, к примеру, aba, abababa, bbbbb, baaaaaab и т.д. Просто созидать, что применение первых 2-ух правил (в любом числе и хоть какой последовательности) порождает цепочки (слова) типа αSα^-1, где α^-1 значит слово α, записанное справа влево; применение третьего и 4-ого правил завершает процесс порождения слова и сформировывают слова типа αаα_—¹ либо αbα^-1 .