Метод уменьшения числа состояний автоматов с ограничениями на входе

Как стало ясно из предыдущих параграфов, определение минимальной формы автомата с ограничениями на входе — процесс очень трудоемкий. В тех случаях, когда не обязательно требуется минимальная форма, но уменьшение числа состояний все же желательно, может быть использован упрощенный метод, который часто дает значительно сокращенную форму (а иногда и минимальную форму) по сравнению с заданным автоматом. Предлагаемый метод, по существу, является методом таблиц P_k минимизации автоматов без ограничений на входе, описанным в § 3.6. Единственное различив

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

В качестве примера в таблицах 7.5 и 7.6 представлены соответственно таблица Р₁ и таблица Р₂ для автомата A32, заданного таблицей 7.1. Таблица Р₁ получена путем замены прочерков в клетках подтаблицы z_v таким образом, чтобы

множества {1, 2, 3, 5} и {4, 6} стали 1-эквивалентным разбиением. Заметим, что возможны также другие замены прочерков в клетках, но при выбранной замене получается наименьшее число классов 1-эквивалентности. Таблица Р₂ получена заменой прочерков в клетках таблицы Р₁ таким образом, что множества {1, 2}, {3, 5} и {4, 6} становятся 2-эквивалентным разбиением. Так как это — конечная таблица P₁, то Р₂ является эквивалентным разбиением, из которого сокращенная форма может быть построена по алгоритму 7.2. Случайно получилось, что множества {1, 2}, {3, 5} и {4, 6} также составляют минимальную правильную группировку, так что сокращенный автомат, полученный на основе Р₂, является также минимальной формой автомата A32 (действительно, это автомат A32₁(с волной) рис. 7.2). Заметим, однако, что другая замена прочерков клеток в таблице P₁ может

в результате дать 2-эквивалентное разбиение {1}, {2, 3, 5}, {4, 6}, затем 3-эквивалентное разбиение {1}, {2, 3, 5}, {4}, {6} и, наконец, эквивалентное разбиение {1}, {2}, {3, 5}, {4}, {6}. Ясно, что последнее разбиение дает менее удовлетворительную минимизацию автомата A32, чем {1, 2}, {3, 5}, {4, 6}. В общем случае целесообразно пробовать несколько различных замен на каждом шаге процесса разбиения и изучать, как влияют различные замены на число классов, получаемых при окончательном разбиении или, по крайней мере, при разбиении, непосредственно следующем за данным. Замена прочерков должна быть выбрана так, чтобы дать наименьшее число классов.

Преимущество описанного метода состоит в том, что он позволяет использовать личную изобретательность и опыт для получения сокращенных форм за относительно малое время. Недостатком его является то, что он не гарантирует уменьшения числа состояний и, конечно, не гарантирует

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

группировка может быть образована из пересекающихся совместимых множеств. Например, рассмотрим автомат A33, представленный графом на рис. 7.4 и таблицей 7.7. Р₁ в этом случае будет {1, 2}, {3}, или {1,3}, {2}. В каждом из этих случаев Р₂ будет {1}, {2}, {3}, а это означает, что A33 не может быть минимизирован предложенным методом. С другой стороны, если применить общий метод минимизации, то окажется, что {1, 2} и {1, 3} являются С-множествами для A33

и что эти два С-множества составляют правильную группировку. Поэтому A33 имеет минимальную форму A33, которая состоит из двух состояний. На рис. 7.5 приведена эта минимальная форма, в которой состояния 1 и 2 представляют соответственно множества {1, 2} и {1, 3} автомата A33.

Задачи

7.1. Покажите, что не существует множества в минимальной правильной группировке, которое можно было бы включить в какое-либо другое множество этой группировки.

7.2. C₁, С₂,..., С_k, представляют собой все С-множества автомата М с ограничениями на входе. Покажите, что С₁, С₂,..., С_h составляют правильную группировку и, следовательно, что число состояний в Ṁ не может превышать А.

7.3. Первый вариант таблицы пар для автомата с шестью состояниями представлен таблицей 3 7.1. Найдите все С-множества и минимальную правильную группировку для этого автомата.

7.4. Найдите минимальную форму автомата, заданного таблицей 3 7.2.

7.5. Определите минимальную форму автомата с ограничениями на входе, изображенного на рис. 3 7.1.

7.6. Уменьшите число состояний автомата, заданного таблицей 3 7.3, используя метод сокращения, описанный в § 7.5.

БИБЛИОГРАФИЯ [42]

Айзерман М А., Гусев Л. А., Розоноэр Л. И., Смирнова И. М., Таль А. А., Конечные автоматы, Автоматика и телемеханика, т. XXI, №№ 2, 3, 1960.

Aufenkamp D. D., Analysis of Sequential Machines, IRE Trans., vol. EC-7, pp. 299—306, 1958. [Русский перевод: Ауфенк а м п Д. Д., Анализ последовательностных машин, II, Сб. переводов «Математика», 3: 6, 1959.]

Aufenkamp D. D. and Н о h n F. E., Analysis of Sequential Machines, IRE Trans., vol. EC-6, pp. 276—285, 1957. [Русский переперевод: А у ф е н к а м п Д. Д., X о н Ф. Е., Анализ последовательностных машин, 1, Сб. переводов «Математика», 3:3, 1959.]

Bellman R., Sequential Machines, Ambiguity and Dynamic Programming, J. Assoc. Comput. Mach., vol. 7, pp. 24—28, 1960.

Bellman R., Adaptive Control Processes, pp. 119—123, Princeton University Press, Princeton, N. J., 1961. [Русский перевод: Беллм а н Р., Процессы регулирования с адаптацией, «Наука», 1964.]

Bennett W. S., Minimizing and Mapping Sequential Circuits, Trans., AIEE, vol. 74, pt. 1, pp. 443—447, 1955.

Блох А. Ш., Эквивалентные преобразования последовательностных машин, Автоматика и телемеханика, т. XXI, № 11, 1960.

Burks A. W., The Logic of Fixed and Growing Automata, Annals of the Computation Laboratory, vol. 29, pp. 147—188, Harvard University Press, Cambridge, Mass., 1959.

Burks A. W. and Wang H., The Logic of Automata, J. Assoc. Comput Mach., vol. 4, pp. 193—218, 279—297, 1957.

Burks A. W. and Wright J. В., Theory of Logical Nets, Proc. IRE, vol. 41, pp. 1357—1365, 1953. [Русский перевод: Беркс А., Райт Дж., Теория логических сетей, «Кибернетический сборник», № 4, ИЛ, 1962.]

С a d d е п W. J., Equivalent Sequential Circuits, IRE Trans., vol. CT-6, pp. 30—34, 1959.

de Bruijn N. Q., A. Combinatorial Problem, Proc. Ned. Acad. Wetensch., vol. 49, pp. 758—764, 1946.

E 1 s p a s В., The Theory of Autonomous Linear Sequential Networks, IRE Trans., vol. CT-6, pp. 45—60, 1959.

Fitch F. В., Representation of Sequential Circuits in Combinatory Logic, Phil., Sci., vol. 25, pp. 263—279, 1958.

Friedland В., Linear Modular Sequential Circuits, IRE Trans., vol. CT 6, pp. 61—68, 1959.

Frledland В. and Stern T. E., On Periodicity of States In Linear Modular Sequential Circuits, IRE Trans., vol. IT-5, pp. 136—137, 1959.

Gill A., Comparison of Finite-State Models, IRE Trans., vol. CT-7, pp. 178—179, 1960.

Gill A., Analysis of Nets by Numerical Methods, J. Assoc. Comput. Mach., vol. 7, 251—254, 1960.

Gill A., Characterizing Experiments for Finite-memory Binary Automata, IRE Trans., vol. EC-9, pp. 469—471, 1960.

Gill A., A Note on Moore's Distinguishability Theorem, IRE Trans., vol. EC-10, pp. 290—291, 1961.

Gill A., Cascaded Finite-State Machines, IRE Trans., vol. EC-10, pp. 366—370, 1961.

Gill A., State-identification Experiments in Finite Automata, Information and Control, vol. 4, pp. 132—154, 1961.

Gill A., A Theorem Concerning Compact and Cyclic Sequences, IRE Trans., vol. IT-8, p. 255, 1962.

Gillespie R. G. and Aufenkamp D. D., On the Analysis of Sequential Machines, IRE Trans., vol. EC-7, pp. 119—122, 1958.

Ginsburg S., On the Length of the Smallest Uniform Experiment Which Distinguishes the Terminal States of a Machine, J. Assoc.

Comput. Mach., vol. 5, pp. 266—280, 1958. [Русский перевод: Гинзбург С, О длине кратчайшего эксперимента, устанавливающего конечные состояния машины, «Кибернетический сборник», № 3, ИЛ, 1961.]

G i n s b u r g S., A Synthesis Technique for Minimal-state Sequential Machines, IRE Trans., vol. EC-8, pp. 13—24, 1959.

G i n s b u r g S., On the Reduction of Superfluous States in a Sequential Machine, J. Assoc. Comput. Mach., vol. 6, pp. 259—282,1959.

Ginsburg S., A Technique for the Reduction of a Given Machine to a Minimal-state Machine, IRE Trans., vol. EC-8, pp. 346—355,1959.

Ginsburg S., Synthesis of Minimal-state Machines, IRE Trans., vol. EC-8, pp. 441—449, 1959.

Ginsburg S., Connective Properties Preserved in Minimal-state Machines, J. Assoc. Gomput. Mach., vol. 7, pp. 311—325, 1960.

Ginsburg S., Some Remarks on Abstract Machines, Trans. Am.Math. Soc, vol. 96, pp. 400—444, 1960.

Ginsburg S., Compatibility of States in Input-independent Machines, J. Assoc. Comput. Mach., vol. 8, pp. 400—403, 1961.

Hartmanis J., Linear Multivalued Sequential Coding Networks, IRE Trans., vol. CT-6, pp. 69—74, 1959.

Hartmanis J., Symbolic Analysis of a Decomposition of Information Processing Machines, Information and Control, vol. 3, pp. 154—178, 1960.

Hartmanis J., On the State Assignment Problem for Sequential Machines, IRE Trans., vol. EC-10, pp. 157—165, 1961.

Hartmanis J., Loop-free Structure of Sequential Machines, Information and Control, vol. 5, pp. 25—43, 1962.

Hibbard T. N., Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines, J. Assoc, Comput, Mach., vol. 8, pp. 601—612, 1961

Hohn F. E., Seshu S. and Aufenkamp D. D., The Theory of Nets, IRE Trans., vol. EC-6, pp. 154—161, 1957.

Holladay J. C. and V a r g a R. S., On Powers of Non-negative Matrices, Proc. Am. Math. Soc, vol. 9, pp. 631—634, 1958.

Huffman D. A., The Synthesis of Sequential Switching Circuits, J. Franklin Inst., vol. 257, pp. 161—190, 275—303, 1954.

Huffman D. A., Information Conservation in Sequence Transducers, Proc. Symposium on Information Networks, pp. 291—307,1954.

Huffman D. A., The Synthesis of Linear Sequential Coding Networks, pp. 77—95 in С Cherry (ed), «Information Theory», Academic Press, Inc., New York, 1956.

Huffman D. A., A Linear Circuit Viewpoint on Error-correcting Codes, IRE Trans., vol. IT-2, pp. 20—28, 1956.

Huffman IX A., An Algebra for Periodically Time-varying Linear Binary Sequence Transducers, Annals of the Computation Laboratory, vol. 29, pp. 289—203, Harvard University Press, Cambridge, Mass., 1959.

Huffman D. A., Canonical Forms for Information-lossless Finitestate Logical Machines, IRE Trans., vol. CT-6, pp. 41—59, 1959.

H u z i n о S., On Some Sequential Machines and Experiments, Mem. Fac. Sci., Kyushu Univ., ser. A, vol. 12, pp. 136—158, 1958.

H u z i n о S., Reduction Theorems on Sequential Machines, Mem. Fac. Sci. Kyushu Univ., ser. A, vol. 12, pp. 159—179, 1958.

H u z i n о S., Some Properties of Convolution Machines and Sigma Composite Machines, Mem. Fac. Sci., Kyushu Univ., ser. A, vol. 13, pp. 69—83, 1959.

H u z i n о S., On Some Sequential Equations, Mem. Fac. Sci., Kyushu Univ., ser. A, vol. 14, pp. 50—62, 1960.

К а р а ц у б а А. А., Решение одной задачи из теории конечных автоматов, Успехи матем. наук, т. 15, вып. 3, 1960.

Lee Y. Y., Automata and Finite Automata, Bell System Tech. J., vol. 39, pp. 1267—1295, 1960.

L i p p e 1 B. and Epstein I. J., A Method for Obtaining CompleteDigital Coding Chains, IRE Trans., vol. EC-6, p. 121, 1957.

McCluskey E. J., A Comparison of Sequential and Iterative Circuits, Trans. AIEE, vol. 78, pt. 1, pp. 1039—1044, 1959.

McCluskey E. J., Introduction to State Tables, pp. 109—119 in E. J. McCluskey and Т. С Bartee (eds.), «A Survey of Switching Circuit Theory», McGraw-Hill Book Company, Inc., New York, 1962.

McNaughton R., The Theory of Automata, a Survey, pp. 379— 421 in F. L. Alt (ed.), «Advances in Computers», vol. 2, Academic Press, Inc., New York, 1961.

Mealy Q. H., Method for Synthesizing Sequential Circuits, Bell System Tech. J., vol. 34, pp. 1045—1079, 1955.

M e z e i J. E., Minimal Characterizing Experiments for Finite Memory Automata, IRE Trans., vol. EC-10, p. 288, 1961.

Moore E. F., Qedanken-experiments on Sequential Machines, pp. 129—153 in С. Е. Shannon and J. McCarthy (eds.), «Automata Studies», Princeton University Press, Princeton, N. J., 1956.

Narasimhan R., Minimizing Incompletely Specified Sequential Switching Functions, IRE Trans., vol. EC-10, pp, 531—532, 1961.

Net her wood D. В., Minimal Sequential Machines, IRE Trans., vol. EC-8, pp. 339—345, 1959.

P a u 11 M. С and U n g e r S. H., Minimizing the Number of States in Incompletely Specified Sequential Switching Functions, IRE Trans., vol. EC-8, pp. 356—367, 1959.

Rabin M. O. and Scott D., Finite Automata and Their Decision Problems, IBM J. Research Develop., vol. 3, pp. 114—125, 1959.

[Русский перевод: Р а б и н М. О., Скот Д., Конечные автоматы и задачи на разрешение, «Кибернетич. сборник», N° 4, ИЛ, 1962.]

R а п е у G. N., Sequential Functions, J. Assoc. Comput. Mach., vol. 5, pp. 177—180, 1958.

Reed I. S., Mathematical Structure of Sequential Machines, pp. 187— 196 in E. J. McCluskey and Т. С Bartee (eds.), «A Survey of Switching Circuit Theory», McGraw-Hill Book Company, Inc., New York, 1962.

R u n у о n J. P., Derivation of Completely and Partially Specified State Tables, pp. 121—144 in E. J. McCluskey and Т. С Bartee (eds.), «A Survey of Switching Circuit Theory», McGraw-Hill Book Company, Inc., New York, 1962.

Schubert E. J., Matrix Algebra for Sequential Logic, Trans. AIEE, vol. 78, pt. 1, pp. 1074—1079, 1960. S e s h u S., Mathematical Models for Sequential Machines, IRE Natl. Conv. Record, vol. 7, pt. 2, pp. 4—16, 1959.

Seshu S., Miller R. E. and Metze G., Transition Matrices of Sequential Machines, IRE Trans., vol. CT-6, pp. 5—12, 1959.

Seshu S. and Reed M. В., Linear Graphs and Electrical Networks, pp. 250—260, Addison-Wesley Publishing Company, Inc., Reading, Mass., 1961.

Simon J. M., Some Aspects of the Network Analysis of Sequence Transducers, J. Franklin Inst., vol. 265, pp. 439—450, 1958.

Simon J. M., A Note on the Memory Aspects of Sequence Transducers, IRE Trans., vol. CT-6, pp. 26—29, 1959.

S r i n i v a s a n C. V., Narasimhan R., On the Synthesis of Finite Sequential Machines, Proc. Indian Acad. Sci., vol. 50, 1959.

Stearns R. E. and H a r t m a n i s J., On the State Assignment Problem for Sequential Machines, IRE Trans., vol. EC-10, 1961.

Stern T. E. and F r i e d 1 a n d В., The Linear Modular Sequential Circuit Generalized, IRE Trans., vol. CT-8, pp. 79—80, 1961.

T p a x т е н б р о т Б. А., Об операторах, реализуемых в логических сетях, ДАН СССР, т. 112, № 6, 1957.

U n g e r S. H., Simplification of State Tables, pp. 145—170 in E. J. McCluskey and Т. С Bartee (eds.), A. Survey of Switching Circuit Theory, McGraw-Hill Book Company, Inc., New York, 1962.

van Aardenne-Ehrenfest T. and de Bruijn N. G., Circuits and Trees in Oriented Linear Graphs, Simon Stevin, vol. 28, pp. 203—217, 1950—1951.

Y о e 1 i M., The Cascade Decomposition of Sequential Machines, IRE Trans., vol. EC-10, pp. 587—592, 1961.

Z a d e n L. A., From Circuit Theory to System Theory, Proc. IRE, vol 50, pp. 856—865, 1962.

[1] Понятие множество, если не будет специально оговорено, всегда будет предполагать неупорядоченное множество. Множество элементов e₁, e₂,..., e_r будет записываться так: { e₁, e₂,..., e_r }. Число элементов r называется мощностью множества.

[2] Понятие «состояние», как основное при описании систем, было впервые введено в 1936 г. Тьюрингом (А. М. Turing, On Computable Numbers with an Application to the Entscheidungproblem, Proc. London Math. Soc, ser. 2, vol. 42, pp. 230—265, 1936— 1937). Позже это понятие было использовано Шенноном в его основополагающей работе по теории информации (С. Е. S h e п- non, A Mathematical Theory of Communication, Bell System Tech. J., vol. 27, pp. 379—423, 623—656, 1948). Еще позднее понятие «состояние» было вновь введено Хаффменом (D. A. Huffman, The Synthesis of Sequential Switching Networks, J. Franklin Inst., vol. 257, pp. 161—190, 275—303, 1954), Клини (S. С Kleene, Representation of Events in Nerve and Finite Automata, «Automata Studies», pp. 3—41, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: С. К. Клини, Представление событий в нервных сетях и конечных автоматах. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956) и Муром (Е. F. Moor e, Qedanken — Experiments on Sequential Machines, «Automata Studies», pp. 129—153, Princeton University Press, Princeton, N. Y., 1956.

Русский перевод: Э. Ф. М у р, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., Ш56), после чего оно было принято как одно из основных понятий теории дискретных систем.

[3] Определение 1.1 задает конечный автомат Мили. (Прим. перев.)

[4] Такие автоматы называются также автоматами без памяти или комбинационными устройствами. (Прим. ред.)

[5] Вторая модель соответствует автомату Мура. (Прим. перев.)

[6] Эта модель введена в работе фон Неймана (J. von N e u m a n, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components, «Automata Studies», pp 43—98, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Дж. фон Нейман, Вероятностная логика и синтез надежных организмов из ненадежных элементов. В сборнике «Автоматы», под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956).

[7] Основной столбец представляет собой перечень наименований, расположенных в крайнем левом столбце таблицы. Строку, в которой в основном столбце стоит «К» (или в которой содержимое основного столбца есть «K»), обычно будем называть «строкой К».

[8] Объединение множеств R₁, R₂,..., R_N, записываемое в виде R₁ R₂... R_N является множеством, которое содержит все элементы, содержащиеся в R₁, R₂,..., R_N, и никаких других элементов не содержит.

[9] Множества R₁, R₂,..., R_N — непересекающиеся, если не существует двух множеств R _i и R _j (i ≠ j), содержащих общий элемент.

[10] Множество называется пустым, если оно не содержит ни одного элемента. Пустое множество обозначается нулем.

[11] V —стандартный символ, обозначающий логическую связь «или».

[12] Дуга — направленное соединение, ребро — ненаправленное соединение двух вершин графа. (Прим. перев.)

[13] Материал, относящийся к матрицам переходов, частично базируется на работе Хона, Сешу, Ауфенкампа (F. Е. Н о h п, S. S e s h u and D. D. Aufenkamp, The Theory of Nets, J. R. E. Trans., vol. EC—6, pp. 154—161, 1957).

[14] Диагональный элемент матрицы — это элемент (i, J), где i = J. Недиагональный элемент матрицы — это элемент (i, j), где i ≠ J.

[15] Такие произведения в дальнейшем называются членами элементов матрицы. (Прим. перев.)

[16] ') Множество R₁∩R₂ означает пересечение множеств R₁ и R₂ и состоит из элементов, принадлежащих обоим множествам. Нуль (0) обозначает пустое множество.

[17] Материал этой главы частично базируется на работах: Хаффмена (D. A. Huffman, -The Synthesis of Sequential Switching Networks, J. Franclin Inst., vol. 257, pp. 161—190, 275—303, 1954), Mypa (E. F. Moor e, Gedanken — Experiments on Sequential Machines, «Automata Studies», pp. 129—153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. М у р, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956), Мили (О. Н. Mealy, Method for Synthesizing Sequential Circuits, Bell System Tech. J., vol. 34, pp. 1054—1079, 1955) и Ауфенкампа и Хона (D. D. A u f e n k a m p and F. Е. Н о h n, Analysis of Sequential Machines, IRE Trans., vol. EC—6, pp. 276—285, 1957).

[18] Вместо выражения «различимость автоматов М₁| σ _i и М₂| σ _j» будет употребляться выражение «различимость состояний σ _i и σ _j» во всех случаях, когда по контексту М₁ и М₂ подразумеваются. Аналогично вместо выражения «реакция автомата М | σ» будет употребляться выражение «реакция состояния σ», когда по контексту автомат М подразумевается.

[19] k —номер пары, d — номер класса эквивалентности. (Прим. перев.)

[20] То есть с точностью до обозначения состояний.

[21] Материал этой главы частично основывается на работах; Мура (Е. F. Moor, Oedanken — Experiments on Sequential Machines, «Automata Studies», pp. 129—153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. Myp, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956), Гинзбурга (S. О i n s b u r g, On the Length of the Smallest Uniform Experiment Which Distinguishes the Terminal States of a Machine, J. Assoc. Comput. Mach., vol. 5, pp. 266—280, 1958. Русский перевод: С. Гинзбург, О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины, «Кибернетический сборник» № 3, ИЛ, 1961) и Гилла (A. Oil 1, State Identification Experiments in Finite Automata, Information and Control, vol. 4, pp, 132—154, 1961).

[22] В тексте оригинала употреблено слово «копия». Здесь и далее это слово заменено словом «экземпляр». {Прим. перев.)

[23] Так как О-эквивалентность не определена, состояния, которые 1-различимы и О-эквивалентны, должны считаться просто 1-различимыми.

[24] Хотя σ-множество не является «множеством» в формальном смысле (так как оно содержит повторяющиеся элементы), оно будет обозначаться фигурными скобками, как это принято для обычных множеств.

[25] Терминология, которая будет использована для дерева кратного эксперимента, такая же, как терминология, использованная для диагностического дерева.

[26] В § 4.15 будет показано, что такая последовательность всегда существует.

[27] Автором этого автомата является Хиббард (Т. N. Н i b b а г d, Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines, J. Assoc. Comput. Mach., vol. 8, pp. 601—612, 1961).

[28] Автором этого результата является Гинзбург (S. Ginsburg, On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine, J. Assoc. Comput. Mach., vol. 5, pp. 266—280, 1958. Русский перевод: С. Гинзбург, О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины, «Кибернетический сборник», № 3, ИЛ, 1961).

[29] Материал этой главы частично базируется на работе Мура (Е. г. Moor e, Gedanken-Experlments on Sequential Machines, «Automata Studies», pp. 129—153, Princeton University Press, Princeton, N. У., 1956. Русский перевод: Э. Ф. Мур, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956).

[30] Если не определено иначе, то будем считать, что «класс» автоматов состоит из сравнимых минимальных автоматов таких, среди которых никакие два автомата не являются эквивалентными.

[31] Материал этого параграфа частично базируется на работе Хаффмена (D. A. Huffman, Canonical Forms for Information — Lossless Finite —State Logical Machines, IRE Trans., vol. CT —6, special supplement, pp. 41—59, 1959).

[32] Имеется в виду потеря информации. (Прим. ред.)

[33] Материал этой главы основывается на работе Симона (J. M. Simon, A note on the Memory Aspects of sequence Transducers, IRE Trans., vol. CT-6, pp. 26—29, 1959) и Заде (L. A. Z a- d e h, Unpublished notes on discrete — state systems and automata, University of California, Berkeley, 1960).

[34] Автоматы, у которых выходная реакция не зависит от входного воздействия, называются автономными. Автономные автоматы в книге не рассматриваются.

[35] Несущественная переменная является такой переменной, которая оставляет без изменения значение функции независимо от значения, принимаемого этой переменной.

[36] Сложение по модулю 2 определяется следующим образом: 00 = 0, 0 1 = 1, 1 0 = 1, 1 1 = 0. Если у принимает значение 0 или 1, то у у = 0.

[37] Материал о линейном двоичном автомате базируется частично на работах Хаффмена (D. A. Huffman, The synthesis of Linear Sequential Coding Networks, «Information Theory», pp. 77 — 95, Academic Press, Inc. Neu York, 1956. Русский перевод: Д. А. X а ф ф м е н, Синтез линейных многотактных кодирующих схем. В сборнике переводов «Теория передачи сообщений», ИЛ, М., 1957; D. A. Huffman, An Algebra for Periodically Timevarying Linear Binary Sequence Tranducers, Annals of the Computation Laboratory, vol. 29, pp. 189 — 203, Harvard University Press, Cambridge Mass., 1959).

[38] Метод предложен Липпелом и Эпштейном (В. Lippel and 1. J. Epstein, A Method for Obtaining Complete Digital Coding Chains, IRE Trans., vol. EC-6, p. 121, 1957).

[39] Этот результат получен ван Аарденном-Эренфестом и де Брюином (Т. van Aardenne-Ehrenfest and N. О. de В г u 1J n, Circuits and Trees in Oriented Linear Graphs, Simon Stevin, vol. 28, pp. 203—217, 1950—1951.)

[40] Как автомат М, так и автомат М^-1 являются автоматами без потери информации (см. § 5.8).

[41] Материал этой главы частично базируется на работах Ауфенкампа (P. D. Aufenkamp, Analysis of Sequential Machines, IRE Trans., vol. EC — 7, pp. 299—306, 1958), Гинзбурга (S. О i n s b u г g, A Technique for the Reduction of a Given Machine to a Minimal — State Machine, IRE Trans., vol. EC —8, pp. 346—355, 1959; S. Oinsb u r g, On the Reduction of Superfluous States in a Sequential Machine, J. Assoc. Comput. Mach., vol. 6, pp. 259—282, 1959) и Паула и Ангера (М. С. Р a u 11 and S. H. U n g e r, Minimizing the Number of States in Incompletely Specified Sequential Switching Functions, IRE Trans., vol. EC —8, pp. 356—367, 1959).

[42] Библиография ограничена статьями и книгами, в которых непосредственно рассматриваются вопросы, затрагиваемые в этой книге.