Comprovando a regularidade de um determinado idioma

7

Eu estive mexendo com esse problema durante a última hora e estou incrivelmente perplexo.

Seja . Mostre que é regular.A={0ku0kk1 and uΣ}A

Obviamente, a linguagem satisfaz o lema de bombeamento, mas isso não é conclusivo para a regularidade. Como diabos eu provo que esse idioma é regular? Estou ciente de todos os métodos normais (fechado), mas não consigo descobrir a condição apropriada para continuar.

Dave
fonte

Respostas:

14

É uma pergunta complicada. Você pode encontrar uma forma mais simples para descrever o idioma.

Hendrik Jan
fonte
... e sim, conheço a solução, mas achei que seria mais útil dar uma cutucada na direção certa, em vez de anotá-la na íntegra. Apenas minha ideia.
Hendrik Jan
10

O idioma pode ser reescrito como .A={0u0uΣ}

A idéia básica é que não importa qual seja o valor de , tudo será "absorvido" em que é a linguagem completa .kuΣ

Ayush Agarwal
fonte
mas como 'u' é a linguagem completa, não poderia ser também a string vazia? quais serão as implicações se 'u' for a string vazia?
Shubham Singh raw5 /
@ShubhamSinghrawat Sim, mas isso não tem implicações. Lembre-se de que um idioma é regular se existir um DFA que o reconheça. considerar a palavra . Esta resposta está lhe dizendo que, em vez de vê-la dessa maneira, você pode vê-la como a palavra com e você pode ver que isso corresponde à definição das palavras em , mas também à definição desta resposta. No final, o DFA para A é simplesmente: verifique se a primeira letra é e se a última letra é , tudo o resto não importa. w=03ϵ03Aw=01u01u=0202ΣA00
Bakuriu 5/10
Se isso não foi suficientemente claro, um NFA que reconhece é apenas com e e, na verdade, esse é quase um DFA, exceto que não é total ...AN=(Q,Σ,Δ,q0,{q2})Q={q0,q1,q2}
Δ={(q0,0,q1),(q1,0,q2),(q2,0,q2)}{(q1,x,q1)xΣ{0}}{(q2,x,q1)xΣ{0}}
Bakuriu
8

Se fosse esse idioma:

B={0k1u10kk1 and uΣ}

você estaria com problemas. não é regular.B

O problema fundamental é que ao tentar reconhecer cordas de , é preciso "lembrar" uma quantidade ilimitada de informação da seqüência inicial de s (quantos foram), porque você precisa distinguir entre as cordas como e outros como (onde ). Expressões regulares (ou DFAs) não conseguem expressar esse tipo de "memória ilimitada".B00k1...10k0k1...10jjk

A aparência , como ele tem o mesmo problema, mas na verdade não há necessidade de dizer aos "equilibradas" e "desequilibrado" casos separados. Para qualquer sequência (se e são iguais, mas ambos são pelo menos 1), você também pode escrevê-la como , em que . Tal seqüência também atende a regra para cordas 's (escolhendo e ), e por isso não realmente importa que os esquerda e à direita s foram equilibrados, afinal.0ku0jjk0v0v=0k1u0j1Ak=1u=v0

Ben
fonte