WWW.DISSERS.RU

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

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 9 |
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Филологический факультет А. Е. Пентус, М. Р. Пентус Теория формальных языков Учебное пособие Москва 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 —конечный автом ат.

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



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

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