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 ...
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 ...
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 ...
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 ...
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
...
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, ...
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 ...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Tags relacionadas
autômatos × 14teoria-da-computação × 7
linguagens-formais × 6
regex × 3
terminologia × 2
matemática × 2
c × 1
algoritmo × 1
ciência-da-computação × 1
pseudocódigo × 1
bitwise × 1