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



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

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


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

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

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

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

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

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

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

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

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

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


Пусть L1 и L2 – два языка над алфавитом V. Язык L называется объединением этих языков ( обозначается L = L1 L2 ), если L ={x / x L1 x L2}.

Пересечением языков L1 и L2 называется язык L (обозначается L = L1 L2 ), такой, что L ={x / x L1 & x L2}.

Дополнением языка L1 до V* называется язык L (обозначается L=V*\L1), такой, что L={ x/ xV* & x L1}.

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


Произведением (иначе конкатенацией) языков L1 и L2 называется язык L (обозначается L=L1L2), если L={x y/xL1 & yL2}.


Например, L1={ ac, a }, L2={ cb, b}, тогда L1L2 ={ acb, accb, ab}.

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

  1. операция умножения языков ассоциативна:

L1 (L2 L3)= (L1 L2) L3;

  1. операция умножения языков дистрибутивна относительно объединения:

L (L1L2 ) = LL1 LL2 ,

(L1L2 ) L = L1L L2L;

  1. операция умножения языков не коммутативна: L1 L2 L2 L1.

  2. L {}= {} L = L;

  3. L(L1L2 ) LL1 LL2 , в общем случае равенства нет, что легко показать, подобрав соответствующий пример.

В силу ассоциативности операции произведения, как и в случае конкатенации цепочек, записывается как L=L1n. По определению, L0={}. Отметим, что {} . так как (пустой язык) вообще не содержит никаких цепочек.

Итерацией языка L1 называется язык L (обозначается L=L1*), если L=L10 L11 L12 … =. Как нетрудно видеть, итерация алфавита V* (алфавит можно рассматривать как язык, состоящий из односимвольных слов) образует язык, состоящий из всех возможных цепочек, составленных из символов V. Это обстоятельство и объясняет, почему V* используется для обозначения всех слов над алфавитом V.

Вводится также операция усеченной итерации. L называется усеченной итерацией языка L1 (обозначается L=L1+), если L=L10 L11 L12 … =.
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