Perguntas com links
10 questions linked to/from Reduzir gramáticas na hierarquia de Chomsky
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? ...
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 ...
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 ...
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 ...
-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 ...
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 ...
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 ...
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 ...
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’...
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 ...