Создайте DFA для следующего языка: все строки, имеющие как минимум три 0 и максимум два 1

Question

Я должен построить DFA из пересечения двух более простых DFA. Первый более простой DFA распознает языки всех строк, которые имеют по крайней мере три 0, а второй более простой язык DFA распознает языки строк не более двух 1. Алфавит (0,1). Я не уверен, как построить больший DFA, объединяющий два. Спасибо!

Answer 1

Вот общая идея:

Самый простой способ сделать это - использовать разные пути для подсчета ваших 0, основанные на количестве 1, которые вы видели, так, чтобы они были "параллельными"друг другу.Переходите от одного слоя пути к следующему в любое время, когда вы видите 1, а затем переходите от последнего слоя к состоянию ловушки, если вы видите третий 1. В зависимости от точного характера задания вы можете сжать это, но если у вас есть базовый макет, вы можете определить это.Обычно вы можете комбинировать состояния из первого DFA со состояниями во втором DFA для получения меньшего конечного результата.

Вот более математическое объяснение :

Построение автоматов для операции пересечения.
Предположим, нам даны два DFA M1 = (S1, q (1) 0, T1, F1) и M2 = (S2, q (2) 0, T2,F2).Эти два DFA распознают языки L1 = L (M1) и L2 = L (M2).Мы хотим создать DFA M = (S, q0, T, F), который распознает пересечение L1 ∩L2.Мы используем идею построения DFA для объединения языков.Учитывая вход w, мы запускаем M1 и M2 на w одновременно, как мы объясняли для операции объединения.Как только мы закончим серии M1 и M2 на w, мы посмотрим на конечные состояния этих двух серий.Если оба конечных состояния принимают, то мы принимаем w, в противном случае мы отклоняем w.

---

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

Теперь мы можем объединить их, пройдя оба DFA одновременно.Например, оба начинаются с состояния 1. Теперь, что произойдет, если мы увидим a в качестве ввода?Ну, DFA1 будет идти от 1-> 2, а DFA2 будет идти от 1-> 3.Таким образом, при объединении можно сказать, что пересечение перейдет из состояния «1,1» (оба DFA находятся в состоянии 1) в состояние «2,3».Состояние 2 является состоянием принятия в DFA1 , а состояние 3 является состоянием принятия в DFA2, поэтому состояние "2,3" является состоянием принятия в нашем новом DFA3.Мы можем повторить это для всех состояний / переходов и получить:

Имеет ли это смысл?

Ссылка: Изображения, найденные в этого назначения из Корнельского университета.

Answer 2

Простейшим способом было бы использование модели 2DFA : из конечного состояния первого DFA (тестируемого по крайней мере для 3 нулей) перейти в начальное состояние второго и вернуться к начало ввода. Затем позвольте второму DFA проверить строку.