Если из любого состояния автомата достижимы все его состояния, то такой автомат называется

Задача отыскания начального (стартового) состояния заданного автомата называется

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

Если автомат задан в виде ориентированного графа, у которого начальной является вершина , то входному слову в графе автомата будет соответствовать

Если состояние не является концом ни одной дуги автомата , т.е не достижимо ни из одного состояния, отличного от , то оно называется

Автомат называется оптимальным, если

Задача преобразования произвольного автомата в ОБПИК-автомат порядка 1 осуществляется путем

Линейный автомат называется автоматом БПИ, если

Линейный автомат называется неизбыточным по выходам, если

Для того чтобы задача распознавания функции выходов неинициального автомата (с точностью до эквивалентности) была разрешима, необходимо и достаточно, чтобы автомат был

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. . На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если состояние автомата равно 1, то конечное состояние будет равно