[Л11=3 4

1 2 3 4 5

13 10 0

1 4 0 0 0

13 0 10

1 0 0 3 1

1 0 0 3 1

(2.40)

[Л112=:

(2.41)

2,13. Частичное построение матриц

Характерная особенность рассмотренных в предыдущих параграфах матриц состоит в том, что они являются квадратными. Следовательно, они содержат информацию, касающуюся не только двух определенных состояний, но также информацию о любой паре состояний. Часто желательно иметь такую информацию, но она получается ценой выполнения над матрицами трудоемких преобразований, сложность которых возрастает примерно пропорционально квадрату числа состояний автомата. В тех случаях, когда представляют интерес только те пути, которые начинаются из определенного начального состояния, некоторые затруднения, связанные с этими преобразованиями, могут быть обойдены благодаря частичному построению матриц, как это будет показано ниже.

Лемма 2.8. Пусть [Mf обозначает матрицу-строку, построенную из 1-й строки матрицы [Mf. Тогда

[Ж]*+ = [Ж]*[Ж]. (2.42)

Доказательство. Из определения Р* и л и преобразований, аналогичных проведенным в (2.17), получим:

Pf/> = i я,Л*) = i ЛХ,. (2.43)

и = 1

полученной умножением [Ж]* на [М]. Следовательно, равен-

Для фиксированного / множество Pf/ состоит из элементов /-Й строки матрицы Также для фиксированного /

множество 2 Pfuui состоит из элементов матрицы-строки,

u = l

полученной умножением ство (2.42) выполняется.

Лемма 2.8 означает, что [Ж]* может быть построена путем

последовательного умножения [Ж] на матрицу-строку, а не на квадратную матрицу. Когда представляют интерес только пути, начинающиеся в о, такое частичное построение матрицы

оказывается достаточным, так как [Ж]** содержит ту же

информацию об этих путях, что и вся матрица [Ж]*. В результате объем преобразований над матрицами сократится примерно в число раз, равное числу строк в матрице [Ж]. Можно заметить, что описанная схема частичного построения

непосредственно применима к построению матриц [Ж1**\ описанному в алгоритме 2.4.

Матрицы (2.44) - (2.47) иллюстрируют схему частичного построения матрицы для определения всех элементарных путей длины 1, 2, 3 и 4, начинающихся в состоянии 1 автомата А\. [Л1]*** обозначает t-ю строку матрицы [Л1]**

Можно легко показать, что лемма 2.8 справедлива в случае замены [Ж] на [Ж] или на [Ж]. Поэтому частичное построение можно применять для определения строк скелетных матриц и модифицированных скелетных матриц разных степеней.

Задачи,

2.1. Постройте таблицу переходов, граф переходов и матрицу переходов для случаев, сформулированных в задачах 1.2-1.9. Для каждого случая рассмотрите число возможных начальных состояний и входных последовательностей и подтвердите, что выходные последовательности, получаемые на основании различных представлений, соответствуют тем, которые предполагались соответствующими словесным описаниям.

2.2. Известно, что конечный автомат имеет входной алфавит {а, Р}, выходной алфавит {0,1} и множество состояний {1,2,3}. Начертите граф переходов, удовлетворяющий этим условиям.

2.3. Подсчитайте число различных; (а) (л, р, д)-автоматов, в которых реакция в настоящий момент зависит только от состояния в настоящий момент и не зависит от входного сигнала в настоящий момент; (б) (л, р, д)-автоматов, в которых л = р и из каждого состояния можно перейти в любое другое, подав на автомат один входной символ; (в) (л, р, д)-автоматов, в которых нет изолированных состояний; (г) (л, р, )-автоматов, в которых каждый из q выходных символов появляется в таблице переходов, по крайней мере, один раз (достаточно получить рекуррентную формулу для подсчета этого числа автоматов).

2.4. Постройте автомат, изоморфный автомату, изображенному таблицей 3 2.1, посредством замены обозначений состояний 1, 2, 3,

Таблица 3 2.1

4, 5 и 6 на 2, 3, 4, 5, 6 и 1 соответственно. Без построения всего семейства перестановок автомата покажите, что это семейство имеет мощность, равную 61.

2.5. Покажите, что если b обозначает число дуг в графе переходов (л, р, д)-автомата, то л < 6 < л/>.

2.6. (а) Постройте таблицу переходов и матрицу переходов автомата, изображенного на рис. 3 2.1. (б) Определите преходящие, тупиковые и изолированные состояния в автомате, (в) Определите для этого автомата G (1), G (2).....G (8).

2.7. Пусть (т; - состояние из множества состояний S автомата М. Пусть G ((т;) - (т;-достижимое множество и пусть множество G(ст;) состоит из элементов множества S, не содержащиеся q G (а).