Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 27

Имеется следующая таблица состояний автомата-автомата с двумя состояниями A и B, одним входом и одним выходом:

Present
State A
Present
State B
Input Next
State A
Next
State B
Output
0 0 0 0 0 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1

Если начальное состояние A = 0, B = 0, какова минимальная длина входной строки, которая переведет машину в состояние A = 0, B = 1 с выходом = 1?
(А) 3
(Б) 4
(С) 5
(D) 6

Ответ: (А)
Пояснение: // (0, 0) –1–> (0, 1) –0 -> (1, 0) –1–> (0, 1) и выход 1

В соответствии с вопросом мы должны достичь состояний A = 0, B = 1 и output = 1. Это состояние показано зеленым цветом. Таким образом, чтобы достичь конечных состояний как A = 0, B = 1 и output = 1, мы должны достичь предыдущих состояний A = 1, B = 0. Поскольку начальные состояния A = 0, B = 0 (красный); мы предоставляем input = 1 (для достижения A = 0, B = 1) Теперь это даст нынешние состояния как A = 0, B = 1 и output = 0. Теперь мы предоставляем (синий) вход = 0 (для достижения A = 1, B = 0) с текущими состояниями как A = 0, B = 1.
Текущее состояние станет A = 1, B = 0 и output = 0. Это то, что требуется. При обеспечении input = 1 мы получаем конечные состояния как A = 0, B = 1 и output = 1.
Следовательно, входная строка 3, то есть 101, приводит к желаемому результату и состояниям.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2009 | Вопрос 27

0.00 (0%) 0 votes