Autômato Finito Determinístico (AFD) com 2 "condições"

[KrilMun 0]

Bom dia amigos,

 

Venho novamente requisitar seu auxílio, a fim de solucionar um problema proposto por meu professor, a saber:

 

"Para cada linguagem a seguir apresente um AFD correspondente sobre Σ = {0, 1}.

a) {α ∈ Σ* : α possui no mínimo três 0's e no mínimo dois 1's}.

b) {α ∈ Σ* : α possui quantidade par de 0's e cada 0 é seguido por pelo menos um 1}."

Onde Σ é o conjunto e α é a palavra. OBS: ∈ = pertence a

 

O problema é que estou quebrando a cabeça com a questão A) desde ontem, e parece tão simples porém não consigo solucionar, pelo fato de pedir 2 condições simultaneamente.

 

Por exemplo, a questão A) poderia ser quebrada nos 2 AFDs abaixo:

 

Spoiler

 

Mínimo dois 1's

Mínimo três 0's

 

*Utilizei o software JFLAP para gerar os autômatos;

 

 

Porém eu não posso simplesmente concatenar os 2 autômatos, porque se eu concatenasse o primeiro com o segundo, por exemplo, não poderia inserir a palavra válida 00011, pelo fato de ser obrigado a inserir pelo menos dois 1's para apenas a partir daí poder contar os 0's, ou mesmo palavras que apenas passassem por tais estados muito a frente, mas que seriam válidas para o enunciado da questão, como 00000100111. Da mesma forma, se eu concatenasse o segundo com o primeiro, palavras como 11000 não seriam aceitas, por ter que inserir pelo menos três 0's para contar os 1's.

Não consigo pensar em uma forma de fazer um único autômato sem que haja Não Determinismo e/ou transições em vazio.

 

Já a questão B) eu consegui fazer, ficando da seguinte forma:

 

Spoiler

 

Mas a questão A) ainda está me dando um nó na cabeça hahaha

 

Agradeço de antemão a ajuda!

[_Isis_ 202]

E por que não faz um EFN ou AFN e converte em AFD?