Тест для внешней (выходной) памяти
Основной инструмент для определения, имеет ли данная машина конечную выходную память – это модифицированная тестирующая таблица и ее тестирующий граф. Тестирующая таблица (для выходной памяти), состоит из двух частей, имеет q
столбцов O1O2…Oq, соответствующих различным значениям выходов. Строки верхней части имеют имена состояний таблицы переходов М. На пересечении Si
строки и Оj
столбца записывается состояние, в которое будет переход из Si
при значении Оj
на выходе. Будем называть эти состояния Оj-премниками Si. Клетки верхней половины таблицы заполняются соответствующими преемниками. Верхняя часть таблицы называется таблицей выходных преемников (наследников). Таким образом, машина М Table 3а имеет
| PS
| NS,z | ||||
| x=0 | x=1 | ||||
| A | B,0 | D,1 | |||
| B | C,1 | A,1 | |||
| C | B.0 | C,0 | |||
| D | C,0 | C,1 |
Table 3
выходные 1-преемники состояния В состояния А и С и не имеет ни одного 0-преемника. В Table 3b это соответствует заполнению строки В верхней половины таблицы. Для каждой пары состояний в нижней части таблицы записываются соответствующие преемники. Выходной Ок-преемники SiSj – парные сочетания выходных Ок-преемники из Si и Sj. Например, если преемниками из Si и Sj есть SpSq и SrSt, соответственно, тогда их преемники имеют вид: SpSr, SpSt, SqSr
и SqSt.
Тестирующий (для выходной памяти) граф такой, что:
Пример тестирующего графа приведен в Table 3с. Обратите внимание, что из вершины АВ выходит две дуги с одинаковыми значениями выхода, равного 1.
Утверждение 2 Машина М имеет конечную выходную память, если и только если тестирующий граф не имеет циклов. Если граф, свободный от циклов, имеет наибольший путь длинной l, то М имеет выходную память порядка µ= l+1.
В примере Table 3с граф свободен от цикла и наибольший путь AB=>AD=>CD=>BC равен 3, а порядок µ=4.
Обратите внимание, что граф не содержит вершин с повторяющимися вхождениями, например, ВВ
и т.д.. Наличие таких пар не влияет на неопределенность.
