Пример 8.1

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

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

Понятие экономичности системы счисления

Контрольные вопросы и задания

Перевод целых чисел из одной системы счисления в другую

Сопоставление алгоритмических моделей

Пример 4.2

Вернуться в оглавление: Теоретические основы информатики