WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Филологический факультет А. Е. Пентус, М. Р. Пентус Теория формальных языков Учебное пособие Москва 2004 УДК 519.713 ББК 28.25 П25 Рецензенты:

Доктор физико-математических наук В. А. Успенский, Кандидат физико-математических наук В. Н. Крупский Печатается по постановлению Редакционно-издательского совета филологического факультета МГУ Пентус А. Е., Пентус М. Р.

П25 Теория формальных языков: Учебное пособие. — М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004. — 80 с.

Учебное пособие посвящено классическому разделу математической лингвистикой и теоретической информатики — теории формальных языков. Рассматриваются порождающие грамматики, классификация формальных языков по Хомскому, регулярные выражения, конечные автоматы, автоматы с магазинной памятью, алгоритмические проблемы, связанные с контекстно-свободными грамматиками.

Для студентов, аспирантов и специалистов, занимающихся математической лингвистикой или теоретической информатикой.

УДК 519.713 ББК 28.25 © А. Е. Пентус, М. Р. Пентус, 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. Словом (цепочкой, строкой) (string) в алфавите называется конечная последовательность элементов.

Пример 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, b baa, ba baa и baa baa.

Определение 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.

Слова, языки и грамматики Определение 1.20. Если L, то L называется языком (или формальным языком) над алфавитом.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом (обозначения L1 L2, L1 L2, L1 - L2).

Пример 1.21. Множество {a, abb} является языком над алфавитом {a, b}.

Пример 1.22. Множество {akbal | k l} является языком над алфавитом {a, b}.

Определение 1.23. Пусть L. Тогда язык - L называется дополнением (complement) языка L относительно алфавита. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык - L является дополнением языка L.

Определение 1.24. Пусть L1, L2. Тогда L1 · L {xy | x L1, y L2}. ЯзыкL1·L2 называется конкатенацией языков L1 и L2.

Пример 1.25. Если L1 = {a, abb} и L2 = {bbc, c}, то L1 · L2 = = {ac, abbc, abbbbc}.

Определение 1.26. Пусть L. Тогда L0 {} и Ln L ·.. · L.

.

n раз Пример 1.27. Если L = {akbal | 0 < k < l}, то L2 = = {akbalbam | 0 1}.

Определение 1.28. Итерацией (Kleene closure) языка L (обозначение L) называется язык Ln. Эта операция назыnN вается также звёздочкой Клини (Kleene star, star operation).



Пример 1.29. Если ={a, b} и L = {aa, ab, ba, bb}, то L = = {w | |w| делится на 2}.

Определение 1.30. Обращением или зеркальным образом R (reversal) слова w (обозначается w ) называется слово, составленное из символов слова w в обратном порядке.

R Пример 1.31. Если w = baaca, то w = acaab.

R R Определение 1.32. Пусть L. Тогда L {w | w L}.

Слова, языки и грамматики 1.2. Гомоморфизмы [Сал, с. 10], [Гин, с. 57], [АхоУль, 0.2.3], [ХопМотУль, 4.2.3, 4.2.4], [Гла, 1.1], [КукБей, с. 259], [LewPap2, с. 85] Определение 1.33. Пусть 1 и 2 — алфавиты. Если отображение h: удовлетворяет условию h(x · y) =h(x) · h(y) 1 для всех слов x и y, то отображение h называется 1 гомоморфизмом (морфизмом).

Замечание 1.34. Можно доказать, что если h — гомоморфизм, то h() =.

Пример 1.35. Пусть 1 = {a, b} и 2 = {c}. Тогда отображение h:, заданное равенством h(w) = c2|w|, 1 является гомоморфизмом.

Замечание 1.36. Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

Определение 1.37. Если h: — гомоморфизм и 1 L, то через h(L) обозначается язык {h(w) | w L}.

Пример 1.38. Пусть ={a, b} и гомоморфизм h: задан равенствами h(a) = abba и h(b) =. Тогда h({baa, bb}) ={abbaabba, }.

Определение 1.39. Если h: — гом ом орфизм и 1 L, то через h-1(L) обозначается язык {w | h(w) L}.

2 Пример 1.40. Рассмотрим алфавит ={a, b}. Пусть гом оморфизм h: задан равенствами h(a) =ab и h(b) =abb.

Тогда h-1({, abbb, abbab, ababab}) ={, ba, aaa}.

1.3. Порождающие грамматики [Гин, 1.1], [Сал, 2.1], [АхоУль, 2.1.2], [Гла, 1.2], [Лал, с. 159–161], [Бра, с. 32–36], [ГлаМел, с. 34–48], [ГорМол, с. 354–355, 367–370], [СокКушБад, с. 12–13], [ТраБар, 1.12], [LewPap2, 4.6], [Рей, с. 28–30], [КукБей, с. 264–268] Определение 1.41. Порождающей грамматикой (грамматикой типа 0) (generative grammar, rewrite grammar) называется четвёрка G N,, P, S, где N и — конечные алфавиты, N =, P (N )+ (N ), P конечно и S N.

Здесь — основной алфавит (терминальный алфавит), его Слова, языки и грамматики элементы называются терминальными символами или терминалами (terminal), N — вспомогательный алфавит (нетерминальный алфавит), его элементы называются нетерминальными символами, нетерминалами или переменными (nonterminal, variable), S — начальный символ (аксиома) (start symbol). Пары (, ) P называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде.

Пример 1.42. Пусть даны множества N = {S}, ={a, b, c}, P = {S acSbcS, cS }. Тогда N,, P, S является порождающей грамматикой.

Замечание 1.43. Будем обозначать элементы множества строчным и буквам и из начала латинского алфавита, а элем енты множества N — заглавными латинскими буквами. Обычно в примерах мы будем задавать грамматику в виде списка правил, подразумевая, что алфавит N составляют все заглавные буквы, встречающиеся в правилах, а алфавит —все строчные буквы, встречающиеся в правилах. При этом правила порождающей грамматики записывают в таком порядке, что левая часть первого правила есть начальный символ S.

Замечание 1.44. Для обозначения n правил с одинаковыми левыми частями 1,..., n часто используют сокращённую запись 1 |... | n.

Определение 1.45. Пусть дана грамматика G. Пишем, G если =, = и ( ) P для некоторых слов,,, в алфавите N.

Замечание 1.46. Когда из контекста ясно, о какой грамматике идёт речь, вместо можно писать просто.

G Пример 1.47. Пусть G= {S}, {a, b, c}, {S acSbcS, cS }, S.

Тогда cSacS cSa.

G Определение 1.48. Если 0 1... n, где n 0, G G G то пишем 0 n (другими словами, бинарное отношение G G является рефлексивным, транзитивным замыканием бинарного отношения, определённого на множестве (N )). При этом G Слова, языки и грамматики последовательность слов 0, 1,..., n называется выводом (derivation) слова n из слова 0 в грам м атике G. Число n называется длиной (количеством шагов) этого вывода.

Замечание 1.49. В частности, для всякого слова (N ) имеет место (так как возможен вывод длины 0).

G Пример 1.50. Пусть G = {S}, {a, b}, {S aSa, S b}, S.

Тогда aSa aaaaSaaaa. Длина этого вывода —3.

G Определение 1.51. Язык, порождаемый грамматикой G, — это множество L(G) { | S }. Будемтакже говорить, G что грамматика G порождаёт (generates) язык L(G).

Замечание 1.52. Существенно, что в определение порождающей грамматики включены два алфавита — и N. Это позволило нам в определении 1.51 “отсеять” часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту.

Пример 1.53. Если G = {S}, {a, b}, {S aSa, S bb}, S, то L(G) ={anbban | n 0}.

Определение 1.54. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.55. Грамматика S abS, S a и грам м атика T aU, U baU, U эквивалентны.

1.4. Классы грамматик [Гин, с. 23–24, 78–79], [АхоУль, 2.1.3, с. 191], [Сал, 2.1, с. 94], [Гла, 1.2, 1.3], [Бра, с. 39–45], [ГлаМел, с. 54, 63, 69–70], [ГорМол, с. 361–367], [ТраБар, 1.12], [КукБей, с. 268–271], [ЛПИИ, 5.2.1] Определение 1.56. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1) (context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид A, где A N, (N ), (N ), (N )+.





Слова, языки и грамматики Пример 1.57. Грамматика S TS, S US, S b, Tb Ab, A a, TA AAT, UAb b, UAAA AAU не является контекстной (последние три правила не имеют требуемого вида).

Определение 1.58. Контекстно-свободной грамматикой (КС-грамматикой, бесконтекстной грамматикой, грамматикой типа 2) (context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид A, где A N, (N ).

Пример 1.59. Грамматика S AST A, S AbA, A a, bT bb, AT UT, UT UV, UV TV, TV TA является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Определение 1.60. Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид A u или A uBv, где A N, u, v, B N.

Пример 1.61. Грамматика S TT, T cT T, T bT, T a является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Определение 1.62. Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3) (right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид A u или A uB, где A N, u, B N.

Пример 1.63. Грамматика S aSa, S T, T bT, T является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример 1.64. Грамматика S T, U abba праволинейная.

Пример 1.65. Грамматика S aS, S bS, S aaaT, S aabaT, S abaaT, S aabbaT, S ababaT, S abbaaT, T aT, T bT, T праволинейная.

Пример 1.66. Грамматика S, S aaaS, S abbS, S babS, S aabT, T abaT, T baaT, T bbbT, T bbaS праволинейная. Обобщённый вариант языка, порождаемого этой грамматикой, используется в доказательстве разрешимости арифметики Пресбургера [Sip, с. 207–208].

Конечные автоматы Определение 1.67. Правила вида называются -правилами.

Лемма 1.68. Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без -правил является контекстной грамматикой.

Определение 1.69. Классы грамматик типа 0, 1, 2 и образуют иерархию Хомского (Chomsky hierarchy).

Определение 1.70. Язык называется контекстным языком (контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой контекстной грамматикой (соответственно контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример 1.71. Пусть дан произвольный алфавит = {a1,... an}. Тогда язык является праволинейным, так как он порождается грамматикой S, S a1S,..., S anS.

2. Конечные автоматы 2.1. Недетерминированные конечные автоматы [Гин, 2.1], [Сал, 2.1], [АхоУль, 2.2.3], [ХопМотУль, 2.3], [Гла, 5.1], [Лал, с. 185], [ГорМол, с. 391–392], [СокКушБад, с. 19–21], [ЛПИИ, 5.2.3], [Бра, с. 106–107], [ГроЛан, 10.3.1], [ТраБар, 1.5], [LewPap2, 2.2], [Sip, 1.2], [Рей, с. 46–47], [КукБей, с. 324–325], [АхоСетУль, 3.6] Определение 2.1. Конечный автомат (finite automaton, finite-state machine) — это пятёрка M = Q,,, I, F, где — конечный алфавит, Q и — конечные множества, Q Q, I Q, F Q. Элем енты Q называются состояниями (state), элементы I — начальными (initial) состояниями, элементы F — заключительными или допускающими (final, accepting) состояниями. Если p, x, q, то p, x, q называется переходом (transition) из p в q, а слово x — меткой (label) этого перехода.

Конечные автоматы Пример 2.2. Пусть Q = {1, 2}, = {a, b}, I = {2}, F = {2}, = { 1, aaa, 1, 1, ab, 2, 1, b, 2, 2,, 1 }. Тогда Q,,, I, F —конечный автом ат.

Определение 2.3. Путь (path) конечного автомата — это кортеж q0, e1, q1, e2,..., qn, где n 0 и ei = qi-1, wi, qi для каждого i. При этом q0 — начало пути, qn — конец пути, n — длина пути, w1... wn — метка пути.

Замечание 2.4. Для любого состояния q Q существует путь q. Его м етка —, начало и конец совпадают.

Определение 2.5. Путь называется успешным, если его начало принадлежит I, а конец принадлежит F.

Пример 2.6. Рассмотрим конечный автомат из примера 2.2.

Путь 2, 2,, 1, 1, 1, aaa, 1, 1, 1, b, 2, 2 является успешным. Его метка — aaab. Длина этого пути —3.

Определение 2.7. Слово w допускается (is accepted, is recognized) конечным автоматом M, если оно является меткой некоторого успешного пути.

Определение 2.8. Язык, распознаваемый конечным автоматом M, —этоязыкL(M), состоящий из меток всех успешных путей (то есть из всех допускаемых даннымавтоматомслов). Будем также говорить, что автомат M распознаёт (accepts) язык L(M).

Замечание 2.9. Если I F =, то язык, распознаваем ый конечным автоматом Q,,, I, F, содержит.

Пример 2.10. Пусть M = Q,,, I, F, где Q = {1, 2}, ={a, b}, ={ 1, a, 2, 2, b, 1 }, I = {1} и F = {1, 2}. Тогда L(M) ={(ab)n | n 0}{(ab)na | n 0}.

Определение 2.11. Два конечных автомата эквивалентны, если они распознают один и тот же язык.

Определение 2.12. Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.

Замечание 2.13. Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.30).

Пример 2.14. Рассмотрим однобуквенный алфавит ={a}.

При любых фиксированных k N и m N язык {ak+mn | n N} является автоматным.

Конечные автоматы Замечание 2.15. Каждый конечный язык является автоматным.

Определение 2.16. Состояние q достижимо (reachable) из состояния p, если существует путь, началомкоторого является p, а концом —q.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.