É

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

Assuma o idioma$L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

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 $(a^*b^*)^*$$a^nb^m$

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

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.

$L$$w_n = a^n b$$n \in \mathbb{N}$$w_n^2 \in L$$n \neq m$$w_n w_m \notin L$$L$$w_n$

$r=2$$r$

$L$$L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$$r=2$$m=1$

O idioma: {(a ⁿ 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 ⁿ 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 ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbb ) ² = 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.