Linguagens livres de contexto
Qual é a forma geral de uma regra de produção em uma gramática livre de contexto?
Anotacoes
Linguagens livres de contexto *Definição* Uma gramática livre do contexto G é uma gramática: G = (V, T, P, S) com a restrição de que qualquer regra de produção de P é da forma: A → α onde A é uma variável de V, e α, uma palavra de (V ∪ T)*. Portanto, uma gramática livre do contexto é uma gramática na qual o lado esquerdo das produções contém exatamente uma variável. Ou seja, as regras de produção são sempre do tipo: um não terminal se transformando em uma palavra que pode conter terminais ou não terminais. --- • O motivo simples é que os não-terminais aparecem livres à esquerda da seta em linguagens livres de contexto. Portanto, uma regra A → α indica que A pode ser substituída por α em qualquer ponto, independentemente de onde ocorra A. • Em contrapartida, podemos informalmente definir um contexto como um par de cadeias (de terminais e não-terminais) β, γ, tais que uma regra se aplicaria apenas se β ocorresse antes e γ ocorresse depois do não-terminal. Isso poderia ser escrito como: β A γ → β α γ • Uma regra dessa forma, em que α ≠ ε, é denominada regra gramatical sensível a contexto. Gramáticas sensíveis a contexto são mais poderosas que gramáticas livres de contexto,...
Estude com jogos interativos
Envie suas anotacoes e gere flashcards, provas e mais com IA
Comecar gratis