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 ...
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 ...
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 ...
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 ...
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)...
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 ...
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
...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Tags relacionadas
linguagens-formais × 12teoria-da-computação × 10
autômatos × 6
ciência-da-computação × 4
regex × 2
terminologia × 2
matemática × 2
algoritmo × 1
parser × 1