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

Скачать 1.2 Mb.

страница	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={v₁, v₂,…,v_n}, n1 – некоторый алфавит. Тогда любая последовательность x₁x₂…x_k, k0, где x_i V, 1  i k , слово в алфавите V; при k=0 –получается пустое слово, обозначим его . Множество всех слов алфавита V обозначается V*.

Слово X =x₁…x_k графически совпадает со словом Y=y₁…y_m, если x_iV (1  i k), y_jV (1  j m), m=k, и для любого i ,1  i k, x_i=y_i. Графическое совпадение слов обозначается X=Y.

Длиной слова Х (обозначается Х) называется число вхождений символов в слово Х. Если X =x₁…x_k, то Х=k . =0.

Конкатенацией слов X =x₁…x_kи Y=y₁…y_lназывается слово Z= =XY= x₁…x_k y₁…y_l. Например, конкатенацией слов «поло» и «вина» будет слово «половина».

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

 является единицей для конкатенации, т.е. для любого слова Х верно, что Х=Х=Х.
Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).
Операция конкатенации не является коммутативной, XYYX.

Для конкатенации, как и для произведения, конкатенация n одинаковых слов X обозначается Xⁿ. Считаем, что

X⁰= для любого слова Х. Множество V* всех слов алфавита V является полугруппой относительно операции конкатенации.

Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.

Если слово Х=Х₁ Х₂, то Х₁ – начало слова Х, а Х₂ – конец слова Х.

Определим, что слово 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 обозначаются RPS, где R, P,S – слова в алфавите V, V. Тогда R – левое крыло вхождения, S – правое крыло вхождения, P – основа.

Определим, что вхождение P₁ слова P в слово Q предшествует вхождению P₂ слова P в это же слово, если левое крыло вхождения P₁ является собственным началом левого крыла вхождения P₂.

1 2 3 4 5 6 7 8 9 ... 22

Похожие:

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

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