Промышленная установка управляется по 4-разрядной шине данных. Команды по ней передаются последовательно. Для удобства записи будем интерпретировать их как символы в алфавите 0,1,2,..,9,A,B,C,D,E,F.
Известно, что некоторые цепочки команд приводят к поломке установки. Поэтому на шине планируется установить защитный блок, исправляющий такие цепочки на безопасные. Логика работы защитного блока определяется двумя таблицами. Первая из них определяет следующую активную строку в зависимости от входного символа и текущей активной строки (функция переходов). Вторая таблица определяет, что появится на выходе защитного блока в зависимости от входного символа и текущей активной строки (функция выходов). В начальный момент времени активна строка с номером 0. Фрагмент кода функции работы защитного блока приведен ниже.
Паскаль |
Си |
type matrix= array[1..n,1..m] of integer; function GetOutput( StateMas : matrix;
integer; var NewState:integer; OutSymb:integer; begin NewState := StateMas[CurState] [InSymb]; OutSymb := OutMas[CurState] [InSymb]; CurState := NewState; result := OutSymb; end; |
int GetOutput( int **StateMas,
// StateMas –таблица(матрица) переходов // OutMas – таблица(матрица) выходов // InSymb – входной символ // CurState – текущее состояние (меняется в результате выполнения функции) // RETURN – выходной символ { int NewState; int OutSymb;
NewState = StateMas[CurState] [InSymb]; OutSymb = OutMas[CurState] [InSymb]; CurState = NewState; return OutSymb; } |
Настройте защитный блок таким образом, чтобы он пропускал все команды, кроме запрещенных, вместо которых на выходе должна появиться безопасная выходная последовательность (см. таблицу).
Запрещенная входная
|
Выходная последовательность |
1F10AE |
1F10A1 |
Результат выполнения задачи – файл с прошивкой защитного блока.
Комментарий. К задаче прилагается: программа обучения и тестирования защитного блока.
Защитный блок устроен следующим образом: при подаче на вход символа выполняется две операции:
1. по функции выходов определяется, какой символ будет на выходе. Он зависит от текущего активного состояния (выделенная строка в таблице выходов) и подданного на вход символа (столбец в таблице выходов). Значение ячейки на пересечении строки и столбца – это и есть выходной символ;По таблицам переходов и выходов видно, что алфавит составляет 16 символов (16 столбцов), и число состояний равно 16 (16 строк в таблице). Изначально активным считается состояние 0.
Чтобы определить последовательность входных символов необходимо следующее:
- при подаче очередного символа последовательности изменять активное состояние;
- при подаче символа не из последовательности сбрасывать активное состояние в начальное.
Чтобы изменить последний символ последовательности необходимо следующее:
- определить, что предыдущие символы принадлежат искомой последовательности;
- при подаче на вход последнего символа последовательности изменить выходной символ в таблице выходов.
Поскольку всего возможно 16 состояний, то максимум такой блок может отслеживать последовательность длиной 16 символов. По условию требуется последовательность длиной 6 символа. Предлагается выделить следующие состояния:
- состояние 0 – не введена никакая последовательность;
- состояние 1 – введена последовательность 1;
- состояние 2 – введена последовательность 1F;
- состояние 3 – введена последовательность 1F1;
- состояние 4 – введена последовательность 1F10;
- состояние 5 – введена последовательность 1F10A;
- состояние 6 – введена последовательность 1F10AE.
Замена последовательности 1F10AE на 1F10A1
1. При подаче на вход первого символа 1 необходимо перейти из любого состояния в состояние 1. Для этого в таблице переходов необходимо заменить ячейки:
StateMas[i][1] = 1, i = 0,1,...,F, кроме i=2.
2. Если на вход подается символом F и активным является состояние 1 (ввод символа 1), значит это продолжение последовательности и необходимо перейти в состояние 2. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[1][F] = 2.
Остальные незадействованные ячейки в строке 1 должны быть равны 0.
3. Если на вход подается символом 1 и активным является состояние 2 (ввод символов 1F), значит это продолжение последовательности и необходимо перейти в состояние 3. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[2][1] = 3.
Остальные незадействованные ячейки в строке 2 должны быть равны 0.
4. Если на вход подается символом 0 и активным является состояние 3 (ввод символов 1F1), значит это продолжение последовательности и необходимо перейти в состояние 4. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[3][0] = 4.
Остальные незадействованные ячейки в строке 3 должны быть равны 0.
5. Если на вход подается символом A и активным является состояние 4 (ввод символов 1F10), значит это продолжение последовательности и необходимо перейти в состояние 5. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[4][A] = 5.
Остальные незадействованные ячейки в строке 4 должны быть равны 0.
6. Если на вход подается символом E и активным является состояние 5 (ввод символов 1F10A), значит это окончание последовательности и необходимо перейти в состояние 6 либо в состояние 0. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[5][E] = 6.
Остальные незадействованные ячейки в строке 5 должны быть равны 0.
Кроме того, необходимо изменить выходной символ E->1. Для этого необходимо изменить ячейку в таблице выходов:
OutMas[5][E] = 1.