![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Начальные понятия теории формальных языковСтр 1 из 5Следующая ⇒ Введение
Рассмотрим непустое конечное множество А, состоящее из символов {a1, …, ak}. Будем называть А алфавитом, а его символы – буквами. Всякая конечная последовательность букв этого алфавита называется словом (цепочкой или строкой): w=a1a2…an – слово (ai ÎA), |w| – длина слова (число букв, из которых состоит слово, причем каждый символ встречается столько раз, сколько раз он встречается в w). Через |w|b обозначим количество вхождений символа b в слово w. Бесконечная последовательность букв алфавита А называется сверхсловом,
Любое подмножество Если x и y – слова языка Говорят, что слово х – подслово слова у, если y=uxv для некоторых слов u и v. Все подслова слов языка Примеры. 1. ba3=baaa, 2. Множество {a, abb} - язык (конечный) над алфавитом {a, b}. 3. Множество
Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом. Так, язык Пусть Примеры. 1. Если 2. Если L={0, 01}, то Итерацией языка L называется язык Пример. Если A={a, b} и L={aa, ab, ba, bb}, то Обращением или зеркальным образом слова w называется слово wR, в котором буквы слова w идут в обратном порядке. Например, если w=bac, то Пусть Всякое начало слова будем называть префиксом, а всякий конец слова – суффиксом. Например, если y=xv, то х – префикс слова у (обозначение – х[y), а v – суффикс слова у (обозначение – v]y). Очевидно, что пустое слово является как префиксом, так и суффиксом любого слова. Все префиксы слов языка Если язык L таков, что никакое слово L не является префиксом (суффиксом) никакого другого слова L, то говорят, что L обладает префиксным (суффиксным) свойством. Пусть А1 и А2 – алфавиты. Если отображение f: Замечания. 1. Можно доказать, что если f – гомоморфизм, то 2. Гомоморфизмы не всегда являются биекциями, но каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах. 3. Применяя гомоморфизм к языку L, получаем другой язык f(L). Если f: Примеры. 1. Допустим, мы хотим заменить каждое вхождение в цепочку символа 0 на символ а, а каждое вхождение 1 – на bb. Тогда можно определить гомоморфизм f так, что 2. Пусть f – гомоморфизм, для которого
|