Description:

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Филологический факультет А. Е. Пентус, М. Р. Пентус Теория формальных языков Учебное пособие Москва 2004 УДК 519.713 ББК 28.25 П25 Рецензенты: Доктор физико-математических наук В. А. Успенский, Кандидат физико-математических наук В. Н. Крупский Печатается по постановлению Редакционно-издательского совета филологического факультета МГУ Пентус А. Е., Пентус М. Р. П25 Теория формальных языков: Учебное пособие - М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004. - 80 с. Учебное пособие посвящено классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, классификация формальных языков по Хомскому, регулярные выражения, конечные автоматы, автоматы с магазинной памятью, алгоритмические проблемы, связанные с контекстно-свободными грамматиками. Для студентов, аспирантов и специалистов, занимающихся математической лингвистикой или теоретической информатикой. УДК 519.713 ББК 28.25 ·c Пентус А. Е., Пентус М. Р., 2003 Введение Учебное пособие содержит основные определения и теоремы курса по теории порождающих грамматик и формальных языков, рассчитанного на 16 теоретических занятий по два академических часа. Материал тщательно структурирован. Факультативные разделы и пункты помечены звёздочками. В пособии приведены главным образом теоретические результаты. Развёрнутые доказательства, примеры и приложения можно найти в других книгах, ссылки на которые имеются в каждом разделе. Многие определения и результаты пояснены простыми примерами. Из примера, приведённого сразу после леммы или теоремы, часто можно понять идею доказательства. Изложение строго математическое, но в то же время используются только самые простые математические понятия. Пособие можно рекомендовать студентам математических, лингвистических и компьютерных специальностей. 1 Слова, языки и грамматики 1.1 Формальные языки Гин, с. 12-14_, _АхоУль, 0.2_, _Сал, 1.1_, _Гла, 1.1_, _ХопМотУль, 1.5_, _ГорМол, с. 347-349_, _СокКушБад, с. 11-12_, _LewPap2, 1.7_, _Рей, с. 22-23_, _КукБей, с. 257-262_, _АхоСетУль, 3.3_ Определение 1.1 Будем называть натуральными числами неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2,...} обозначается N. Определение 1.2 Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами). Определение 1.3 Словом (цепочкой, строкой) в алфавите называется конечная последовательность элементов. Пример 1.4 Рассмотрим алфавит {a, b, c}. Тогда baaa является словом в алфавите. Слова, языки и грамматики Определение 1.5 Слово, не содержащее ни одного символа (то есть последовательность длины 0), называется пустым словом и обозначается. Определение 1.6 Длина слова w, обозначаемая |w|, есть число символов в w, причём каждый символ считается столько раз, сколько раз он встречается в w. Пример 1.7 Очевидно, baaa = 4 и ε = 0. Определение 1.8 Если x и y - слова в алфавите, то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией (катенацией, сцеплением) слов x и y. Иногда конкатенацию слов x и y обозначают x · y. Определение 1.9 Если x - слово и n ∈ N, то через xn обозначается слово x · x · ... · x. По определению x0 (знак n читается "равно по определению"). Всюду далее показатели над словами и символами, как правило, являются натуральными числами. Пример 1.10 По принятым соглашениям, ba3 = baaa и (ba)3 = bababa. Определение 1.11 Множество всех слов в алфавите обозначается Σ*. Определение 1.12 Множество всех непустых слов в алфавите обозначается Σ+. Пример 1.13 Если Σ = {a}, то Σ+ = {a, aa, aaa, aaaa,...}. Определение 1.14 Говорят, что слово x - префикс (начало) слова y (обозначение x ≤ y), если y = xu для некоторого слова u. Пример 1.15 Очевидно, baa, baabaa, babaa и baabaabaa. Определение 1.16 Говорят, что слово x - суффикс (конец) слова y (обозначение x ≥ y), если y = ux для некоторого слова u. Определение 1.17 Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v. Определение 1.18 Через w[a] обозначается количество вхождений символа a в слово w. Пример 1.19 Если Σ = {a, b, c}, то baaa[a] = 3, baaa[b] = 1 и baaa[c] = 0. Ключевые слова: подслово, порождаться грамматика, конечный автомат, класс, математический, вывод, найтись, тьюринг, учебник использоваться, контекстно, алфавит, править, css, система соответствие, дерево вывод, линейный, достаточный заменить, выполняться, следовательно, эквивалентный мп-автомат, asa, формальный язык, ахоуля, ad, контекстно-свободный доказательство, лал, память, sb, наука, ak, длина, свободный грамматик, существовать путь, однозначный, слово, ахоуля хопмотуля, ограничение общность, гролан, рассмотреть мп-автомат, машина тьюринг, достаточный построить, свободный, cl, позволять, гин, символ, данный, положить, накачка лемма-насос, автоматный доказательство, sip, bac, гомоморфизм, форма, ast, контекстно-свободный грамматика, dt, массовый задача, доказательство, машин тьюринг, обозначить, конфигурация, относительно язык, qa qr, нормальный форма, порождающий, праволинейный грамматика, контекстно-свободный грамматик, abc, brt, узнать верный, меткий, проблема, разрешимый, место, свободный язык, следующий, система, постовский система, эквивалентный, ab, синтаксический, обозначаться, mod, возможный, порождать, выражение, br, порождаемый, мп-автомат, xi, yi, однобуквенный алфавит, csr, автомат магазинный, упражнение, произвольный, ответ, постовский, язык pref, соответствие, нормальный, равенство, контекстно-свободный язык, магазинный память, существовать, детерминированный конечный, язык автоматный, rr, rt, замечание обычный, исходный язык, следовать, конечный, лемма, aibaj, регулярный выражение, порождающий грамматик, полный детерминированный, утверждение, автоматный язык, терминальный символ, регулярный, сила теорема, алгоритмический проблема, bsb, алгоритм позволять, суффикс, lr, рей, контекстно свободный грамматик, автоматный ответ, контекст ясный, содержать, контекстно свободный, qa, хопмотуля, замечание, aat, исходный, грамматика, гормол, распознавать, доказать, метка, мир, гла, легкий проверить, получить грамматика, машина, автомат, вильямс, рассмотреть алфавит, su, допускаться мп-автоматом, aaa, детерминированный deterministic, достижимый reachable, язык, контекстно свободный язык, рассмотреть, праволинейный, автоматный, детерминированный, имеющий ровно, индукция, ss, aba, язык распознаваться, сало, путь, свойство, aa, qab, начальный, ct, оглавление, правило, хопмотуль, алгоритмически, очевидный, решение, bc, bs, задача, определение, st, распознаваться мп-автоматом, полный, asb, zczr, длинный путь, заключительный, bt, порождаться, abs, aab, магазинный, префикс, алгоритмический, распознаваться, теорема, nn, грамматик, au, bu, ахоуль, язык алфавит, алгоритм, мп-автомат эквивалентный, утверждение лемма, контекстно-свободный, ai, множество, переход, ar, состояние, bb