Perguntas com links

4 votos
1 resposta
288 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 ...
Igor Da Silva Lagaggio's user avatar
-7 votos
2 respostas
1mil visitas

Regex - pegar apenas a primeira ocorrência de uma palavra em Python? [fechada]

Em uma string, existem várias ocorrências de uma palavra, porém, quero pegar apenas a primeira ocorrência desta, como fazer? Abaixo vem 'primeiro' duas vezes, porém, desejo somente o primeiro. re....
Perciliano's user avatar
15 votos
1 resposta
488 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 ...
Jefferson Quesado's user avatar
7 votos
6 respostas
974 visitas

Qual o motivo da aplicação do conceito LIFO (Last In, First Out)?

Existe uma vantagem na implementação do conceito LIFO (Last In, First Out) ou é só uma questão semântica para representar uma ordem na lógica do algoritmo?
raphael's user avatar
  • 2.307
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’...
Luiz Augusto's user avatar
  • 2.490
4 votos
1 resposta
485 visitas

Reduzir gramáticas na hierarquia de Chomsky

Sei que pela hierarquia de Chomsky, toda gramática regular é também uma gramática livre de contexto. Analogamente, sei que uma gramática livre de contexto também é uma gramática sensível ao contexto e ...
Léo Eduardo Silva's user avatar
46 votos
2 respostas
6mil visitas

O que é um problema de parada de Turing?

Eu já li e reli no Wikipédia, já assisti uns 15 videos em inglês e em português sobre esse assunto, já li vários artigos no google, mas não consigo entender. Por que ela entraria num loop infinito? ...
Nakamoto's user avatar
  • 1.361
5 votos
2 respostas
2mil visitas

Como obter a representação de um número inteiro positivo em binário, usando recursão?

Procurei por vários sites, e em nenhum eu consegui entender como fazer um código de conversão usando recursão de um inteiro positivo para binário. Eu conheço que existe a função itoa porém o desafio ...
Braian Freitas's user avatar
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 ...
Jefferson Quesado's user avatar
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?
viana's user avatar
  • 27,7mil
17 votos
3 respostas
941 visitas

Problema da parada pode ser resolvido na prática?

O problema da parada pode ser explicado como: dado um programa e uma entrada para o mesmo, ele vai completar sua execução e retornar uma resposta ou entrará em um ciclo infinito? Isso foi provado ...
Guilherme Bernal's user avatar
10 votos
1 resposta
1mil 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?
João Neto's user avatar
  • 2.736