Lenguajes formales

La idea básica es considerar a un lenguaje como un conjunto compuesto por cadenas de longitud finita formadas por símbolos tomados de un alfabeto. Es decir, dado un alfabeto $\Sigma = \{ \sigma_1 , \sigma_2 , . . . \sigma_n \}$, decimos que $x = \sigma_{i_1} \sigma_{i_2} . . . \sigma_{i_m}$, (para un $m$ dado, que llamamos longitud de $x$) es una cadena construida con símbolos de $\Sigma$. Si $m=0$ tenemos la cadena llamada vacia, y denotada por $\Lambda$. Al conjunto formado por de todas las cadenas que se pueden construir con las letras de dicho alfabeto se le llama lenguaje universal y se le denota por $\Sigma$* . Es evidente que el número de elementos de $\Sigma$* es infinito numerable. Entre las cadenas, como elementos de $\Sigma$* , se define una operación, llamada concatenación, mediante la cual a dos cadenas dadas $x, y \in \Sigma$* se le asocia otra cadena $z$ obtenida por yuxtaposición de $x, y$; es decir, si $x =x_1 x_2 . . . x_p \textrm{ con } x_i \in \Sigma$*, e $y = y_1 y_2 . . .y_q \textrm{ con } y_j \in \Sigma$*, entonces la cadena $z = xy$ , sería : $z = x_1 x_2 . . . x_p y_1 y_2 \ldots y_q$ .

Llamamos lenguaje construido con el alfabeto $\Sigma$, a cualquier subconjunto L de $\Sigma$*. Diremos que un lenguaje es finito, si es finito el número de cadenas de que consta; en otro caso diremos que es infinito. El lenguaje vacio no tiene ninguna cadena (que no debe confundirse con el lenguaje que solo tiene la cadena vacia).

Una vez dada esta definición tan general de lenguaje, el problema inicial que se nos presenta es como distinguir con precisión las cadenas que pertenecen a un lenguaje L de aquellas que no pertenecen. Hay dos formas de hacerlo: una consiste en dar las reglas mediante las cuales construir las cadenas que forman el lenguaje, y otra es dar un procedimiento para determinar si una cadena dada pertenece o no al lenguaje considerado. En el primer caso se trata de definir las gramáticas formales, o generadores, y en el otro los autómatas o reconocedores.

Para fijar un poco las ideas de lo que se entiende por lenguaje definido por una gramática formal, demos ligeramente algunos detalles técnicos. Una gramática es un procedimiento finito para formar o generar cualquiera de todas las posibles cadenas de un lenguaje. Formalmente diremos que una gramática es un sistema :

$$G = ( V_N , V_T , P , S )$$

Donde $V_N$ es un alfabeto llamado vocabulario no terminal; $V_T$ es un alfabeto, llamado vocabulario terminal. Las reglas de $P$ son de la forma $\alpha_i \rightarrow \alpha_j$, donde

$$\alpha_i \in (V_N \cup V_T)^+ , \qquad \alpha_j \in (V_N \cup V_T)^*$$

y $S$, un símbolo de $V_N$, llamado símbolo inicial. Para generar una palabra mediante la gramática $G$, nos apoyamos en secuencias de cadenas de símbolos, $v_1 , v_2 , . . . v_m$ . Estas secuencias (cada una de las cuales es llamada derivación), se construyen del siguiente modo:

1:

El primer elemento de la derivación es siempre el símbolo inicial S (es decir, siempre $v_1 = S$).

2:

A partir de un elemento $v_i$ se pasa al siguiente $v_{i+1}$, (donde $v_i$ y $v_{i+1}$ pertenecen a ) , mediante una regla de $P$, es decir, si $v_i = \delta \alpha_i \delta'$, y la regla $\alpha_i \rightarrow \alpha_j \in P$, entonces será $v_{i+1} = \delta \alpha_j \delta'$, (escribiremos $v_i \Rightarrow v_{i+1}$)

3:

Si $v_m$, obtenida aplicando $m$ veces el procedimiento anterior, pertenece a $V_T^*$, entonces decimos que $v_m$ es una palabra generada por $G$.

A la derivación $S = v_1 , v_2 , . . . v_m$, se la puede expresar:

$$S \Rightarrow v_1 \Rightarrow v_2 \Rightarrow . . . . \Rightarrow v_m ,$$

o simplemente

$$S =*\Rightarrow v_m$$

que podría leerse: $v_m$ se obtiene por derivación de $S$ aplicando reglas de $G$, o simplemente: $v_m$ en una derivada de $S$.

Podemos sintetizar lo anterior diciendo que el lenguaje generado por la gramática $G$, es:

$$L(G) = \{ x \vert x \in V_T^* , S =*\Rightarrow x \}$$

Decimos que dos gramáticas son equivalentes, si y solo si generan el mismo lenguaje, es decir

$$G_1 \equiv G_2 \Leftrightarrow L(G_1) = L(G_2)$$