Детерминированный конечный автомат для сравнения Modulo

Question

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

Вы можете создавать строки, изготовленные из х-х и у-х. Как создать диаграмму, которая принимает только язык, когда число (x mod 4) больше числа (y mod 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) 

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

Answer 1

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

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

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

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

>(0,0) -y-> (0,1) 
    x 
(1,0)