Skip to main content

Respostas interessantes marcadas com a tag

30 votos
Aceito

O que é uma linguagem livre de contexto?

Existe uma hierarquia definida por Chomsky e refinada por outros pesquisadores acerca de estrutura de linguagens denotadas por sequências de símbolos, palavras, letras, etc. Essa estrutura contém os ...
Victor Stafusa's user avatar
  • 64,9mil
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 ...
Guilherme Lautert's user avatar
14 votos

O que é uma linguagem livre de contexto?

A resposta do @Victor Stafusa é excelente, venho aqui apenas aprofundar alguns pontos. Linguagem Uma linguagem é um subconjunto (podendo ser finito ou infinito) de palavras geradas pelo operador ...
Jefferson Quesado's user avatar
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 ...
Jefferson Quesado's user avatar
7 votos

Uma linguagem subconjunto de uma linguagem livre de contexto é decidível?

Imagine que temos uma linguagem U que seja indecidível. As palavras dela pertencem ao alfabeto Σ. Se U existir, então ela é uma sublinguagem de Σ*. Tomemos agora a seguinte gramática G que produza L(G)...
Jefferson Quesado's user avatar
6 votos

Dúvida acerca da hierarquia de Chomsky

A hierarquia A hierarquia de linguagens é essa: As que Chomsky considerou à sua época, foram as linguagens regulares, livres de contexto, sensíveis ao contexto e irrestritas. No entanto, eu vou ...
Victor Stafusa's user avatar
  • 64,9mil
5 votos
Aceito

Reduzir gramáticas na hierarquia de Chomsky

Na Hierarquia de Chomsky, temos as seguintes gramáticas, da mais simples à mais poderosa: Gramática regular Gramática livre de contexto Gramática sensível a contexto Gramática irrestrita ...
Jefferson Quesado's user avatar
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, ...
Jefferson Quesado's user avatar
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 ...
Jefferson Quesado's user avatar
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 ...
Jefferson Quesado's user avatar
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 ...
Jefferson Quesado's user avatar
2 votos

Preciso de uma ferramenta de construção de parsers

O que deseja é um gerador de parser e provavelmente o ANTLR é o mais usado de todos. Não que ele seja certamente o melhor para o que precisa. Coco/R é outro bem usado. Mais um é o SableCC. Alguns ...
Maniero's user avatar
  • 484mil
1 voto

Questões sobre Backus Naur Form

BNF nada mais é que uma notação glorificada para produções de gramáticas formais, muitas vezes usadas para gramáticas livres de contexto. Ela tem suas peculiaridades, que são: não-terminais são ...
Jefferson Quesado's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible