Детерминированные автоматы с конечным состоянием для сравнения по модулю

Я работаю над созданием детерминированного конечного автомата для следующей проблемы:

Вы можете создавать строки, состоящие из x и y. Как создать диаграмму, которая принимает язык только тогда, когда количество (x по модулю 4) больше, чем количество (у по модулю 4)?

В настоящее время я могу понять, что мне нужно создать диаграмму, подобную приведенной ниже:

>(0,0) -b-> (0,1) -b-> (0,2) -b-> (0,3) -b-> (0,4)
   a          a          a          a          a
 (1,0) -b-> (1,1) -b-> (1,2) -b-> (1,3) -b-> (1,4)
   a          a          a          a          a
 (2,0) -b-> (2,1) -b-> (2,2) -b-> (2,3) -b-> (2,4)
   a          a          a          a          a
 (3,0) -b-> (3,1) -b-> (3,2) -b-> (3,3) -b-> (3,4)
   a          a          a          a          a
 (4,0) -b-> (4,1) -b-> (4,2) -b-> (4,3) -b-> (4,4)

Но чего я не понимаю, так это того, как сравнивать количество раз, когда x и y встречаются относительно друг друга.


state-machine deterministic finite-automata
person sc1892353    schedule 07.09.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я пытаюсь ответить на ваш вопрос, определяя поведение DFA с помощью таблицы переходов вместо использования диаграммы переходов — здесь проще ввести таблицу, и она функционально эквивалентна соответствующей диаграмме переходов.

В таблице ниже

  • в первом столбце перечислены все состояния; каждое состояние представлено упорядоченной парой, элементы которой представляют, соответственно, количество x и количество y, прочитанных до сих пор
  • второй и третий столбцы содержат, соответственно, состояние, достигнутое при чтении x или y, когда DFA находится в состоянии, показанном в первом столбце таблицы.
  • состояния, выделенные желтым цветом, являются состояниями принятия: если DFA находится в одном из этих состояний после проверки последнего символа в строке, тогда строка принимается, то есть она принадлежит языку.

введите здесь описание изображения

Глядя на эту таблицу, вы легко сможете адаптировать свою диаграмму, чтобы все работало правильно. Например, первая строка в таблице соответствует следующей части диаграммы.

>(0,0) -y-> (0,1)
   x
 (1,0)
person mw215    schedule 08.09.2015