DFA двух простых языков, а затем создание продукта этих двух языков

Question

Язык ниже является пересечением двух более простых языков.Сначала определите более простые языки и дайте диаграммы состояний DFA, которые их распознают.Затем используйте конструкцию продукта для создания DFA, который распознает язык, указанный ниже;дать диаграмму состояний до и после упрощения, если есть какие-либо ненужные состояния или состояния, которые можно объединить.

Язык: {w является членом {0,1} * |w содержит нечетное число 0, а сумма его 0 и 1 равна 1}

Это мое предлагаемое решение: https://imgur.com/a/lh5Hwfr Должны ли нижние два состояния быть связаны с 0s?

Кроме того, что было бы DFA, если бы это было ИЛИ вместо AND?

Answer 1

Вот рисунок, который, я надеюсь, поможет понять, как это сделать:

Язык A - это "нечетное число нулей".Состояния помечены Z0 и Z1, указывая четное или нечетное число нулей.

Язык B - это «ровно один» (что эквивалентно «сумме цифр равно единице»).Состояния помечены как I0, I1 и I2, обозначая ноль, один или несколько единиц.

Язык A + B можно интерпретировать как A∩B (игнорируя пунктирные круги) или AUB (считая пунктирные круги).При построении A∩B состояния Z0I2 и Z1I2 могут быть объединены вместе.

Я надеюсь, что это дает не только ответ на точную проблему в вопросе, но также и идею, как построить аналогичные ответы для подобных проблем.