Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [ 21 ] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

Покажите, что: (а) если G(<т<) О и G (ffi) ПО ) = О >). то

G ((Т,) и G (Oi) представляют собой два изолированных подавтомата автомата М; (б) если G (СТ;) = О и G (а,) П О (G ((Т;)) = О, то G (а,)


(ct/m(fi/f) (а ]Ч(р/£1} Рис. 3 2.1.

и G ((Tj) представляют тупиковый и преходящий авто.чаты соответственно; (в) если G ((Т;) =0, то М не содержит изолированных подавтоматов.

2.8. Таблица 3 2.2 представляет автомат А. (а) Найдите G (5,6) для автомата А. (б) Используя результаты задачи 2.7, покажите, что G (6) представляет изолированный подавтомат, а G (2) - тупиковый подавтомат, (в) Найдите максимальное разложение автомата А.

Таблица 3 2.2

) Множество /?1П/?2 означает пересечение множеств /?, и и состоит из элементов, принадлежащих обоим множествам. Нуль (0) обозначает пустое множество.



2.9. Постройте таблицу переходов для расщепляемого автомата, который состоит из автоматов А, Б ч В, изображенных на рис. 3 2.2.

2.10. Пусть (Si) - множество всех состояний автоматами, из которых можно попасть в любое состояние множества Si при подаче входных последовательностей длины k или меньше.


(а) Сформулируйте алгоритм для определения (5;)-множества состояний, из которых Si достижимо при подаче входной последовательности любой длины, (б) Примените алгоритм к автомату А из задачи 2.8 при 5;= {3}. (в) Покажите, что G(Si)\JF(Si) = Н(Si).

2.11. Автомат А 01р2делен матрицей переходов [А], (а) Определите преходящие, тупиковые и изолированные состояния автомата А. (б) Определите G, (5, 7) и Я, (2, 3). (в) Путем изменения порядка строк и столбцов в [А] определите, составляют ли множества состояний {1,2,4,7} и {3,5,6,8} пару из преходящего и тупикового подавтоматов, пару изолированных подавтоматов или пару автоматов, не принадлежащих ни к одному из указанных типов.

1 2 3 4 5 6 7 8

[А] =

(а/1) V (Р/0) О О О

О 0 0 (а/О) О (р/1) О О (а/1) V (Р/1) О О

О О О О О

О О О О О

(а/1) (а/О)

О О О О

(р/0) о

о о о о о

0 0-

0 о о о о о

о (р/1)

о (а/1) V (р/0) о О (р/0) О о (а/1) О (а/О) V (Р/1) о О

2.12. (а) Покажите, что если в)/- единственный ненулевой влемент в /-й строке матрицы [М], то в*;** - единственный ненуле-



1, если является исходящей дугой или петлей, О во всех остальных случаях.

(л X л1)-матрица [М/,] с элементом (I, j), обозначенным через btj, определяется так:

J - / " является заходящей дугой или петлей, 1 О во всех остальных случаях.

Покажите, что М] = [Ма] [МЬ, где [МьЬ является транспонированной матрицей [М,,].

2.20. Используя методику частичного построения матриц, описанную в § 2.13, ответьте на следующие вопросы, относящиеся к автомату, представленному таблицей 3 2.3: (а) Какие кратчайшие входные последовательности переводят автомат из состояния .3 В состояние 1 ? (б) Какие входные последовательности длины 4 или

вой элемент в 1-й строке матрицы (для любого целого *>1). (б) Покажите, что если ej - единственный ненулевой элемент в j-M столбце матрицы [М], то e*y*j - единственный ненулевой элемент в j-u столбце [АГ] * (для любого целого й>1).

2.13. Покажите, что [AJ]"* [AJ]* = [AJ] (для всех *> /).

2.14. Для автомата А из задачи 2.11 постройте; (а) [А], [А],

[If; (б) [А], [Af.....[Af\ (в) [А], [А]\ [If; (г) [Л], [Af,

[AY; (д) установите, что А не имеет полных контуров.

2.15. Покажите, что необходимым условием существования полного контура в автомате М является наличие в каждой строке и в каждом столбце матрицы [М], по крайней мере, одного недиагонального ненулевого элемента. Докажите с помощью примера, что это условие не является достаточным.

2.16. Подсчитайте число различных скелетных матриц и скелетных модифицированных матриц, которые описывают (л, р, д)-авто-маты.

2.17. Требуется определить, существует ли в автомате М путь, который ведет из СТ; в через ст, и если существует, то определить длину минимального пути, соответствующего такому переходу. Сформулируйте алгоритм для решения этой задачи.

2.18. На автомат Men состояниями требуется подать такую входную последовательность, чтобы, начиная из состояния ст,, автомат перешел в состояние через (ft - 1) Л входных символов (где 2 < ft < л) и в состояние а„ через nh символов. Полагая, что элементом (/, j) матрицы [МУ является элемент dfj, найдите число возможных последовательностей, которые отвечают сформулированным требованиям.

2.19. Граф переходов автомата М имеет л состояний, обозначенных а , 02, ..., а„, и т дуг, обозначенных р,, Рг. • • •. Рт- (" X т)-матрица Мд] с элементом (г, j), обозначенным через aij, определяется так;



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [ 21 ] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0009