Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 69

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

Текст из файла (страница 69)

В теории формальных языков— в разных ее аспектах — оказываются полеэнымн оба подхода. Описание языков дается в терминах порождающих процедур, которые типичны для формально-системного подхода; эти процедуры реализуются в виде порождающих грамматик, которые рассматривались в гл. 7.

Задачи же синтаксического анализа, заключающиеся в распознавании принадлежности текста языку и построении его дерева, ставятся как задачи разработки детерминированных распознающих процедур, которые типичны для алгоритмического подхода. Этн процедуры реализуются в виде различных моделей автоматов, адекватных различным классам языков. Для языков типа 3, как следует нз теоремы 8.10, адекватной автоматной моделью является конечный автомат. Для более сложных языков адекватными являются другие автоматные модели, отличающиеся от конечных автоматов бесконечностью памяти; однако на эту бесконечность в зависимости от вида модели н связанного с ней языка накладываются различные ограничения — память может быть магазинной (доступной только с одного конца), линейно ограниченной (линейно зависящей от длины распознаваемого слова) н т.

д., что делает этн модели более ограннченнымн в своих возможностях, чем машины Тьюринга, которые можно считать автоматной моделью языков типа О. Рассмотрение этих моделей выходит за рамки настоящей книги. 3.3. СЕТИ ИЗ АВТОМАТОВ, ИХ АНАЛИЗ И СИНТЕЗ Комбинационные и логические автоматы. Автомат' назыннстся комбинационным, если для любого входного симгн чш и и любых состояний д, и 31 Л(д» и) =Л(д1, а), иначе говоря, если выходной символ не зависит от состояния и определяется текущим входным символом, В таком автомате все состояния эквивалентны и, следовательно, минимальный комбинационный автомат имеет одно состояние.

Функция переходов в нем вырождена; его поведение однозначно задается функцией выходов с одним аргументом; Л(а,) =оь Автомат называется логически.ч, если его входной алфавит состоит из 2ю двоичных наборов длины пг, а выходной — из 2" двоичных наборов длины и. Функция выходов логического комбинационного автомата — это просто система и логических функций от т переменных (1-я функция определяет значения 1-й компоненты в выходном векторе автомата). Последовательные автоматные вычисления. В этом параграфе речь будет идти о различных способах комбиниро.

вания автоматов друг с другом. Если рассматривать ав- Да томаты просто как частный случай алгоритмов, то естественно прежде всего изу- 3в 3в чить автоматные блок-схемы, т. е. блок-схемы (введенные в 3 5.! для произвольных алгоритмов), все блоки ко- лет торых являются конечно-ав- Рис. 8.3 томатными алгоритмами. Поскольку общие свойства схем оказываются очень простыми, ограничимся рассмотрением этих свойств на примере.

На рис. 8.9 дана блок-схема, на которой 51 и 5в — автоматяые операторы, а 5в — автоматный предикат. Как и обычно, сама блок-схема не содержит указаний о том, с какой информацией работают автоматы; оиа лишь указывает передачи управления: сначала работает 5ь затем 5„, затем автомат 5е проверяет условие; при положительном ответе работает 5ь при отрицательном — 5я. Понятно, что ' Здеся н далее, если не оговорено противное, рассматриваются автоматы общего вида — автоматы Милн, 331 Таблица 8.8 Чн Чм Ч~з Чзз Чвз Чзз Чзз Чзз Чзз Чзз Чзз Чзз Чн Чм Чы Чвз Чзз Чзз Чзы Чзз Чззз Чззз Чзз Чзв Чзз Чззв Чззз Чзз б) в) Случай 1: входные алфавиты исходных автоматов не пересекаются. Пусть А! = (а, (з, с), Аз=(ав, )), Аз= (д, й, в).

Тогда схеме на рис. 8.9 соответствует табл. 8.9,а. В ней заключительные состояния отождествлены с начальными состояниями последующих автоматов (аналогнчные преобразования производились прн композиции машин Тьюринга в $ 5,2). Полученную таблицу переходов можно минимизировать по правилам минимизации частичных автома- Таблица 8,9 1 2 2 3 2 1 — 1 ! 1 а) б) при таком взаимодействии автоматы должны «уметь останавливаться», как алгоритмы в гл.

5. Формально будем считать, что каждый из автоматов в заключительном состоянии не определен, т. е. не воспринимает последующих входных сигналов, Автомат, вычисляющий предикат, будет иметь два заключительных состояния — для «да» и для «нет». Зафиксируем (пока без входного алфавита) конкретные таблицы переходов для 5ь Яз, Яз (табл. 8.8, а — в) н рассмотрим два крайних случая, которые возможны для входной информации автоматов. (Выходы для данных рассмотрений несущественны; для определенности будем считать, что онн во всех клетках различны.) лучим табл, 8.10. В этом случае объединения состояний, вообще говоря, не происходит, если только состояния из разных подавтоматов не оказываются эквивалентными. Общий входной алфавит является объединением исходных алфавитов; его мощность равна мощности максимального нз исходных алфавитов.

Число состояний полученного автомата не превосходит суммы чисел состояний исход- а ь с Чп Чм Чп Чм Чи Чзг Чзз Чгг Чзз Чгг Чв| Чм Чзз ЧМ Чзг Чп Чп Чзз Чп Чзз Чзз Чзз Чвз Чзз Чвз ных автоматов. Очевидно, что остальные возможные случаи соотношения алфавитов — это их частичное пересечение; получающиеся таблицы имеют вид, «промежуточный» между табл. 8.9 и 8.10; возможности их минимизации будут зависеть от конкретного вида исходных автоматов. Наконец, заметим, что для графов автоматов указанные преобразования крайне просты и сводятся к отождествлению заключительных вершин с соответствующими начальными вершинами. Прав.

да, возможности минимизации видны на графе не столь наглядно. ЗЗЗ тов; результат приведен в табл. 8.9,б. Разумеется, автомат, описываемый в табл. 8.9,б, будет работать в соответствии с блок-схемой рис. 8.9 только в том случае, если в нужные моменты времени будут происходить «переключения внешней среды», т.

е. переходы от алфавита А~ к алфавиту Аг и т. д. Поскольку эти моменты соответствуют переходам от одного подавтомата к другому и, следовательно, автоматом с табл. 8.9,б распознаются, то переключения можно осуществлять с помощью выходных сигналов. В нашем примере переключающими сигналами будут Х(1, Ь), Л(2, а), ).(2, с(), Х(1, Ь), с.(2, и), З.(2, Ь). Итак, в этом случае блоксхема из автоматов — это также автомат, алфавит которого является объединением алфавитов исходных автоматов, а число состояний не превосходит щах !Я;(, где максимум берется по мощностям множеств состояний исходных автоматов.

Можно сказать, что такой автомат (табл. 8.9,б) реализует блок-схему рис, 8.9 на общей памяти с переключением входов. Случай 2: входные алфавиты исходных автоматов совпадают или включаются друг в друга, Если в рассматриваемом примере положить А1=Аз=(а, Ь, с), Аг=(а, Ь), то для блок-схемы по- Подведем итог. Блок-схема из конечных автоматов 5ь ..., 5ы работающих последовательно (т. е. неодновременно), — это конечный автомат 5, следовательно, множество автоматов замкнуто относительно условного и безусловного перехода. Мощности входного алфавита и множества состояний 5 не превосходят суммы мощностей соответственно входных алфавитов и множеств состояний 5ш...5ю Автомат 5 называют суммой 5ь ..., 5», часто, впрочем, термин «сумма» относят лишь к операции безусловного перехода (т.

е. последовательного соединения с неодновременной работой). Синхронные сети из автоматов. Если автоматы рассматривать как устройства с входами и выходами, то присоединение выходов одних автоматов ко входам других дает схему, пли сеть из автоматов, все автоматы которой работают одновременно. Под состоянием сети из пг одновременно работающих автоматов 5ь ..., 5 (компонент сети) понимается вектор (дп, ..., гуг ), где д, — состояние автомата 5ь Поэтому в общем случае число возможных состояний сети равно произведению чисел состояний составляющих ее компонент. Возникает вопрос, является ли сеть из автоматов автоматом; если да, то как получить ее автоматное опи.

саине из описаний ее подавтоматов. Прежде всего заметим, что вектор-состояние сети указывает, в каких состояниях находятся компоненты сети в один и тот же момент времени. Таким образом, при описании автоматных сетей — в отличие от абстрактных автоматов — необходимо явно вводить понятие времени. Существуют два основных способа введения времени — синхронный и асинхронный, Синхронный способ заключается в следующем. Вводится шкала времени, которая делится на отрезки одинаковой длины (такты); границы тактов называются моментами автоматного времени и нумеруются натуральными числами, начиная с нуля.

Длина такта принимается за единицу времени, Входное слово (последовательность букв) рассматривается как временная последовательность сигналов или импульсов (каждый сигнал соответствует букве); интервал между соседними импульсами равен в точности длине такта'. Следовательно, слово ' При такой интерпретации импульс является «точечным». Можно считать, что сигнал длится на протиженин всего такта; но тогда в случае, если сигналы в соседних тактах одинаковы, нужны внешние часы, укааывающие границы такта.

Характеристики

Список файлов книги