Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7
| Вид материала | Конспект |
- Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
- Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
- Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
- Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
- Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
- Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
- Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
- Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
- Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
- Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ
(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)
Сергиевский Г.М., Короткова М.А.
Введение в математическую лингвистику и теорию автоматов.
Конспект лекций
МОСКВА 2004
УДК 519.713(075)+519.76(075)
ББК 22.18я7
С32
Сергиевский Г.М., Короткова М.А. Введение в математическую лингвистику и теорию автоматов. Конспект лекций. – М., МИФИ, 2004
Учебное пособие предназначено для студентов факультета Кибернетики, изучающих на пятом семестре математическую лингвистику и основы теории автоматов. Пособие представляет собой конспект лекций по этому курсу. В дальнейшем планируется расширить представленный материал и дополнить его методическими указаниями, примерами и задачами. Пособие может быть полезно всем желающим получить начальные знания по изложенным разделам дискретной математики.
Рецензент В.П. Румянцев
Рекомендовано редсоветом МИФИ
в качестве учебного пособия
© Г.М.Сергиевский, М.А.Короткова, 2004
© Московский инженерно-физический институт
(государственный университет), 2004
Содержание
1. Алфавит, слова, операции над словами 4
2. Языки. Операции над языками 5
2.1. Теоретико-множественные операции 5
2.2.Специфические операции 6
3. Абстрактные формальные системы 7
4. Формальные порождающие грамматики 9
5. Классификация грамматик 10
6. А-языки. Конечные лингвистические автоматы 13
6.1. Диаграмма грамматики 13
6.2. Порождение и распознавание цепочек 14
6.3. Детерминизация недетерминированных автоматов 18
6.4. Автоматы с -переходами 20
6.5. Минимизация числа состояний автомата 26
6.6. Регулярные множества и регулярные выражения 31
6.7. Разрешимые проблемы для А-грамматик 37
7. Нотации для задания КС-грамматик 38
7.1. Математическая нотация 38
7.2. Бекусова нормальная форма 38
7.3. Расширенная форма Бекуса – Наура (РБНФ) 40
7.4. Синтаксическая диаграмма 41
8. Структура цепочек. СУ-схемы 43
9. Преобразования КС-грамматик 48
9.1 Устранение непроизводящих правил 48
9.2. Устранение недостижимых нетерминалов 49
9.3. Устранение -правил 50
9.4. Устранение цепных правил (правил вида А В) 52
10. Разрешимые и неразрешимые свойства КС-грамматик 53
10.1. Разрешимые свойства КС-грамматик 53
10.2. Неразрешимые свойства КС-грамматик 55
11. Синтаксический анализ для КС-языков 57
11.1. Типовая задача синтаксического анализа 58
11.2. LL(k)-грамматики 58
11.3. Восходящий анализ 65
12.Элементы теории конечных автоматов 70
12.1. Автомат Мили 70
12.2. Автоматы Мура 76
12.3. Частичные автоматы 80
13. Сети автоматов. Их анализ и синтез 83
13.1. Синхронные сети автоматов 84
13.2. Правильно построенные логические сети 88
Пособие рассматривает основные понятия и теоремы математической лингвистики, а также включает некоторые аспекты теории автоматов.
1. Алфавит, слова, операции над словами
Пусть V={v1, v2,…,vn}, n1 – некоторый алфавит. Тогда любая последовательность x1x2…xk, k0, где xi V, 1 i k , слово в алфавите V; при k=0 –получается пустое слово, обозначим его . Множество всех слов алфавита V обозначается V*.
Слово X =x1…xk графически совпадает со словом Y=y1…ym, если xiV (1 i k), yjV (1 j m), m=k, и для любого i ,1 i k, xi=yi. Графическое совпадение слов обозначается X=Y.
Длиной слова Х (обозначается Х) называется число вхождений символов в слово Х. Если X =x1…xk, то Х=k . =0.
Конкатенацией слов X =x1…xk и Y=y1…yl называется слово Z= =XY= x1…xk y1…yl. Например, конкатенацией слов «поло» и «вина» будет слово «половина».
Свойства конкатенации:
- является единицей для конкатенации, т.е. для любого слова Х верно, что Х=Х=Х.
- Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).
- Операция конкатенации не является коммутативной, XYYX.
Для конкатенации, как и для произведения, конкатенация n одинаковых слов X обозначается Xn. Считаем, что
X0= для любого слова Х. Множество V* всех слов алфавита V является полугруппой относительно операции конкатенации.
Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.
Если слово Х=Х1 Х2, то Х1 – начало слова Х, а Х2 – конец слова Х.
Определим, что слово P входит в слово Q, если существует пара слов R и S, такая, что R – первый элемент пары, S – второй элемент пары, и Q =R P S.
Легко доказать следующее
Утверждение. Если слово P входит в слово Q, то существует некоторое слово U, такое, что P – начало U, а U – конец Q.
Следствие. Если слово P входит в слово Q, то P есть начало некоторого конца Q (или конец некоторого начала Q).
Если P есть некоторое начало (конец) Q и P Q, то P – собственное начало (конец) Q.
Конкретные вхождения слова P в слово Q обозначаются RPS, где R, P,S – слова в алфавите V, V. Тогда R – левое крыло вхождения, S – правое крыло вхождения, P – основа.
Определим, что вхождение P1 слова P в слово Q предшествует вхождению P2 слова P в это же слово, если левое крыло вхождения P1 является собственным началом левого крыла вхождения P2.