Arvore de derivacao

Anotacoes

**• Subtema: Árvore de derivação** Para uma determinada gramática livre do contexto, a representação da derivação de palavras na forma de árvore, denominada árvore de derivação, é como segue (considere a figura 6.2): a) A raiz é o símbolo inicial da gramática. b) Os vértices interiores obrigatoriamente são variáveis. Se A é um vértice interior e X₁, X₂, ..., Xₙ são os "filhos" de A, então: - A → X₁, X₂, ..., Xₙ é uma produção da gramática; - Os vértices X₁, X₂, ..., Xₙ são ordenados da esquerda para a direita. c) Um vértice folha, ou simplesmente folha, é um símbolo terminal ou o símbolo vazio. Neste caso, o vazio é o único filho de seu pai (A → ε). --- **• Subtema: Exemplo de gramática e linguagem gerada** **Exemplo 2:** Considere a gramática Gₐ = ({S}, {a, b}, R, S), sendo o conjunto das regras R o seguinte: S → aSb | SS | ε. Determine a linguagem gerada por Gₐ. Por exemplo, uma derivação da palavra "aabb" pode ser feita a partir de Gₐ. --- **• Subtema: Exercícios sobre árvores sintáticas e derivações** Retomando a Gramática Livre do Contexto (GLC) G4 do Exemplo 2.4, vamos renomear suas variáveis com apenas uma letra para simplificar: - E → E + T | T - T → T × F | ...