DFA, который принимает строку с нечетным числом 1 и нечетным числом 0 - PullRequest
Новая
       13

DFA, который принимает строку с нечетным числом 1 и нечетным числом 0

1 голос
/ 11 апреля 2019

Я хочу генерацию DFA, которая будет принимать строку, имеющую нечетное число 1 и нечетное число 0 .

Ответы [ 2 ]

0 голосов
/ 14 апреля 2019

Означает, что вы хотите DFA для odd-odd language

, вот DFA, который вам требуется enter image description here

, смотрите здесь, когда вы подаете заявку 0 он не принял .. затем вы подаете 1 он достигнет конечного состояния.Так как DFA принимает нечетное число '0's и нечетное число '1's. Он будет принимать строки, если их длина нечетная. Вы можете запустить строки в DFA, чтобы проверить это.Надеюсь, это поможет вам

0 голосов
/ 11 апреля 2019

Во-первых, давайте создадим DFA, который принимает нечетное число 0. Нам нужно хотя бы одно состояние, иначе мы ничего не сможем принять.Это состояние не может быть принято, поскольку пустая строка ведет туда, а пустая строка не имеет нечетного числа 0. Итак, нам нужно как минимум два состояния - начальное состояние, которое не принимает, и состояние принятия.Нужно ли нам больше?

Чтобы ответить на этот вопрос, давайте начнем заполнять переходы и посмотрим, где мы получим.Должен быть переход, исходящий из принимающего состояния.Куда это идет?Если он идет сам по себе, то мы не принимаем строку 0, которая имеет нечетное число (один), равное 0. Поэтому нам нужно перейти в какое-либо принимающее состояние на 0 в исходном состоянии.У нас так получилось, что мы уже принимаем государство;пойдем туда.

Далее у нас должен быть переход из принимающего состояния.Если мы вернемся в состояние принятия, мы примем строку 00, поэтому мы не можем этого сделать.Мы должны перейти в какое-то непринятое состояние.У нас уже есть непринятое состояние - наше начальное состояние - так что выбор может сработать.В качестве альтернативы, если нет, мы должны ввести новое состояние.Давайте сначала рассмотрим, работает ли возврат в исходное состояние, поскольку в этом случае мы закончили.

Мы уже пришли к выводу, что строки 0 и 00 обрабатываются правильно.С тех пор 000 будет обрабатываться правильно, так как мы возвращаемся в состояние принятия из начального состояния в последующие 0;действительно, мы возвращаемся в исходное состояние в 0 ^ 2k и в принимающее состояние в 0 ^ (2k + 1) при k> = 0. Следовательно, этот DFA корректен для языка строк с нечетными числами 0.диаграмма выглядит следующим образом: 

        /---0----\
        |        |
        V        |
----->(q0)--0-->(q1)

Изменяя метки, мы можем получить автомат для языка строк нечетных чисел 1: 

        /---1----\
        |        |
        V        |
----->(q2)--1-->(q3)

Чтобы получить автомат, принимающий строки, содержащие нечетныечисла 0 и 1, представьте, что оба автомата запускаются одновременно: всякий раз, когда мы видим 0, мы передаем его первому, а всякий раз, когда мы видим 1, мы передаем второму.Затем мы принимаем, оказались ли оба автомата в состоянии принятия.Мы можем представить объединенное состояние двух автоматов, рассматривая все четыре пары состояний из первого и второго автоматов как состояния нового комбинированного автомата, график переходов которого выглядит следующим образом: 

          /----0----\
          |         |
          V         |
----->(q0,q2)--0-->(q1,q2)
       ^  |         ^  |
       |  1         |  1
       1  |         1  |
       |  V         |  V
      (q0,q3)--0-->(q1,q3)
          ^         |
          |         |
          \----0----/

Это интуиция, лежащая в основе теоремы Майхилла-Нерода о регулярности языков и машинной конструкции декартовых произведений для пересечения регулярных языков.

...