Упаковка
Перенос - это операция над строками с двумя заголовками, определяемыми следующим образом:
Позволять а также быть терминальными строками, начинающимися с x и y соответственно.
Конкатенация
Конкатенация - это семейство операций над строками с заголовком n> 0, определенное для n = 1, 2, 3 следующим образом:
Позволять , , а также быть терминальными строками, начинающимися с x , y и z соответственно.
И так далее для . Можно резюмировать шаблон здесь просто как «объединить некоторое количество терминальных строк m с заголовком строки n, обозначенным как заголовок результирующей строки».
Форма правил
Правила грамматики головы определяются в терминах этих двух операций, причем правила принимают любую из форм
где , , ... являются либо конечной строкой, либо нетерминальным символом.
Головные грамматики способны генерировать язык . Мы можем определить грамматику следующим образом:
Вывод слова abcd таков:
И для "aabbccdd":