Estimation for an output symbol multiplicity in invertible automata.pdf Рассматриваются сильно и слабо обратимые конечные автоматы с конечной задержкой. В первых входная последовательность восстанавливается с задержкой по выходной последовательности, во вторых - по выходной последовательности и начальному состоянию [1, 2]. Автомат называется обратимым, если он слабо или сильно обратим. Множество всех обратимых автоматов обозначается Inv. Пусть далее A есть произвольный конечный автомат с n состояниями, m входными символами и с множеством выходных символов Y. Пусть также рА (у) -количество вхождений выходного символа у G Y в таблице выходов автомата A, P(A) = ryeYx{PA(y)} и Р = jrapc P(A). По определению, р есть максимально возможное количество повторений символа в таблице выходов автомата, при котором этот автомат обратим. Теорема 1. n + 1 n + 2 , если n + 2 2 2 2 (n - m + 1)m, если 2 ^ m; р n + 2 > m.

Скачать электронную версию публикации