Idiomas que satisfazem o lema de bombeamento, mas não são regulares?

18

Dada uma linguagem regular , é fácil provar que existe um constante, como , com existem cadeias , e modo que e e, para todo , éLNσL|σ|Nαβγ|αβ|N|β|ϵkαβkγL. É amplamente afirmado que o inverso não é verdadeiro, mas não vi nenhum exemplo claro. Alguma sugestão? Claramente, a prova de que a linguagem ofensiva não é regular deve usar métodos mais fortes do que o típico "não satisfaz o lema da bomba". Eu estaria interessado em exemplos simples, para apresentar em aulas introdutórias de idiomas formais.

vonbrand
fonte
existe uma sutileza que é verdadeira apenas para RLs com palavras infinitas . A wikipedia tem um exemplo .
vzn
Na minha definição, uma palavra (string) é finita .
vonbrand

Respostas:

16

A linguagem parece ser simples. A segunda parte é regular (e pode ser bombeada). A primeira parte não é regular, mas pode ser bombeada "para dentro" da segunda parte, escolhendo $ para bombear.{$anbnn1}{$kwk1,w{a,b}}$

(adicionado) Obviamente, isso pode ser generalizado para para qualquer L { a , b } . Às vezes, a formulação está no estilo "se ... então ...": se w começa com um único $ , é da forma. Que eu pessoalmente acho menos intuitivo.$L{$kk1}{a,b} L{a,b}w$

Conforme observado por @vonbrand, a parte (possivelmente) não regular do idioma é isolada pela interseção com . Isso pode ser testado separadamente usando o lema de bombeamento, se necessário.${a,b}

Hendrik Jan
fonte
Obrigado! Isso certamente se encaixa na conta. Ainda estou interessado em mais exemplos.
vonbrand
Ah, e para ser completo: para provar que isso não é regular, cruze com e apague $ com um homomorfismo. $ab$
precisa saber é