Provas usando o lema de bombeamento regular

Eu tenho duas perguntas:

1. Eu considero o seguinte idioma

   $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ Em outras palavras $w$não é palíndromo com comprimento uniforme. Eu provei que esse idioma NÃO é regular, provando que seu complemento não é regular. Minha pergunta é como provar usando o lema de bombeamento sem usar o complemento.

2. Deixei

   $$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}.$$ Eu provei que esse idioma não é regular usando classes de equivalência. Como posso provar isso usando o lema de bombeamento?

Muito obrigado pela edição :)

Nem todos os idiomas não regulares são reprovados no teste do lema de bombeamento. A Wikipedia tem um exemplo irritantemente complexo de uma linguagem não regular que pode ser bombeada. Portanto, mesmo que um idioma não seja regular, talvez não possamos provar esse fato usando o lema de bombeamento.

Mas podemos usar o lema de bombeamento para provar que seu primeiro idioma não é regular. Não tenho certeza sobre o segundo.

Afirmação: $L_1$ não é regular.

Prova: pelo lema de bombeamento. Deixei$p$seja o comprimento do bombeamento. (Vou usar o alfabeto$\{a,b\}$ ao invés de $\{0,1\}$.) E se $p = 1$, então pegue a string $abbaa$, que está em $L_1$ e bombeá-lo para $aabbaa$ que não está em $L_1$, tão $L_1$ não seria regular.

E se $p > 1$, então pegue a string $a^pbba^{N}$. (Vamos descobrir o que queremos$N$ para ser posterior.) Em seguida, considere qualquer divisão da string em $xyz$ Onde $x=a^{p-k}$, $y=a^k$e $z=bba^{N}$.

Agora vamos bombear essa corda $i$vezes. (Vamos descobrir o que queremos$i$ para ser mais tarde.) Recebemos a string $xy^iz$, que dá $a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$.

Agora vamos voltar. Primeiro, escolhemos$N$. Então, alguma escolha de$k$foi feito. Então, escolhemos$i$. Queremos descobrir o que$N$ escolher para que, para qualquer escolha de $k \in [1,p]$, podemos escolher um $i$ que torna essa string um palíndromo, tornando o número de $a$s à esquerda é igual ao número à direita. (Ele sempre terá um comprimento uniforme.)

Então, queremos sempre conseguir isso $p-k+ik=N$. Se brincarmos com a matemática, achamos que devemos escolher$N=p+p!$ e escolher $i=p!/k+1$.

Então, para recapitular, escolhemos $N=p+p!$ e escolheu a string $a^pbba^N$. Então alguma escolha de$k$ foi feito para que a corda fosse composta de $a^{p-k}ybba^N$ Onde $y=a^k$. Então nós escolhemos$i=p!/k + 1$. Nós bombeamos a corda para obter$a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$.

Mas sabemos que $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. E$N=p+p!$. Então o número de$a$s em ambas as extremidades é o mesmo; portanto, a cadeia é um palíndromo de comprimento par; portanto, não está $L_1$, tão $L_1$ não é regular. $\square$

Para a primeira pergunta, a string $0^{p}1^{2p}0^{p+p!}$é um contra-exemplo adequado. Seja qual for o comprimento de$y$ é, deve ser um fator de $p!$, então bombeamos o suficiente e obtemos $p+p!$ zeros no início.

Depois de muito pensar, acho que respondi 2.

escolhemos string (010) ^ N (101) ^ N, em que N está bombeando o comprimento. Não importa o que y escolhermos, xy ^ 0z terá mais 101 do que 010. a idéia é que só podemos adicionar mais 101 sub-strings na primeira parte da string ou remover algumas sub-strings 010.