Короткова Задачник по курсу Математическая лингвистика и 2012
.pdfМинистерство образованияинауки Российской Федерации
Национальный исследовательский ядерный университет «МИФИ»
М.А. Короткова, Е.Е.Трифонова
Задачник по курсу
«МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА И ТЕОРИЯ АВТОМАТОВ»
Рекомендовано УМО «Ядерные физика и технологии» в качестве учебного пособия для студентов высших учебных заведений
Москва 2012
УДК 519.713(075)+ 519.76(075) ББК 22.18я7
К 68
Короткова М.А., Трифонова Е.Е. Задачник по курсу «Ма-
тематическая лингвистика и теория автоматов». Учебное пособие.
М.: НИЯУ МИФИ, 2012. 92 с.
В пособие включены задачи по лингвистике, теории автоматов и кодированию. Задачи разделены по темам, каждый раздел содержит краткое изложение базовой теории. Для ряда задач даны ответы или указания.
Данное пособие предназначено для студентов факультета кибернетики и информационной безопасности, изучающих математическую лингвистику и теорию автоматов, и может быть также рекомендовано всем интересующимся математической лингвистикой и теорией автоматов.
Пособие подготовлено в рамках Программы создания и развития НИЯУ МИФИ.
Рецензент: канд. физ.-мат. наук А.Д. Яшунский
ISBN 978-5-7262-1702-4 |
© Национальный исследовательский |
|
ядерный университет «МИФИ», 2012 |
|
Содержание |
|
Предисловие.................................................................................................... |
4 |
|
Задачи............................................................................................................... |
|
5 |
Тема 1. |
Языки, способы задания, операции над языками ....................... |
5 |
Тема 2. |
Порождающие грамматики....................................................... |
10 |
Тема 3. |
А грамматики, конечные автоматы....................................... |
15 |
Тема 4. |
Бекусовы (бекусовские) нормальные формы............................. |
29 |
Тема 5. |
Структура цепочек. СУ схемы................................................... |
34 |
Тема 6.Эквивалентные преобразованияКС грамматик...................... |
41 |
|
Тема 7. |
LL(k), строго LL(k) грамматики.................................................. |
46 |
Тема 8. |
Грамматики простого предшествования (ГПП), восходящий |
|
анализ......................................................................................................... |
|
51 |
Тема 9. |
Конечные автоматы Мили и Мура........................................... |
54 |
Тема 10. Элементы теории кодирования.............................................. |
64 |
|
Ответы и указания....................................................................................... |
71 |
|
Тема 1. Языки, способы задания, операции над языками ..................... |
71 |
|
Тема 2. Порождающие грамматики....................................................... |
71 |
|
Тема 3. А грамматики, конечные автоматы....................................... |
73 |
|
Тема 4. Бекусовы (бекусовские) нормальные формы............................. |
78 |
|
Тема 5. Структура цепочек. СУ схемы................................................... |
80 |
|
Тема 6. Эквивалентные преобразования КС грамматик..................... |
82 |
|
Тема 7. LL(k), строго LL(k) грамматики.................................................. |
83 |
|
Тема 8. Грамматики простого предшествования (ГПП), восходящий |
|
|
анализ......................................................................................................... |
|
83 |
Тема 9. Конечные автоматы Мили и Мура........................................... |
85 |
|
Тема 10. Элементы теории кодирования.............................................. |
88 |
|
Список литературы...................................................................................... |
90 |
|
|
3 |
|
Предисловие
Математическая лингвистика как самостоятельная дисциплина является достаточно молодой — она сформировалась лишь в 60-е года XX века. В связи с этим, если теоретическая часть курса в какой-то мере обеспечена фундаментальными методически продуманными трудами, то изданий с задачами по математической лингвистике на настоящий момент практически нет. Данное учебное пособие призвано устранить этот пробел.
Основное внимание в пособии уделено задачам, позволяющим студентам освоиться с понятиями и методами математической лингвистики как фундаментальной дисциплины, содержатся также и задачи, демонстрирующие связи с другими дисциплинами и возможные применения математической лингвистики.
Материал пособия разбит на разделы, к каждому из разделов приведены необходимые теоретические сведения, достаточные для решения большинства задач, а также алгоритмы решения типовых задач. Для части задач приведены ответы и указания к решению.
Задачи обеспечивают материал для семинарских занятий по всему курсу «Теория автоматов и математическая лингвистика», а наличие теоретического материала позволяет использовать пособие и для самостоятельной работы студентов при освоении дисциплины.
4
Задачи
Тема 1. Языки, способы задания, операции над языками
Теория. V (алфавит) – любое множество различных символов.
Цепочка (слово) в алфавите V – произвольная последовательность символов v1v2…vn, vi V, i [0,n]. При n= 0 получается пустое слово, оно обозначается λ.
V*- множество всех слов над алфавитом V. Длина слова v1v2…vn (обозначается v1v2…vn ) равна n . Длина пустого слова равна 0.
Конкатенация слов x и y – слово, полученное приписыванием справа к слову x слова y (обозначается xy). Свойства конкатенации:
•в общем случае xy ≠ yx
•(xy)z = x(yz)
•λx = xλ = x
xn = xx...x
•123
n... раз
Если x = uv, то u – начало слова x, а v – хвост (или конец) x. λ – начало и хвост любого слова.
Если x = uyv, то говорят, что имеет место вхождение y в x. При этом u называют левым крылом вхождения, а v – правым крылом.
Если λ – левое крыло, то y называют начальным вхождением, если λ – правое крыло, то y – концевое вхождение.
Инверсия.
= |
= |
5
При этом λ% = λ .
Формальным языком L на V называется произвольное подмножество V*. Пустой язык (язык, который не содержит ни одного слова) - . { λ }- λ-язык (язык, который содержит одно слово - пустое).
Операции над языками:
1.L = L1 L2 ={x | x L1 x L2} – объединение;
2.L = L1∩L2 = {x | x L1 & x L2} – пересечение;
3.L = L1\L2 = {x | x L1 & x L2} – вычитание
(разность);
4.L = L1L2 = { xy | x L1 & y L2} – произведение
(конкатенация);
5. |
L 1n = L 1 L 1 . . . L |
1 – возведение языка в |
|
|
14 |
2 43 |
|
n р а з
степень; 6. L0 = { λ };
∞
7. L*1 = L10 L11 L12 ... = UL1n — итерация языка
n =0
L1;
∞
8. L1+ = L11 L12 L13 ... = UL1n — усечённая итерация
n=1
языка L1.
Пусть VT – конечный алфавит. Регулярные множества в алфавите VT определяются рекурсивно:
1)– регулярное множество;
2){λ} – регулярное множество;
3){a} – регулярное множество для любого a VT;
4)если P и Q – регулярные множества, то регулярными
множествами являются и P Q, PQ, P*;
5) никаких других регулярных множеств нет.
6
Регулярные выражения в алфавите VT обозначают регулярные множества и определяются рекурсивно следующим образом:
1)0 – регулярное выражение, обозначающее регулярное множество ;
2)1 – регулярное выражение, обозначающее регулярное
множество {λ};
3)если a VT, то a – регулярное выражение, обозначающее регулярное множество {a};
4)если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то:
a)(p+q)– регулярное выражение, обозначающее
регулярное множество P Q ,
б) (pq) – регулярное выражение, обозначающее регулярное множество PQ,
в) (p*) – регулярное выражение, обозначающее регулярное множество P*;
5) никаких других регулярных выражений нет.
Задачи:
1.Задан алфавит V = {0; 1; 2} и слова x = 01; y = 2; z = 001. Требуется записать выражения для xy, yx, xyz, x4, x2y2, (xy)2 через символы алфавита.
2.Построить все возможные начала для цепочки (xy)2 и всевозможные концы для цепочки xyz из предыдущей задачи.
3.Определить, имеет ли место вхождение x в z (см. задачу 1). Каково левое крыло вхождения, правое? Является ли вхождение концевым или начальным?
4.Построить все возможные начала и концы слова abcdc.
5.Определить длины слов, построенных в предыдущей задаче.
7
6.Пусть x=bbc, y= ac, z=b. Построить слова xy, (xy)2, x2y2, y3, xyz, xzy, xz2y.
7.Доказать, что для любых слов x и y справедливо
.
8.Задан алфавит V = {a; b}. Определить, являются ли
множества L1 = {a; b; baaa}; L2 = {ba; ab; ac} и L3 = { λ; a; ba} языками над этим алфавитом.
9.Даны языки L1 = {ab; c} и L2 = {c; ca}. Найти результат выполнения следующих операций: L1 L2, L1∩L2, L1\L2, L1L2, L2L1, L12 \ L22 , L12 L22 .
10.Пусть A, B, C, В – слова, AB = CD и |A| ≤ |C|. Доказать, что X: C = AX и B = XD.
11.Даны языки L1 = {a; b} и L2 = {aa; bb}. Чему будет равен результат выполнения следующих действий: L1L2, L2L1, L1L2 ∩L2L1?
12.Среди приведённых выражений для языков указать те
языки, которые равны между собой для любого языка
L:L ; L{λ}; L; {λ}L; ; L; {λ}.
13.Даны произвольные языки L1, L2, L3. Требуется проверить, справедливы ли следующие соотношения (доказать, что они выполняются, или привести опровергающий пример):
a)L1 (L2 L3) = L1L2 L1L3;
b)L1 (L2 ∩ L3) = L1L2 ∩ L1L3.
14.Даны два языка L1 = {ab; c} и L2 = {c; ca}. Чему равны
значения для выражений L2i , L3i , Lni , L*i , L+i , где i = 1,2.
15.Даны L1={ab, ba}, L2={ba, aa, bb}. Построить L1∩ L2 , L1 L2 , L1\ L2, L2\ L1.
16.Даны L1={ab, ba}, L2={bb, aa}. Построить L1 L2, L2L1, L12, L22.
17.Дан L1={ab, ba}. Построить L13, L1n, L1+, L1*.
8
18.Язык L3 состоит из различных двоичных чисел. Записать этот язык в виде множества, в виде регулярного выражения.
19.Даны L1={abа, ba}, L2={аb, aa}. Чему будут равны
L1L2, L2L1, L12, L22?
20.Пусть алфавит V = {0; 1}. В множестве L содержатся всевозможные положительные двоичные целые числа,
вL1 – всевозможные положительные двоичные нечётные целые числа.
a)Записать выражения для L и L1 в виде регулярных выражений;
b)определить, чему равны результаты операций LL1
иL1L;
c)вычислить, чему будут равны L+ и L*.
21.Пусть дан произвольный алфавит V. Верно ли, что λ
V*?
22.Для каких языков L*=L+?
23.Существует ли язык L такой, что для любого языка L1 верно, что L1 =L L1?
24.Существует ли язык L такой, что для любого языка L1 верно, что L L1 =L?
25.Пусть |L1|=n, |L2|=m. Оцените величину |L1L2|.
26.Пусть |L1|=n, n >0, |L2|=m, m>0. В каком случае |L1L2|= nm?
27.Записать регулярное выражение для множества всех слов в алфавите {a; b}, содержащих
a)не менее одной буквы a;
b)не более двух букв b подряд;
c)не менее одной буквы а и не менее одной буквы b.
28.Записать регулярное выражение для множества всех слов в алфавите{a; b}, не содержащих
a)двух букв b подряд;
b)нечётное число букв b подряд;
c)ни одного вхождения слова аbа.
9
29.Записать регулярное выражение для множества всех слов в алфавите{a, b, с}, содержащих
a)не более одной буквы a;
b)хотя бы одну букву a, хотя бы одну букву b.
Тема 2. Порождающие грамматики
Теория. Порождающей грамматикой называется четверка объектов G=< VN, VT, S, R>, где
•VT – алфавит терминальных или основных символов;
•VN — алфавит нетерминальных или вспомогательных символов (VT∩VN = );
•S – начальный символ ( S VN);
•R – конечное множество правил или продукций вида ϕ →
ψ, где ϕ VT* VN (VT VN)*, ψ (VT VN )* — различные цепочки, “→” – метасимвол.
Цепочка ω1 непосредственно выводима из цепочки ω0 (обозначается ω0 ω1 ), если существуют такие ξ1, ξ2, ϕ, ψ,
что ω0=ξ1 ϕ ξ2, ω1=ξ1 ψ ξ2 и правило ϕ→ψ R.
Цепочка ωn выводится из цепочки ω0 за один или более шагов (обозначается ω0 +ωn ), если существует последовательность цепочек ω0, ω1, ω2,…, ωn (n>0), такая, что ωi ωi+1, i {0,…n-1}. Последовательность цепочек ω0, ω1, ω2,…, ωn называется выводом. Если ω0 +ωn или ω0=ωn , то пишут ω0 *ωn.
Языком L(G), порождаемым грамматикой G , называется множество цепочек в основном алфавите, выводимых из начального символа:
L(G) = {x / S * x & x VT* }.
Контекстно-зависимые (КЗ-грамматики) –
грамматики, все правила которых имеют вид ϕ → ψ, где
ϕ VT*VN(VT VN)*, ψ (VT VN )+ и ϕ ≤ ψ .
10