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

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


2 чел. помогло.
Смотрите также:
Удк 681. 5;519. 16;519. 68...
Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450. 2я731-1...
Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2...
Конспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73...
Учебно-методическое пособие Кострома 2007 удк 519. 8 (075)...
Удк 519. 876 + 519. 71 + 51-77 обобщенные линейные алгоритмы управления формациями...
Учебное пособие Москва 2007 удк 657(075. 8) Ббк 65. 052я73...
Учебно-методический комплекс москва макс пресс 2011 удк 316. 7 (075. 8) Ббк 60. 56я73...
Удк 519. 713. 1...
Конспект лекций составлен в соответствии с программой дисциплины «Прикладная статистика»...
Учебное пособие Москва Киев 2009 «Рыбари» «Знання» удк 002. 2(075. 8) Ббк 73. 031+76. 110я73...
Учебное пособие Издание 2-е, переработанное и дополненное москва юристъ 2 0 0 0 удк 341...



Загрузка...
страницы:   1   2   3   4   5   6   7   8   9   ...   17
скачать


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


МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)


Сергиевский Г.М., Короткова М.А.


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

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


МОСКВА 2004


УДК 519.713(075)+519.76(075)

ББК 22.18я7

С32

Сергиевский Г.М., Короткова М.А. Введение в математическую лингвистику и теорию автоматов. Конспект лекций. – М., МИФИ, 2004

Учебное пособие предназначено для студентов факультета Кибернетики, изучающих на пятом семестре математическую лингвистику и основы теории автоматов. Пособие представляет собой конспект лекций по этому курсу. В дальнейшем планируется расширить представленный материал и дополнить его методическими указаниями, примерами и задачами. Пособие может быть полезно всем желающим получить начальные знания по изложенным разделам дискретной математики.


Рецензент В.П. Румянцев


Рекомендовано редсоветом МИФИ

в качестве учебного пособия


© ^ Г.М.Сергиевский, М.А.Короткова, 2004

© Московский инженерно-физический институт

(государственный университет), 2004

Содержание

1. Алфавит, слова, операции над словами 4

2. Языки. Операции над языками 5

2.1. Теоретико-множественные операции 6

2.2.Специфические операции 6

3. Абстрактные формальные системы 7

4. Формальные порождающие грамматики 9

5. Классификация грамматик 11

6. А-языки. Конечные лингвистические автоматы 13

6.1. Диаграмма грамматики 13

6.2. Порождение и распознавание цепочек 15

6.3. Детерминизация недетерминированных автоматов 19

6.4. Автоматы с -переходами 22

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

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

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

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

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

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

7.3. Расширенная форма Бекуса – Наура (РБНФ) 43

7.4. Синтаксическая диаграмма 44

8. Структура цепочек. СУ-схемы 45

9. Преобразования КС-грамматик 51

9.1 Устранение непроизводящих правил 51

9.2. Устранение недостижимых нетерминалов 52

9.3. Устранение -правил 53

9.4. Устранение цепных правил (правил вида А  В) 55

10. Разрешимые и неразрешимые свойства КС-грамматик 56

10.1. Разрешимые свойства КС-грамматик 56

10.2. Неразрешимые свойства КС-грамматик 59

11. Синтаксический анализ для КС-языков 60

11.1. Типовая задача синтаксического анализа 61

11.2. LL(k)-грамматики 62

11.3. Восходящий анализ 69

12.Элементы теории конечных автоматов 74

12.1. Автомат Мили 74

12.2. Автоматы Мура 80

12.3. Частичные автоматы 85

13. Сети автоматов. Их анализ и синтез 88

13.1. Синхронные сети автоматов 89

13.2. Правильно построенные логические сети 93


Пособие рассматривает основные понятия и теоремы математической лингвистики, а также включает некоторые аспекты теории автоматов.
^

1. Алфавит, слова, операции над словами


Пусть V={v1, v2,…,vn}, n1 – некоторый алфавит. Тогда любая последовательность x1x2…xk, k0, где xi V, 1  i k , слово в алфавите V; при k=0 –получается пустое слово, обозначим его . Множество всех слов алфавита V обозначается V*.

Слово X =x1…xk графически совпадает со словом Y=y1…ym, если xiV (1  i k), yjV (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. Операция конкатенации не является коммутативной, ^ XYYX.

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

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

2. Языки. Операции над языками


Произвольное множество цепочек над алфавитом V, иначе любое подмножество свободной полугруппы V*, называется фомальным языком над V. Поэтому язык может быть задан как любое множество:

  • перечислением элементов;

  • ограничивающим свойством;

  • через известные множества;

  • порождающей процедурой.

В основном будем использовать четвёртый способ, но рассмотрение языков начнем с третьего способа их представления.

Например, для любого V множество слов четной длины является языком. Множество слов нечетной длины также является языком, но в отличие от первого — не замкнутым относительно операции конкатенации. Будем обозначать языки буквой L (с индексами или без них). Рассмотрим операции над языками.

Так как язык является множеством, то применимы все соответствующие операции, для которых выполняются все законы теории множеств.

В частности,  L,  L.




Скачать 1,76 Mb.
оставить комментарий
страница1/17
Дата29.09.2011
Размер1,76 Mb.
ТипКонспект, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4   5   6   7   8   9   ...   17
плохо
  2
средне
  1
отлично
  5
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх