Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 02»

Кибернетический сборник НОВАЯ СЕРИЯ выпуск 2 Сборник переводов Под редакцией А. А. ЛЯПУНОВА и О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО „МИР" Москва 196 6 УДК 519. 95 НАУЧНЫЙ СОВЕТ ПО КИБЕРНЕТИКЕ АКАДЕМИИ НАУК СССР Второй выпуск новой серии кибернетических сборников (продолжение серии, выпускавшейся Издательством иностран- иностранной литературы в 1960—1963 гг. и издательством «Мир» в 1964 г. ) состоит из двух разделов: математические вопросы и математи- математическая лингвистика. Первый из них содержит статьи, посвя- посвященные некоторым вопросам теории последовательностных авто- автоматов, теории графов и динамического программирования. Раз- Раздел «Математическая лингвистика» включает работу Н. Хом- ского о формальных свойствах грамматик. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, интересую- интересующихся кибернетикой в ее математическом аспекте. Редакция литературы по математическим наукам Математические вопросы ТОЧНЫЕ ВЕРХНИЕ ГРАНИЦЫ ДЛИН МИНИМАЛЬНЫХ ЭКСПЕРИМЕНТОВ, ОПРЕДЕЛЯЮЩИХ ЗАКЛЮЧИТЕЛЬНОЕ СОСТОЯНИЕ, ДЛЯ ДВУХ КЛАССОВ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН1) Т. Н. Хиббард Введение В этой статье рассматривается задача определения состояния последовательностной машины, впервые поставленная в [1]. Пред- Предполагается, что информация о состоянии машины может быть получена только путем подачи входных сигналов и наблюдения выходных сигналов. Подача входных символов, вообще говоря, заставляет машину изменить состояние; это заключительное сос- состояние может быть определено, даже если тачальное состояние останется неизвестным. Вывести конечное состояние машины пос- после введения последовательности входных символов (входов) и наблюдения результатов на выходе (выходов) — значит узнать состояние машины. Процедуру для такого узнавания мы назы- называем экспериментом заключительного состояния, или просто экспериментом2). В [1] было показано, что для произвольной машины с/2 раз- различными состояниями можно построить эксперимент, который в самом худшем случае содержит не более чем п(п—1)/2 сигналов на входе. Хотя статья [1] ограничивалась случаем входно-независимых машин3) (их определение дано в первом разделе настоящей статьи), ее результат и метод, которым он получается, с небольшими из- изменениями лриложимы ко всему классу полных машин4). В сфор- ) Н 1 Ь Ь а г с1 Т. Н. , Ьеаз! Ц1ррег Воипйз оп М1шта1 Тегтта1 51а1е Ехрептегйз 1ог Тт> Оаззез о! 5е^иеп^а1 МасЫпез, ^. Аъвос'тИоп [ог СотриНп§ МасЫпегу, 8, № 4 A961), 601—612. 2) В [1] и [2] эксперимент обозначает последовательность входов, но с тех пор в общепринятом употреблении его заменил термин «лента». 3) В дальнейшем вместо термина «входно-независимая машина» (три{- тс1ерепс1еп1 гласите) мы употребляем принятый в настоящее время термин «автомат (машина) Мура». — Прим. ред. 4) Вместо термина «полная машина» (сотр1е!е гласите) мы будем употреб- употреблять принятый в настоящее время термин «автомат (машина) Мили». — Прим. ред. 8 Т.