GLC – Gramática Livre do Contexto

Definição

• Gramática Livre do Contexto / GLC = gramática formal onde cada regra de produção tem a forma A → α em que
  • A é um não-terminal = símbolo que pode ser expandido
  • α / alpha é uma cadeia qualquer de terminais e não-terminais -inclusive a cadeia vazia ε - epsilon

Componentes

• GLC = é definida como uma quádrupla G = (V,Σ,R,S), onde
  • V = conjunto finito de variáveis - ou não-terminais
  • Σ - Sigma = conjunto finito de terminais
  • R = conjunto finito de regras de produção
  • S ∈ V = símbolo inicial

Exemplo

G = ({S}, {a,b}, R, S)
R:
S → aSb | ε

• essa gramática gera a linguagem L= { a^n b^n | n ≥ 0}
  • ou seja - o número de a’s é igual ao número de b's, com todos os a’s vindo antes

Usos

• GLCs descrevem linguagens livres do contexto, que são reconhecidas por autômatos com pilha - PDAs
• usadas em linguagens de programação para definir sintaxe