Prova de que não é regular

8

Mostre que não é regularL={an2|n0 0}

Ei pessoal. Eu estou tendo uma aula de CS e esse material é realmente novo para mim, então tenha paciência comigo. Tentei verificar se havia alguma contradição usando o lema de bombeamento para idiomas regulares e resolvi-o assim:

Suponha que seja regular. Então deve haver um número natural para todas as palavras em com comprimento existe uma decomposição , de modo que esteja no idioma para qualquer .eumzeu|z|mz=uvw,|uv|m,|v|>0u(vi)wi0

Considere a sequência .am2

Em seguida, , para alguns e . Então .uv=ak2=ax+ykmx=(k1)2
v=ay=a2k1

Seja . Então . Mas não é necessariamente um número natural -> Contradição! Portanto, não pode ser regular.i=2u(v2)w=ax+2yx+2yL

Bem, eu sei que esse caminho é desnecessariamente complicado e você pode provar isso de maneira diferente (eu já sei a solução mais simples). Mas minha pergunta aqui é: minha prova também é válida ou contém alguma falha? Está formalmente correto?

Agradeço qualquer feedback! Obrigado!

Gilles 'SO- parar de ser mau'
fonte
1
FYI - Expressões regulares, conforme definidas em ciência da computação teórica, e expressões regulares que os programadores usam são relacionadas, mas muito diferentes.
2
Você parece ter cometido alguns dos erros clássicos ao aplicar o lema de bombeamento. Observe nossa pergunta de referência para obter uma explicação detalhada e um exemplo.
Raphael
Isso não está correto, não. Seu argumento não pode depender de assumiruv=ak2.
Patrick87

Respostas:

8

Você não pode deduzir isso uv=ak2, tudo o que o lema de bombeamento fornece é que |uv|m. Nem todos os números são menores quemsão quadrados. Não apenas isso, mas mesmo supondo queuv=ak2, não há razão para supor que v=a2k1; todo o lema de bombeamento dá é quevnão está vazio. Finalmente, para obter uma contradição, não basta quex+2y não precisa ser um quadrado, não deve ser um quadrado! Desde ax e x+y são quadrados adjacentes, é verdade que x+2y não é um quadrado.

Yuval Filmus
fonte
Alguma dica de como consertar a prova?
Raphael
O OP "já conhece a solução mais simples", que eu assumo equivale à prova fixa.
Yuval Filmus
@YuvalFilmus Não necessariamente. Há uma prova bastante direta usando o teorema de Myhill-Nerode que não tem nada a ver com o lema de bombeamento. Pode ser o que o OP está se referindo.
precisa saber é o seguinte