Skip to main content

Respostas interessantes marcadas com a tag

18 votos
Aceito

Expressão regular para reconhecer linguagem: palavras que não contenham "bbab"

Bom vejamos que o Linguagem L aceita seguindo a premissa: {a,b,c,d} - assim temos que os únicos caracteres presentes na linguagem são a,b,c,d * - todas as possíveis palavras que podem ser formadas ...
Guilherme Lautert's user avatar
18 votos
Aceito

O que é um autômato?

Não quer saber o que eles [autômatos] comem ou como eles se reproduzem? Maniero Junior, Antonio, 2017 Autômatos comem letras/tokens discretos, vivendo em espaços matemáticos. A priori, se a ...
Jefferson Quesado's user avatar
13 votos
Aceito

Uma máquina de estados finitos é capaz de detectar primalidade de um número?

Não é possível ter nenhum Autômato Finito Determinístico que reconheça números primos (ou reconheça números compostos, que é o subconjunto não trivial do complemento dos números primos). Uma ...
Jefferson Quesado's user avatar
8 votos
Aceito

Quais são diferenças do poder computacional dos autômatos com pilha determinístico e uma não determinístico?

Sim, existe diferença entre os dois. E ela é brutal. Autômatos de pilha não-determinísticos conseguem resolver muito mais linguagens livres de contexto do que os determinísticos. Gostaria de ...
Jefferson Quesado's user avatar
5 votos
Aceito

O que é um autômato celular?

Do que se trata o autômato celular? A primeira definição de Automato Celular Surgiu com Von Neumman nos anos 40 com a intenção de fornecer informações sobre os requisitos lógicos de uma Máquina ...
Daniel Gentil's user avatar
5 votos
Aceito

Diferença entre 'Linguagem regulares' para 'linguagem irregulares'

Bem, acho que a resposta aqui talvez não agrade muito, mas é a correta: uma linguagem regular é aquela que pode ser gerada por uma gramática regular. E, daí, o que seria uma gramática regular? Bem, ...
Jefferson Quesado's user avatar
4 votos

Por que uma Máquina de Turing com fita limitada não tem o mesmo poder computacional que um Autômato Finito?

Vamos fazer um experimento mental? Vamos começar uma máquina de Turing, tranquilo? Primeiro, vamos nos lembrar como que trabalha uma máquina de Turing? Ela é um conjunto de regras que, dado um símbolo ...
Jefferson Quesado's user avatar
4 votos
Aceito

O que é o Pumping Lemma (ou Lema do Bombeamento) ? E como aplicá-lo?

O que é o lema do bombeamento O lema do bombeamento é uma condição sine qua non de linguagens regulares/livres de contexto (dependendo de qual você esteja usando, claro). Porém, não é uma condição ...
Jefferson Quesado's user avatar
3 votos
Aceito

Como transformar uma gramática livre de contexto em um autômato de pilha?

Existe sim um algoritmo que permita fazer exatamente isso, transformar uma gramática qualquer em um autômato de pilha não determinístico. A ideia é que toda produção gramatical consuma, no máximo, um ...
Jefferson Quesado's user avatar
2 votos

Ajuda com na compreensão de código de autômato celular

Ele codificou bit a bit os "vizinhos". No bit 2 (valor 4), colocou o vizinho à esquerda: 4*L_ant[n-1] No bit 1 (valor 2), colocou o valor atual: 2*L_ant[n] Já no bit 0 (valor 1), colocou o ...
Jefferson Quesado's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible