1. Главная
  2. Библиотека
  3. Высшая математика
  4. Автомат задан набором ({a,b},{q_1,q_2,q_3,q_4,q_5 },Q_s,Q_f ), где {a,b} – алфавит, Q_s – множество начальных состояний (в...

Автомат задан набором ({a,b},{q_1,q_2,q_3,q_4,q_5 },Q_s,Q_f ), где {a,b} – алфавит, Q_s – множество начальных состояний (входов), Q_s – множество конечных состояний (выходов), и списком дуг с метками,

«Автомат задан набором ({a,b},{q_1,q_2,q_3,q_4,q_5 },Q_s,Q_f ), где {a,b} – алфавит, Q_s – множество начальных состояний (входов), Q_s – множество конечных состояний (выходов), и списком дуг с метками,»
  • Высшая математика

Условие:

Автомат задан набором ({a, b}, {q1, q2 ,q3, q4, q5} Qs, Qf), где {a, b} – алфавит,  Qs – множество начальных состояний (входов),  Qf  – множество конечных состояний (выходов), и списком дуг с метками, определяющими допустимые переходы. Запись (i, j, a, b)  означает, что дуга (i, j), идущая из состояния qi в состояние qj , имеет две метки –  a и b.

Вход Qs={1} , выход Qf={4,5} , дуги 

1. Построить граф автомата и найти язык L, допустимый автоматом. 

2. Детерминизировать автомат. 

3. Построить графы автоматов, представляющих языки 

 

4. Из построенных  графов удалить -переходы. 

Решение:

1. Построить граф автомата и найти язык L , допустимый автоматом

Определяем язык автомата, решая систему уравнений.

Из начального состояния q1 все состояния достижимы:

2. Детерминизировать автомат.

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет