Regras de derivação

---

Regras de derivação são pares do tipo $⟨\alpha ,\beta ⟩$, onde:

• $\alpha \in (V\cup T{)}^{+}$ → sequência não vazia de variáveis e/ou terminais.
• $\beta \in (V\cup T{)}^{\ast }$ → sequência que pode ser vazia ou não.

Representadas como: $\alpha \to \beta$.

Várias regras com o mesmo $\alpha$, por exemplo:

$$\alpha \to {\beta }_1,\alpha \to {\beta }_2,\dots$$

Podem ser abreviadas:

$$\alpha \to {\beta }_1\mid {\beta }_2\mid \cdots \mid {\beta }_n$$

Linguagem gerada: conjunto de todas as cadeias de símbolos terminais que podem ser derivadas da variável inicial $S$.

Formalmente:

$$L(G)=\{w\in T^{\ast }\mid S\stackrel{+}{\Rightarrow }w\}$$

Exemplo: $G=(V,T,P,S)$

• $V=S,D$
• $T=0,1,\dots ,9$
• $P=S\to D,S\to DS,D\to 0\mid 1\mid \cdots \mid 9$

Derivação da cadeia “243”:

$S\Rightarrow DS\Rightarrow 2S\Rightarrow 2DS\Rightarrow 24S\Rightarrow 24D\Rightarrow 243$

Referências

---

Aula de Gramática Regular