DFA :- все строки, в которых каждый блок из пяти последовательных символов содержит не менее двух нулей

У меня есть ответ, но я не уверен, что он самый эффективный. Я постараюсь объяснить свое понимание, пока я просматриваю решение.

Мы должны построить DFA так, чтобы каждая подстрока длиной 5 содержала не менее 2 нулей. Таким образом, язык будет содержать все строки ‹= 5 без ограничений + длина строк (>=5) с заданными ограничениями.

Сложность в вопросе возникает из-за того, что мы должны отслеживать 2 вещи:

а) Длина строки

б) Проверка, содержит ли подстрока длиной 5 не менее 2 нулей.

Я постараюсь нарисовать все возможные состояния: DFA

Мы отслеживаем 0 и 1 по мере их появления в подстроке.

Как только мы получим 2 0 в подстроке длиной 5 [которая появляется на 5-м уровне дерева], мы вернемся в исходное состояние и начнем снова. Мы расширяем дерево, пока не достигнем желаемого состояния 2 0 для каждой подстроки длиной 5. Затем мы снова разветвляемся к началу дерева. Мы убедились, что у нас не будет подстроки длиной 5, нарушающей правило таким образом.

По теореме Майхилла-Нероде наименьший возможный ДКА для этого языка имеет 12 состояний.

Государственный номер должен фиксировать:

1. Количество символов, увиденных на данный момент в текущем блоке: 0-4
2. Видели ли вы 0, 1 или ›=2 нуля в блоке до сих пор.

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

Состояния (0,1), (0,2) и (1,2) не могут возникнуть, потому что вы не можете видеть больше нулей, чем символов в текущем блоке.

Состояние (4,0) -- 4 символа в текущем блоке, но до сих пор нет нулей, является состоянием ошибки, так как оттуда не получится перейти к акцепту.

Я предлагаю вам записать 15 возможных состояний, таких как (00) (01) (02) (10) (11) ... (42) в массиве 5x3. Отметьте (00) как начальное состояние, отметьте все допускающие состояния, а затем нарисуйте 2 перехода из каждого состояния — один для 0 и один для не-0.

Я смог найти для него решение, однако оно может быть не самым эффективным. Мое решение — полное бинарное дерево, которое работает как дерево вероятностей, т. е. если 0 — 0 — 0 — 0 — 0 истинное состояние 0 — 0 — 0 — 0 — 1 истинное состояние 0 — 0 — 0 — 1 — 1 истинное состояние 0 - 0 - 1 - 1 - 1 истинное состояние 0 - 1 - 0 - 0 - 0 истинное состояние 1 - 0 - 0 - 0 - 1 истинное состояние... однако идея заключается в том, что всякий раз, когда вы заканчиваете все истинные состояния , вы добавляете к ним 4 разных состояния. При этом в последнем состоянии, если оно было истинным, оно возвращается в первое исходное состояние.

Если вы хотите, чтобы такая строка была принята, вы можете использовать хороший подход.

-> Вы не хотите иметь 11111, 11110, 11101, 11011, 10111, 01111,

как подстроки, так как только они имеют менее 2 нулей

Вы рисуете DFA, в котором нет этих вышеперечисленных строк в качестве подстрок, и вы получаете хороший, простой и короткий DFA.

Вот пример для строк длиной 4. Это должно дать вам некоторое представление о том, как это сделать для блока из 5 символов. Красные кружки обозначают состояние ловушки, в котором строка больше не принимается.

Вместо того, чтобы думать о том, что сработает, подумайте о том, что не сработает, а затем поработайте над аналогичными шаблонами...

Шаг 1] Если вы получите эти случаи 1111, 10111, 11011, 11101, строка войдет в состояние дампа (q4).

Шаг 2] Было бы заполнить пробелы в каждом состоянии, выискивая шаблоны.

Пример:
-› в состоянии q5(10) -› если 0 [1.e 100] означает, что вы перезапускаете проверку последовательности аналогично (00000).
-› для состояния q6(101) -› если 0 [т.е. 1010] -› вы можете видеть, что это повторяется, поэтому в состоянии q6 (101) он вернется к q5 (10),
-› в состоянии q7 (1011) -› если 0 [т.е. 10110] --> это приведет к повторению q8(110),
--> в состоянии q8(110) --> если 0 [т.е. 1100] --> равно повторению последовательности, поэтому обратно к началу,
-› в состоянии q9(1101) -› если 0 [т.е. 11010] -› вы видите, что 10 повторяется, поэтому q5(10),
-› в состоянии q10(1110) -› если 0 [т.е. 11100] - › т.е. снова перезапустить.

Нам нужно как минимум 48 различных состояний, чтобы определить автомат, который принимает такой язык. Предполагая, что мы уже просканировали часть строки, так что длина просканированной до сих пор строки больше или равна 5, мы имеем дело с 32 остаточными состояниями, которые варьируются от 00000, 00001 до 11111. Пример того, как будет работать функция перехода: d(00111, 1) = 01111, т.е. путем простого сдвига значения текущего состояния влево на 1 и добавления имеющегося алфавита. Набором всех конечных состояний будут состояния, имеющие 2 или более нулей, например, 00000, 10011, 10110, 10000 и т. д. Теперь, поскольку нам сказали принимать также строки меньше 5. Мы не можем инициализировать состояние 00000 как начальное состояние. Например, если на машину подается число 1111, дельта(00000, 1111) = 01111, где дельта = функция расширенного перехода. Обратите внимание, что несмотря на принадлежность 1111 к определенному языку, 01111 не является принимающим состоянием. Итак, нам нужно отслеживать 4 начальных символа, если они есть, и способ сделать это — построить двоичное дерево с уровнями, имеющими 1 (начальное состояние), 2, 4, 8 и 16 состояний для первых 4 символов, что дает нам в общей сложности 63 различных штата. Обратите внимание, что каждое состояние в дереве является принимающим состоянием. Однако можем ли мы сделать лучше? Как оказалось, да, мы можем. Вместо того, чтобы строить дерево с 31 различным состоянием, мы можем определить 16 различных состояний, которые собирают информацию о первых 4 символах, начиная с 0000 до 1111, все из которых являются принимающими состояниями. На этот раз общее количество состояний оказывается равным 48. Обратите внимание, что состояние 0000 является начальным состоянием.