Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

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




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

Слово X =x1…xk графически совпадает со словом Y=y1…yl, если xiÎV (1 £ i £k), yjÎV (1 £ j £k), l=k, и для любого i ,1 £ i £k, xi=yi. Будем обозначать графическое совпадение слов X=Y.

Длиной слова Х (обозначается ïХï) будем называть число вхождений символов в слово Х. Если X =x1…xk, то ïХï=k . ïlï=0

Конкатенацией слов X =x1…xk и Y=y1…yl называется слово Z= XY= x1…xk y1…yl. Например, конкатенацией слов «авто» и «бус» будет слово «автобус».

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

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

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

Операция конкатенации не является коммутативной, XY¹YX.

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

X0=l для любого слова Х. Множество 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. Поэтому язык может быть задан теми же способами, как и любое множество:

Перечислением элементов.

Ограничивающим свойством.

Через известные множества

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

В основном будем использовать 4 способ, но начнем с третьего.




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

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

В частности, " L, ÆÎ L.

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

Пусть 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/ xÎV* & xÏ L1}.

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

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

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

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

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

L1 (L2 L3)= (L1 L2) L3

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

L (L1ÈL2 ) = LL1 È LL2.

(L1ÈL2 ) L = L1L È L2L

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

l L {l}= {l} L = L

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



В силу ассоциативности операции произведения, как и в случае конкатенации цепочек,

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

Итерацией языкаL1 называется языкL(L=L1*), если

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

Вводится также операция усеченной итерации.L называ­ется усеченной итерацией языкаL1 (L=L1+),если





Дата добавления: 2014-02-02; просмотров: 995; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10427 - | 7686 - или читать все...

Читайте также:

 

34.226.244.70 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.004 сек.