Perguntas com a tag [autômatos]
Um autômato é posto para rodar sobre uma dada sequência de entradas em passos de tempo discretos. Para cada passo, um autômato recebe uma entrada que é obtida a partir de um conjunto de símbolos ou letras, que é chamado de alfabeto. Em qualquer momento, os símbolos que servem de entrada para o autômato formam uma sequência finita de símbolos, que é chamada de palavra.
14
perguntas
4
votos
1
resposta
230
visitas
Por que uma Máquina de Turing com fita limitada não tem o mesmo poder computacional que um Autômato Finito?
Uma Máquina de Turing com Fita Limitada possui uma fita finita, um conjunto de estados finitos e alfabetos finitos, correto? Portanto, pode assumir um conjunto de estados finitos. Sendo assim, por que ...
15
votos
1
resposta
415
visitas
Uma máquina de estados finitos é capaz de detectar primalidade de um número?
Recentemente vi uma publicação de como ensinaram ao Perl a reconhecer um número primo usando expressões regulares. A expressão regular em questão é:
/^1?$|^(11+?)\1+$/
O único requisito a essa ...
5
votos
1
resposta
2mil
visitas
Diferença entre 'Linguagem regulares' para 'linguagem irregulares'
Lendo uma questão sobre conceitos básicos de programação, deparo-me com a seguinte afirmação:
Sejam A e B duas linguagens sobre o alfabeto binário, isto é, sobre o
alfabeto composto apenas por 0’...
2
votos
1
resposta
56
visitas
Ajuda com na compreensão de código de autômato celular
Gostaria que vocês me ajudassem a entender um código para cálculo e apresentação de autômatos celulares que encontrei na internet. O código em questão é o seguinte:
#include <stdio.h>
#include ...
5
votos
1
resposta
637
visitas
O que é o Pumping Lemma (ou Lema do Bombeamento) ? E como aplicá-lo?
Estava lendo pelo HOPCROFT e tive dificuldade em aplicar o lema do bombeamento de maneira formal aos exercícios para provar que uma linguagem não é regular.
Neste caso, me refiro ao Lema do ...
21
votos
2
respostas
8mil
visitas
O que é um autômato?
Por várias vezes eu ouço discussões sobre autômatos, seja no chat ou em perguntas/respostas. Entretanto eu particularmente não sei o que é um autômato, não tenho nem ideia para falar a verdade. Quando ...
3
votos
1
resposta
713
visitas
Quais são diferenças do poder computacional dos autômatos com pilha determinístico e uma não determinístico?
Existe diferença de poder computacional entre um autômato com pilha determinístico e um não determinístico?
4
votos
1
resposta
2mil
visitas
Como transformar uma gramática livre de contexto em um autômato de pilha?
Eu tenho uma gramática, como por exemplo:
Ou então:
Ou mesmo essa:
Ou então essa gramática, que representa a lógica booleana para três variáveis:
Como transformar essas gramáticas em autômatos de ...
23
votos
1
resposta
2mil
visitas
Expressão regular para reconhecer linguagem: palavras que não contenham "bbab"
O @LINQ me desafiou a escrever uma expressão regular para reconhecer a seguinte linguagem L:
Consegui montar, sobre essa premissa, a seguinte máquina de estados finito:
o Miguel Angelo detectou um ...
9
votos
1
resposta
2mil
visitas
O que é um autômato celular?
Do que se trata o autômato celular? Que tipo de problema isso pode resolver? É algo equivalente às máquinas de Turing?
4
votos
2
respostas
346
visitas
Como é implementada a função find?
Diferentemente do match() que procura por uma ocorrência de uma linguagem y no início da string, o find() faz uma busca por y dentro dessa string. Eu poderia utilizar o algoritmo de Knuth-Morris-Pratt ...
10
votos
1
resposta
982
visitas
Qual a diferença entre autômatos e gramáticas?
Estou estudando sobre compiladores e relacionando as linguagens de programação. Qual a diferença entre autômatos e gramáticas?
4
votos
1
resposta
526
visitas
Qual simular, NFA ou DFA?
Bem, nós sabemos que teoricamente e praticamente, toda NFA pode ser convertida para uma DFA que aceite a mesma linguagem. Minha dúvida é a seguinte:
Qual eu devo realmente simular? NFA ou DFA? Eu não ...
5
votos
2
respostas
2mil
visitas
Qual o real significado de se utilizar ε-transições na NFA?
Bom, eu ainda não compreendo a lógica de se utilizar ε-transições na NFA, qual o real significado? Pular de estado sem efetuar uma leitura?
Por exemplo, dada a regex:
a*
NFA:
DFA: