Siguiente: Ejemplos de gramáticas Un nivel arriba: Gramáticas formales Anterior: Gramáticas formales

Conceptos básicos de gramáticas

Una gramática es una estructura G=(V,T, P, s₀) donde

$$\begin{eqnarray*}V &:& \mbox{\rm\begin{minipage}[t]{38em} es un conjunto de s\'... ...em producciones} o {\em reglas sint\'acticas}. \end{minipage}} \end{eqnarray*}$$

Una pareja $(\alpha,\beta)\in P$ se escribe como $\alpha\rightarrow\beta$, o bien $\alpha::=\beta$. Se dice que $\alpha$ es el antecedente de la regla y que $\beta$ es su consecuente. Si $(\alpha,\beta_1),(\alpha,\beta_2),\ldots,(\alpha,\beta_k)\in P$ es un conjunto de reglas con un antecedente común, se simplifica la notación y se escribe $\alpha\rightarrow\beta_1\vert\beta_2\vert\cdots\vert\beta_k,$ o alternativamente $\alpha::=\beta_1\vert\beta_2\vert\cdots\vert\beta_k.$ Dadas dos palabras $\sigma, \tau\in \Sigma ^*$ decimos que $\tau$ se sigue de $\sigma$ en G, y escribimos $G\vdash(\sigma\rightarrow \tau)$, o simplemente $\sigma\rightarrow \tau$, cuando $\tau$ resulte de $\sigma$ al intercambiar una partícula de $\sigma$, que sea el antecedente de una regla, por el respectivo consecuente de la regla. En símbolos,

$$G\vdash\sigma\rightarrow \tau\;\Leftrightarrow\; \exists \sig... ... = \sigma_1\alpha\sigma_2 \ \& \tau = \sigma_1\beta\sigma_2.$$ (3)

Decimos que $\tau$ se deriva de $\sigma$ en G, y escribimos $G\vdash(\sigma\stackrel{*}{\rightarrow} \tau)$, o simplemente $\sigma\stackrel{*}{\rightarrow} \tau$, si existe una sucesión finita de palabras, cuyos primero y último elementos coinciden con $\sigma$ y $\tau$ respectivamente, y cualquier elemento en la sucesión se sigue del anterior. En símbolos,

$$G\vdash\sigma\stackrel{*}{\rightarrow} \tau\;\Leftrightarrow\... ... \& \forall i<n : G\vdash(\sigma_i\rightarrow \sigma_{i+1})$$ (4)

En tal caso, la sucesión de palabras y producciones $\sigma_{1}P_{1}\sigma_{2}\cdots \sigma_{n-1}P_{n-1}\sigma_{n}$, donde $\sigma_{i+1}$ se sigue de $\sigma_{i}$ precisamente por la aplicación de la producción P_i, es una derivación de $\tau$ a partir de $\sigma$. Así pues, la relación ``se_deriva'' es la cerradura reflexivo-transitiva de la relación ``se_sigue'' El lenguaje de la gramática es el conjunto de palabras formadas con símbolos terminales que se derivan del símbolo inicial,

$$L(G)=\{\sigma\in T^*\vert G\vdash(s_0\stackrel{*}{\rightarrow} \sigma)\}.$$

Siguiente: Ejemplos de gramáticas Un nivel arriba: Gramáticas formales Anterior: Gramáticas formales