Gramáticas generativas

Una gramática es una cuádrupla

$$G=(\Sigma_N,\Sigma_T,P,\$)$$

donde

• $\Sigma_N$ es un alfabeto de símbolos no-terminales.
• $\Sigma_T$ es un alfabeto de símbolos terminales.
• Se exige $\Sigma_N\cap\Sigma_T=\empty$ y se suele usar $\Sigma=\Sigma_N\cup\Sigma_T$.
• $P$ es un sistema de producciones finitos, donde se distingue varios casos, ejemplos son:
  • $P\subset(\Sigma_N\cup\Sigma_T)^*\times(\Sigma_N\cup\Sigma_T)^*$
    caso muy general, (así no haría falta distinguir los dos alfabetos a la primera vista, es decir, $P\subset\Sigma^*\times\Sigma^*$)
  • $P\subset\Sigma^*.\Sigma_N^+.\Sigma^*\times\Sigma^*$
    es decir, a la derecha existe por lo menos un símbolo no-terminal
  • $P\subset \Sigma_N\times\Sigma^*$
    es decir, se sustitue solamente símbolos (palabras) no-terminales
  • $P\subset \Sigma_N\times(\Sigma_N^*\cup\Sigma_T^*)$
    es decir, se sustitue solamente símbolos (palabras) no-terminales, pero por símbolos (palabras) o bien terminales o bien no-terminales
  • Repetimos: se exige que $\vert P\vert<\infty$, es decir, el conjunto de reglas es finito.
  ¡Más adelante vemos en detalle qué tipos de sistemas de producciones se suele usar!
• $\$ es el símbolo inicial (o de partida, o de comienzo, o axioma) que pertenece al alfabeto no-terminal, es decir, $\$\in\Sigma_N$.

El lenguaje generado por una gramática es

$$L(G) = \{ w \;\vert\;w \in \Sigma_T^*\mbox{ y } \$\longrightarrow ^* w \}$$

es decir, se puede derivar la palabra $w\in\Sigma_T$ desde el símbolo inicial aplicando las reglas del sistema de producciones. Dichas palabras derivables que consisten solamente de símbolos terminales se llaman sentencias.