Математическая теория формальных языков
Слова, языки и грамматики
В начале этой лекции определяются основные понятия, используемые в дальнейшем: алфавит, слово, язык над данным алфавитом - и вводятся обозначения для пустого слова, конкатенации слов, степени слова, длины слова, количества вхождений данного символа. В разделе 1.2 фиксируются обозначения для префикса и суффикса слова, а также для ряда операций над языками, таких как конкатенация, итерация, обращение. При беглом чтении раздел 1.3, где определяются образ и полный прообраз языка при гомоморфизме, можно пропустить: вводимые в этом разделе понятия понадобятся только в лекциях 4, 11 и 13.
Используемые в приложениях формальные языки, как правило, являются бесконечными. Очевидно, нужен способ конечного описания формального языка. В данном курсе изучаются несколько классических средств: порождающие грамматики, автоматы, регулярные выражения. Определению понятий грамматики и порождаемого ею языка посвящен раздел 1.4. В конце первой лекции вводятся классы грамматик, образующие иерархию Хомского: грамматики типа 0 (все порождающие грамматики), грамматики типа 1 (контекстные грамматики), грамматики типа 2 (контекстно-свободные, или бесконтекстные, грамматики), грамматики типа 3 (праволинейные грамматики), а также менее важный класс линейных грамматик, промежуточный между классами грамматик типа 2 и 3.
Следует заметить, что каждая грамматика порождает ровно один язык, но обратное неверно: некоторые формальные языки нельзя задать никакой порождающей грамматикой, а каждому языку, который порождается хотя бы одной грамматикой, соответствует сразу бесконечное множество грамматик (причем они могут принадлежать разным классам).
