Дискретная математика

Методы абстрактного синтеза

• Часть 1
• | 2
• | 3
• | 4
• | 5
• | 6
• | 7
• | 8
• | 9
• | 10
• | 11
• | 12

Рассмотрим еще один пример абстрактного синтеза автомата. Найдем таблицу переходов автомата сравнения чисел, условия работы которого заданны регулярными выражениями

S3 = |{|x2|}|xs|; S1 = |[|x2|v|x01|v|x10|}|x01|{|x2|}|xs|;

S2 = |{|x2|v|x01|v|x10|}|x10|{|xr|}xs

Регулярные выражения событий S1 и S2 содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, т.к. в автоматах многократного действия за словом любого события, например S1, может быть подано слово любого другого события, т.е. S2 v S2 v S3. В размеченных выражениях можно объединить места с индексами 4, 6 и 5,9:

S3 = |{|x2|}|xs|; S1 = |[|x2|v|x01|v|x10|}|x01|{|x2|}|xs|;

S2 = |{|x2|v|x01|v|x10|}|x10|{|xr|}xs

По размеченному выражению составим отмеченную таблицу переходов.

При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например. В событии S3 переход из состояния 0 в состояние 1 происходит под действием сигнала x2 а в S1 под действием этого же сигнала из состояния 0 автомат переходит в состояние 3. Поэтому, внутреннее состояние, в которое автомат переходит под действием x2 из состояния 0, будем называть множеством из двух индексов 1 v 3. Аналогично получается переход из состояний 2, 7 и 9 под действием x2, а также переход из состояния 4 и 5 в состояния 3 v 6 и 3 v 8 соответственно под действием x2. При заполнении таблицы получается свободные клетки там, где переходы в автомате не определенны. Такие клетки будем отмечать звездочкой *, которую следует рассматривать как индекс некоторого внутреннего состояния. Таблица переходов составляется не только для состояний, отмеченных индексами основных мест регулярного выражения, но и для состояний, отмеченных множеством индексов. Для заполнения колонок для таких состояний достаточно образовать дизъюнкцию таких индексов, которые расположены в колонках, отмеченных индексами, входящими в множества. Например. Для заполнения колонки 1 v 3 образуем дизъюнкцию индексов расположенных в колонках 1 и 3. Поскольку состояния 1, 3, 6 и 8 отмечены пустой буквой e, то и состояния 1 v 3, 3 v 6, 3 v 8 также отмечаются буквой е.

предыдущаяследующая