É

9

Fiz meus exames de teoria da computação há algumas semanas e essa foi uma das perguntas:

Assuma o idiomaL={(anbm)rn,m,r0}

L é regular? Se sim, forneça uma expressão regular ou um autômato.

Depois que eu lhe perguntei brevemente a resposta após o exame, parece que é realmente regular (acredito que ele disse que a expressão é simples ). No entanto, não consigo entender por que isso acontece. Do jeito que eu vejo, é concatenar r vezes, assim:a n b m(ab)anbm

anbmanbmanbm...anbmanbm ,

que não é regular, pois não há caminho para um autômato recordar n e estou cada vez. Onde estou em falta aqui?

EDIT: Conversei com o professor novamente, ele admitiu que foi um erro. A linguagem não é de fato regular.

Exci
fonte
14
Você deve perguntar ao professor se o idioma é o mesmo que o idioma . Se ele disser "sim", diga a ele que eu lhe disse que a pergunta dele estava mal formada. K = { a n 1 b m 1 a n 2 b m 2a n r b n rr 0 , a 1 , , a r0 , b 1 , , b r0 }LK={an1bm1an2bm2anrbnrr0,a1,,ar0,b1,,br0}
Andrej Bauer
11
Essa parece a única maneira de ser regular e, de fato, é o que eu originalmente pensava e considerava apressadamente (a b ) *, mas depois a apaguei, percebendo que n e m permanecem os mesmos (ou deveriam ..) e deram uma desaprovação do lema de bombeamento para r = 2, dizendo o mesmo aplicado para r maior (provavelmente também não é exatamente uma solução completa, mas parece estar na direção certa). Escusado será dizer que eu tenho 0 para essa pergunta. Vou tentar entrar em contato com ele.
Eu certamente entenderia a pergunta da maneira que você fez inicialmente.
Andrej Bauer
Veja aqui mais maneiras de mostrar que um idioma não é regular.
Raphael
você também pode revelar-se o mesmo com a ajuda de bombeamento lema
SAHIL Thukral

Respostas:

10

Lwn=anbnNwn2LnmwnwmLLwn

Yuval Filmus
fonte
4

r=2r

LLabab={anbanbn0}r=2m=1

Hendrik Jan
fonte
11
LLL
11
LRLR
11
Claro. Eu estava preocupado que os novatos pudessem ler "definindo efetivamente ..." e aplicá-lo sem usar as propriedades de fechamento.
Raphael
0

O idioma: {(a n b m ) r | n, m, r≥0} não é regular, porque enquanto o autômato / máquina lê a primeira sequência de letras 'a' e depois as letras 'b', precisa contar o número de vezes que leu a letra 'a' e o número de vezes que leu a letra 'b' na primeira sequência para saber o valor de n e m .

Se r> 1 , então um outro mesmo é esperado sequência de letras 'a' e 'b letras'.

Se o autômato / máquina não não sei quantas letras 'a' e letras 'b' lia-se na primeira sequência, então ele também não não sabe o valor de n e m e, portanto, pode não dizer se as outras sequências do penúltimo ao último são palavras que são iguais à primeira sequência.

Mas sabe-se que só Máquina de Turing pode contar e saber os valores de n e m e reconhecer a língua em cima, assim não apenas que a linguagem acima é não regular, mas mesmo também é não livre de contexto, ou seja, também faz não existe autômato de empilhamento para reconhecer esse idioma e não existe gramática livre de contexto, pois cada palavra derivada dessa gramática livre de contexto está no idioma acima.

Porque o fato de que tanto determinista finito autômato e pushdown finito autômato pode não contar e conhecer os valores de n e m , ao contrário de máquina de Turing, eles podem não reconhecer a língua acima e, portanto, a linguagem acima é não livre de contexto e não é regular.

Em contrapartida, supondo que o idioma acima seja regular:

Para n = 3 ∧ m = 5 ∧ r = 2 , a seguinte palavra está no idioma acima:

aaabbbbbaaabbbbb

Mas a seguinte palavra não está no idioma:

aaabbbbbaaaaabbb, porque se não existir n, m e r assim:

(a n b m ) r = aaabbbbbaaaaabbb, porque para satisfazer a primeira sequência de letras 'a' e depois as letras 'b', deve ser verdade que n = 3 ∧ m = 5 e porque vemos duas sequências de letras ' a 'e depois letras' b ', então r = 2 , mas se n = 3 ∧ m = 5 ∧ r = 2 então (a n b m ) r = (a 3 b 5 ) 2 = (aaabbbbb) 2 = aaabbbbb ) 2 = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, porque seus sufixos são diferentes, ou seja, aaabbbbb ≠ aaaaabbb, embora seus prefixos sejam iguais a aaabbbbb para r = 1.

O "melhor" autômato finito determinístico que pode ser construído para esse idioma é o autômato finito determinístico que reconhece a expressão regular (a * b *) *, mas não reconhece o idioma acima, porque indica que ambas as palavras aaabbbbbaaabbbbb e aaabbbbbaaaaabbb estão no idioma e isso não é verdade, porque aaabbbbbabaabbbbb está no idioma, mas aaabbbbbabaaaababb não está no idioma.

Mesmo o autômato finito de empilhamento não sabe dizer se as duas palavras estão no idioma ou não, então apenas a máquina de Turing pode.

Na segunda sequência, a máquina de Turing descobriu que n = 5 ∧ m = 3 e isso contradiz que na primeira sequência tenha encontrado que n = 3 ∧ m = 5 , de modo que indica que a segunda palavra não está no idioma , mas nenhuma contradição é encontrada na primeira palavra.

Ambas as seqüências satisfazem que n = 3 ∧ m = 5 , então a máquina de Turing diz que a primeira palavra está no idioma.

Só de Turing pode máquina, se ela é importante e lembra os valores de n e m escrevendo seu valor por si fita e depois lê-los.

Troca de despedida
fonte