пользователей: 21222
предметов: 10454
вопросов: 177450
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


22. Алфавит. Цепочки. Операции над цепочками. Понятие языка. Свойства языков. Примеры языков. Конструкторы и распознаватели языка.

Под алфавитом å будем понимать непустое конечное множество символов.

Цепочка, или строка – это последовательность символов некоторого алфавита, при этом символы в строке могут повторяться. Для цепочки важен ее состав, порядок символов и их количество.

Над цепочками можно выделить следующие операции:

Конкатенацией, или сцеплением (сложением) цепочек, называется строка, полученная их объединением. Свойства: Так как в цепочке важен порядок символов, очевидно, что операция сложения не коммутативна. Конкатенация ассоциативна, т.е. "a,b,g  (ab)g = a(bg).

Обращение цепочки x – это запись ее символов в обратном порядке, обозначается xR. Свойство операции обращения: "a,b  (ab)R= bRaR.

Итерация цепочки n раз – это ее сцепление (повторение) n раз, обозначается an.

Если å – некоторый алфавит, то:

å+ – множество всех цепочек над алфавитом å без l. 

å* – множество всех цепочек над алфавитом å, включая l. 

Языком L над алфавитом Σ  называют произвольное множество цепочек из символов этого алфавита. Такой язык принято обозначать L(Σ).

 Для любого языка L(Σ) справедливо L(Σ) Í Σ*.

Язык L(Σ) включает в себя язык L¢(Σ): L¢(Σ) Í L(Σ), если "aÎL¢(Σ) aÎL(Σ).

Два языка совпадают (эквивалентны): L¢(Σ) = L(Σ), если L¢(Σ) Í L(Σ) и L(Σ) Í L¢(Σ).

Конкатенацией (объединением) языков L1 и L2 называют язык L, состоящий из всевозможных сцеплений цепочек языков L1 и L2: L = L1·L2 = 


19.01.2016; 06:42
хиты: 10
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь