Я пытаюсь решить DFA

Вы можете выполнить формальную конструкцию декартовой машины, чтобы алгоритмически вывести автоматы для пересечения и объединения L1 и L2. Однако, поскольку эти языки настолько просты, может быть проще указать языки и просто написать DFA для каждого из них.

L1 — это язык всех строк as и bs хотя бы с одним a. L2 — это язык всех строк as и bs, содержащих не менее двух bs.

Чтобы принять пересечение L1 и L2, нам нужно увидеть хотя бы один as и два bs. Ниже у нас есть шесть состояний:

1. q0, начальное состояние, где нам нужно одно a и два bs
2. q1, где нам еще нужны два bs
3. q2, где нам еще нужен один b
4. q3, где нам больше не нужно (состояние принятия)
5. q4, где нам еще нужны один a и один b

6. q5, где нам еще нужен один a

   --->q0-a->q1-b->q2-b->q3 -b->q4-a->q2 q3 -b->q5-a->q3

(где переходы отсутствуют, это самоциклы)

Обратите внимание, что есть шесть состояний: это то же самое, как если бы мы построили декартово произведение машины на исходных ДКА с двумя и тремя состояниями соответственно.

Для объединения мы можем использовать точно такой же DFA и изменить набор допускающих состояний на q1, q3, q5. Это фиксирует тот факт, что мы теперь принимаем, когда одно из условий истинно (и состояния q1 и q5 находятся там, где выполняется одно, но не оба (как в q3) условия).