Idioma regular não aceito pelo DFA com no máximo três estados

Descreva um idioma comum que não possa ser aceito por nenhum DFA que possua apenas três estados.

Não sei muito bem por onde começar e queria saber se alguém poderia me dar algumas dicas ou conselhos. Entendo que o lema de bombeamento pode ser usado para provar que um idioma não é regular, mas, nesse caso, deve ser um idioma regular. Se alguém tiver alguma opinião, isso será apreciado.

Pode-se afirmar que o lema de bombeamento leva em consideração o número de estados no DFA. Todo idioma aceito por um DFA com p estados satisfaz o seguinte lema de bombeamento:$L$$p$

$w$$p$$w=xyz$$|xy| \leq p$$|y| \geq 1$$xy^iz \in L$$i \geq 0$

$\{0^p\}$$p+1$

$x,y$$L$$z$$xz \in L$$yz \notin L$$p$$L$$p$$L = \{0^p\}$$p+1$$\epsilon,0,\ldots,0^p$

$p$$p+1$$0$

Essa é, em essência, toda a idéia por trás do lema de bombeamento: se uma corda é realmente longa, os autômatos finitos devem "esquecer" o quão alta é contada e começar tudo de novo, permitindo repetir uma seção várias vezes sem que ela se importe. .

Portanto, qualquer linguagem regular que exija contar até 3 para validar uma palavra, não pode ser descrita por um autômato finito de tamanho 3.

Você consegue pensar em um idioma assim? (Seu professor também pode esperar que você prove esse argumento de contagem, embora em meu currículo esse entendimento do lema de bombeamento tenha sido dado como certo)

$a^3 a^*$$a^3$

outra ideia, diagonalização ! enumere todos os DFAs com três ou menos estados, faça a união de todos eles e faça o complemento. este é um DFA pelo fechamento regular de operações de idioma. isso pode ser construído através de um algoritmo, mas a pergunta apenas pede uma descrição .