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

10

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.

zic10
fonte

Respostas:

17

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:Lp

wpw=xyz|xy|p|y|1xyizLi0

{0p}p+1

x,yLzxzLyzLpLpL={0p}p+1ϵ,0,,0p

Yuval Filmus
fonte
sim zpode estar ^vazio, mas acho que você digitou um erro de digitação em sua cotação. xy^i ∈ L deveria ser #xy^i z ∈ L
Grijesh Chauhan
12

pp+10

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)

Alexis Beingessner
fonte
Boa resposta: explica muito sem abrir mão da solução para o que parece ser um exercício de lição de casa. Bem-vindo à Ciência da Computação !
David Richerby
1

a3aa3

vonbrand
fonte
-2

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 .

vzn
fonte
n
nn+1
@Yuval right. acho que essa idéia pode funcionar, mas talvez não tenho os detalhes exatamente certo, os detalhes são complicados, que acho que pode estar em algum lugar na literatura, mas não vi isso
vzn