Диаграмма состояния ДФА - PullRequest
Новая
       10

Диаграмма состояния ДФА

0 голосов
/ 22 января 2020

Дайте диаграмму перехода состояний DFA, которая распознает следующий язык по алфавиту {x, y}

  1. L1 = множество всех строк, которые начинаются с x и имеют нечетную длину
  2. L3 = множество всех строк, которые заканчиваются на x и имеют четную длину

И мне нужно найти L1 U L3.

Это мой ответ :

enter image description here

Левая часть моего ответа L1 (может быть, я могу убедиться в его правильности), я запутался в его правильности с правой стороны, мой ответ правильный или нет?

1 Ответ

0 голосов
/ 22 января 2020

Ваш ответ неверный. Вы можете сказать, думая о словах, которые должны быть на языке, который DFA не принимает, например xx, который является строкой четной длины, заканчивающейся на x, поэтому он является частью L3. Вы также пропускаете yyyx, который должен быть частью L3.

. То, что вы хотите сделать, это начать с эпсилон-NFA, где начальное состояние имеет два эпсилон-перехода к началу. состояния начальных состояний L1 и L3. Затем используйте алгоритм NFA-to-DFA, чтобы создать DFA, который принимает L1 U L3.

...