Внедрение DFA для ни одной серии длиной менее 4 для ввода (a, b)

Опубликовано: 22 Сентября, 2022

DFA или детерминированные конечные автоматы — это конечный автомат, в котором для каждого входного алфавита выполняется переход из одного состояния в другое в соответствии с набором определенных правил в соответствии с необходимостью принятия строки.
В этой конкретной задаче нужно думать о сериях длины . Входными алфавитами являются {a, b}. Отсутствие серий длиной менее 4 означает, что любые входные алфавиты повторяются минимум 4 раза.

Пример:

Input: n = “aaabab”
Output: string not accepted
Explanation: The starting letter a is not repeated at least 4 times. Hence DFA failed.

Input: n = “aaaabbbbaaaabbbbbaaaaa”
Output: string accepted
Explanation: Every unique occurrence of a and b are repeated at least 4 times. Hence DFA passed.

Пошаговое проектирование DFA:
Шаг 1: Сначала мы должны подумать о том, какой входной алфавит вводится. Так как это минимум 4 прогона длины. Возьмите входной алфавит «a» в состоянии «A» и отметьте это состояние как начальное состояние. На входе «а» происходит следующий переход:

  • Из состояния «А» в состояние «Б»
  • Из состояния «В» в состояние «С».
  • Из состояния «С» в состояние «D».
  • Из состояния «D» в состояние «E»

Шаг 2: Как и в предыдущем шаге, вводятся минимум 4 a, что является приемлемым, поэтому состояние «E» является окончательным. Также допустимы прогоны длиной более 4, поэтому поместите цикл «a» в конечное состояние «E».

Шаг 3: До сих пор проектирование машины выполнялось с входным алфавитом «a». Но осталось разобраться с входным алфавитом «b» состояния «A». Теперь выполните тот же процесс с входным алфавитом «b» в состоянии «A». Следующий переход происходит на входе «b»:

  • Из состояния «А» в состояние «F»
  • Из состояния «F» в состояние «G».
  • Из состояния «G» в состояние «H»
  • Из состояния «H» в состояние «Q»

Отметьте состояние «Q» как конечное состояние. А также допустимы прогоны длиной более 4, поэтому поставьте цикл на конечное состояние «Q».

Шаг 4: До сих пор мы работали только с одним входом a или b, т. е. aaaa и bbbb, но теперь имеем дело с обоими входами, такими как aaaabbbbb или aaaabbbbaaaaa и т. д.
Для этого переход входа «b» из состояния «E» в состояние «F» и переход входа «a» из состояния «Q» в состояние «B».

Шаг 5: Теперь имеем дело с оставшимися входными алфавитами, до сих пор разработанная машина покрывала все возможные допустимые случаи, и ни один из оставшихся входных алфавитов не перейдет в мертвое состояние «DS».

Таблица переходов вышеуказанного DFA:
Здесь «A» — начальное состояние, а «E» и «Q» — конечные состояния. DS называется МЕРТВЫМ СОСТОЯНИЕМ

Реализация Python выше DFA:

РЕКОМЕНДУЕМЫЕ СТАТЬИ