- •Глава 3. Анализ и синтез дискретных систем
- •3.1. Применение теории днф к синтезу комбинационных логических сетей (комбинационных схем)
- •3.1.1. Логические элементы
- •3.1.2. Комбинационные логические сети
- •3.1.2.1. Задача анализа
- •3.1.2.2. Синтез в базисе днф
- •3.1.2.3. Синтез в базисе не и
- •3.1.2.4. Синтез в базисе не или
- •3.2. Элементы теории автоматов
- •3.2.1. Классификация автоматов
- •3.2.2. Способы задания конечных автоматов
- •3.2.3. Триггеры
- •3.2.4. Канонические уравнения
- •3.2.5. Автоматы и языки
- •3.2.6. Операции над конечноавтоматными языками
- •3.3. Контрольные вопросы к главе 3
3.2.5. Автоматы и языки
Рассмотрим ряд базовых определений.
Пусть V есть произвольный алфавит, а v есть буква в V. Назовем словом в V всякую последовательность букв из V. Число вхождений букв в слово назовем длиной слова. Пустое слово (слово длины 0) обозначим через .
Множество всех слов длины n обозначим через . Множество всех слов (слов всевозможных длин) обозначим через , т.е. = …
Языком в алфавите V назовем всякое подмножество L слов в этом алфавите, L .
Рассмотрим на множестве слов операцию конкатенации слов, определяемую как приписывание одного слова к другому. Пусть α, β и α = aba, β = aa, то конкатенация α.β = abaaa.
Назовем источником всякую диаграмму в алфавитах U и V, в которой выделены два подмножества вершин , S U. Вершины из называются начальными, а из S – финальными.
Рассмотрим произвольный маршрут из вершины , , в вершину s, s S. Выпишем последовательность меток дуг этого маршрута в порядке прохождения дуг, получим слово в алфавите V.
Будем говорить, что слово несомо данным маршрутом или что данный маршрут несет слово.
Рассмотрим множество всех маршрутов из вершин множества в вершины множества S. Множество слов, несомых этими маршрутами, образуют язык. Будем говорить, что этот язык представляется данным источником.
На одной и той же диаграмме с помощью различных пар < , S> можно представлять различные языки.
Перенесем введенные понятия на автоматные диаграммы.
Пусть A = <X, Q, ψ> есть автомат без выхода, в котором выделено начальное состояние и множество S финальных состояний, S Q.
Тройку <A, , S> будем называть настроенным автоматом, а пару < , S> – его настройкой.
Язык L(A, , S) есть язык, представленный настроенным автоматом <A, , S>. Этот язык удобно задавать соответствующим настроенным источником в алфавитах Q, X.
На одной и той же автоматной диаграмме переходов с помощью различных пар < , S> (различных настроек диаграммы) можно задавать различные языки.
Произвольный язык L называется конечноавтоматным языком, если существует конечный настроенный автомат <A, , S>, представляющий этот язык.
КАДР
3.2.6. Операции над конечноавтоматными языками
Перечислим основные операции над языками.
1. Дополнение. Если L есть произвольный язык в алфавите X, то = \ L есть его дополнение.
2. Объединение. Если , есть произвольные языки в алфавите X, то язык L = есть их объединение.
3. Пересечение. Если , есть произвольные языки в алфавите X, то язык L = есть их пересечение.
4. Отражение. Если L есть произвольный язык в алфавите X, то язык , полученный из слов языка L путем записи его слов в обратном порядке, называется отражением языка L.
5. Конкатенация. Если , есть произвольные языки в алфавите X, то язык L = , полученный приписыванием к слову языка слова языка (L = {αβ, α ,β }), является конкатенацией языков , .
6. Итерация. Если L есть произвольный язык в алфавите X, то язык = L LL LLL …есть итерация языка L.
7. a - аннулирование. Если L есть произвольный язык в алфавите X, то язык, полученный из него вычеркиванием из всех слов языка L буквы a, называется a - аннулированием.
8. Проекция. Пусть U, V – произвольные алфавиты и L , тогда U-проекцией языка L называется язык, полученный из слов языка L вычеркиванием букв языка V.
Например, если ( , ), ( , ),… – слово языка L, то слово , ,… принадлежит U-проекции языка L.
Аналогичным образом определяется V-проекция языка L.
Теорема 3.1. Класс L(A, , S) конечноавтоматных языков замкнут относительно операций 1–8.
КАДР