Пусть задан недетерминированный конечный автомат - Ответ на вопрос по любому предмету №1171074

Вопрос

Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программойΦ: 0 b →​ 1, 0 →​ 2, 1 a →​ 2, 1 b →​ 4, 2 →​ 3, 2 →​ 5, 3 a →​ 4, 3 b →​ 2, 4 →​ 5Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

• M1 = < {a, b}, {0, 1, 2, 4 ,5}, 0, F1={0, 2, 4, 5}, Φ1> с программой Φ1: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 0 a →​ 5, 1 a →​ 2, 1 a →​ 5,1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• M4 = < {a, b}, {0, 1, 2, 4 }, 0, F4={0, 2, 4}, Φ4> с программойΦ4: 0 b →​ 1, 0 b →​ 2, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• M2 = < {a, b}, {0, 1, 2, 4 }, 0, F2={0, 2, 4}, Φ2> с программойΦ2: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• ни один из выше приведенных автоматов M1, M2, M3, M4
• M3 = < {a, b}, {0, 1, 2, 3, 4 }, 0, F3={0, 2, 4}, Φ3> с программойΦ3: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2, 3 a →​ 4, 3 b →​ 2

Ответ