Perguntas com links

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
33 votos
2 respostas
8mil visitas

O que é uma linguagem livre de contexto?

No Wikipédia possui a seguinte afirmação: Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes ...
viana's user avatar
  • 27,7mil
21 votos
2 respostas
9mil 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 ...
UzumakiArtanis'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
-5 votos
2 respostas
640 visitas

Uma expressão regular pode se transformar em assembly? [fechada]

Sabe -se que expressões regulares são padrões de caracteres que associam sequências de caracteres no texto. Sendo assim, seria possível fazer o mesmo para Assembly? Fazer com que exista expressões que ...
KylanProgram's user avatar
4 votos
1 resposta
3mil 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 ...
Jefferson Quesado's user avatar
8 votos
2 respostas
267 visitas

Alguém poderia me ajudar com essa linguagem formal?

Alguém poderia me ajudar com a seguinte linguagem: {a^n b^m | n<= m <= 2n} Desculpe a ignorância, mas não estou conseguindo formar um autômato de pilha com essa linguagem. Estou tentando ...
Breno Lima's user avatar
3 votos
1 resposta
2mil visitas

Dúvida acerca da hierarquia de Chomsky

A respeito dos 4 tipos de linguagens, tenho dúvida em compreender sobre a linguagem dependente do contexto ou sensível ao contexto. Acho muito confusa a explicação que encontro pelos sites, gostaria ...
Diogo's user avatar
  • 31
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.459
5 votos
1 resposta
882 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 ...
dimitri.marinho's user avatar