Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32



страница1/22
Дата07.11.2012
Размер1.2 Mb.
ТипКонспект
  1   2   3   4   5   6   7   8   9   ...   22


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)
Сергиевский Г.М., Короткова М.А.


Введение в математическую лингвистику и теорию автоматов.

Конспект лекций

МОСКВА 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. Автоматы с -переходами 21

6.5. Минимизация числа состояний автомата 26

6.6. Регулярные множества и регулярные выражения 31

6.7. Разрешимые проблемы для А-грамматик 38

7. Нотации для задания КС-грамматик 39

7.1. Математическая нотация 39

7.2. Бекусова нормальная форма 39

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. Например, конкатенацией слов «поло» и «вина» будет слово «половина».

Свойства конкатенации:

  1.  является единицей для конкатенации, т.е. для любого слова Х верно, что Х=Х=Х.

  2. Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).

  3. Операция конкатенации не является коммутативной, 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.
  1   2   3   4   5   6   7   8   9   ...   22

Похожие:

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconМетодические указания к практическим занятиям Рязань 2004 удк 519. 713 (075)
Теория автоматов в задачах. Ч1: Методические указания к практическим занятиям/ Рязан гос радиотехн акад. Сост.: Н. И. Иопа. Рязань,...
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций москва 2003 ббк вкб / 075 : 378 я 14
История экономики России XX века (1900 – 1917 гг.) : Конспект лекций. – М.: Мгту "Станкин", 2003. – 45 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73 а 65 Рецензент И. П. Арешев
Охватывает ток (рис. 16), то
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций м осква 2000 ббк ВКП / 075 : 378 я 14
История экономики России XIX века: Конспект лекций. М.: Мгту "Станкин", 2000. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций по философии Часть 1 Античная философия Новосибирск 2007 удк 101. 8 (075) ббк ю3я73-1
Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций Таганрог 2001 удк 621. 382. 019. 3 (075. 8) Механцев Е. Б
Обеспечение надежности электронных средств: конспект лекций. Таганрог: Изд-во трту, 2001
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКурс лекций Для студентов вузов Кемерово 2006 удк 113/119(075) ббк 87я7 М42 Рецензенты

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org