Gramáticas
Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del
lenguaje.
Una gramática formal es una cuadrupla G = (N, T, P, S) donde
- N es un conjunto finito de símbolos no terminales
- T es un conjunto finito de símbolos terminales N T =
- P es un conjunto finito de producciones
Cada producción de P tiene la forma
(N T)* y A es S ó A N
- S es el símbolo distinguido o axioma S (N
T)
Restringiendo los formatos de producciones permitidas en una gramática, se pueden especificar
cuatro tipos de gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.

Gramáticas Regulares.

Además de los dispositivos que reconocen lenguajes regulares, que son los autómatas finitos, y de los dispositivos traductores de un lenguaje a otro (como por ejemplo las máquinas de Moore y de Mealy) también resulta importante el poder disponer de algún dispositivo que permita generar todas las cadenas de un lenguaje regular. Este dispositivo es la gramática regular.

En el primer tema se definió una gramática regular como aquella en la que las producciones eran todas de un mismo formato, o bien lineales a la derecha, o bien, lineales a la izquierda,

Lineales a la derecha,

$\begin{displaymath} \begin{array}{l} A \rightarrow aB \\ A \rightarrow a \end{array} \end{displaymath}$
Lineales a la izquierda,

$\begin{displaymath} \begin{array}{l} A \rightarrow Ba \\ A \rightarrow a \end{array} \end{displaymath}$

donde $A, B \in E_{A}, \ a \in E_{T}^{*}$ .

No obstante esta definición permite que coexistan en una misma gramática producciones de muy diverso tipo, como por ejemplo, $A \rightarrow a_{1}a_{2}a_{3}$ ; $A \rightarrow a_{1}a_{2}A$ , $A \rightarrow B$ ; $A \rightarrow \lambda$ ; $A \rightarrow a_{1}$ ; ...

Para evitar esta dispersión de variedades seria interesante fijar de una forma más compacta el formato de los consecuentes de las producciones en una gramática regular, es decir, sería interesante introducir un formato normalizado, una forma normal.

$% latex2html id marker 2456 \fbox {\parbox{115mm}{\begin{teore}Cada lenguaje reg... ...isplaymath}\par \end{itemize}donde $A, B \in E_{A}, \ a \in E_{T}$.\end{teore}}}$

Demostración:

Consiste en determinar los pasos en los que se puede convertir una producción genérica en una del formato normal.

Las producciones que tengan el formato $A \rightarrow \lambda$ y $A \rightarrow aB$ , con $\mid a \mid =1$ , ya están en la forma normal. Por lo tanto, sólo es necesario modificar las producciones del siguiente tipo:

$A \rightarrow aB, \ \mid a \mid \geq 2$ ,
$A \rightarrow a, \ \mid a \mid \geq 1$ ,
$A \rightarrow B$ .

Caso (1)

Sea $A \rightarrow a_{1}a_{2}\ldots a_{n}B$ una producción genérica tal que $a_{i} \in E_{T}$ y $n \geq 2$ . El proceso para conseguir un nuevo conjunto de producciones equivalente al inicial y que respete la forma normal, consiste en eliminar esta producción e introducir las siguientes:

$\begin{displaymath} \left.\begin{array}{l} A \rightarrow a_{1}Z_{1} \\ Z_{1}... ..., Z_{n-1} \ son \ nuevos \ s\acute{{\i}}mbolos \ auxiliares. \end{displaymath}$

Caso (2)

Sea $A \rightarrow a_{1}a_{2}\ldots a_{m}$ tal que $a_{i} \in E_{T}$ y $m \geq 1$ . Se elimina del nuevo conjunto de producciones y en su lugar se insertan las siguientes:

$\begin{displaymath} \left.\begin{array}{l} A \rightarrow a_{1}Y_{1} \\ Y_{1}... ...ts, Y_{m} \ son \ nuevos \ s\acute{{\i}}mbolos \ auxiliares. \end{displaymath}$

Caso (3)

Se realiza el siguiente cálculo, $\forall X \in E_{A}$ se determina

, el conjunto de símbolos auxiliares que derivan al símbolo

$\begin{displaymath} C(X) = \{Y \in E_{A} \mid Y \stackrel{*}{\Rightarrow} X\} \end{displaymath}$

Para construir el conjunto

a partir del conjunto

se realiza el siguiente proceso:

(i): $(X \rightarrow aY) \in P' \Leftrightarrow \exists \ Z \in E_{A} \mid (X \in C(Z) \wedge (Z \rightarrow aY) \in P$ ,
(ii): $(X \rightarrow \lambda) \in P' \Leftrightarrow \exists \ Z \in E_{A} \mid (X \in C(Z) \wedge (Z \rightarrow \lambda) \in P$ .

Por ejemplo, si $(Y \rightarrow X) \in P \wedge (X \rightarrow aZ \mid bS) \in P$ entonces en el nuevo conjunto de producciones se insertan las siguientes producciones: $Y \rightarrow aZ \mid bS$ .

Con este método se consigue transformar todas las producciones de una gramática regular lineal a la derecha en un nuevo conjunto de producciones que respeta la forma normal.

c.q.d.

Ejemplo:

Sea G la gramática definida por el siguiente conjunto de producciones:

$\begin{displaymath} \begin{array}{l} S \rightarrow a_{1}a_{2}a_{3} \mid a_{1}a... ... a_{2}S \\ B \rightarrow a_{1}a_{2}B \mid a_{1}S \end{array}\end{displaymath}$

Escribir una gramática equivalente a G pero cuyas producciones estén en la forma normal.

Primero se añaden nuevos símbolos auxiliares ( $X_{1}$ , $X_{2}$ , $X_{3}$ , $X_{4}$ , $X_{5}$ , $X_{6}$ ) que eliminen las producciones con cadenas de terminales (casos (1) y (2) del teorema anterior):

$\begin{displaymath} \begin{array}[t]{l} S \rightarrow a_{1}X_{1} \mid a_{1}X_{... ...{1}X_{6} \mid a_{1}S \\ X_{6} \rightarrow a_{2}B \end{array}\end{displaymath}$

Para finalizar, falta eliminar la producción $S \rightarrow B$ (caso (3) del teorema). El conjunto de producciones queda de la forma siguiente,

$\begin{displaymath} \begin{array}[t]{l} S \rightarrow a_{1}X_{1} \mid a_{1}X_{... ...{1}X_{6} \mid a_{1}S \\ X_{6} \rightarrow a_{2}B \end{array}\end{displaymath}$

$% latex2html id marker 2500 \fbox {\parbox{115mm}{\begin{corolario}Cada lenguaje... ...displaymath}\end{itemize}donde $A, B \in E_{A}, \ a \in E_{T}$.\end{corolario}}}$

$% latex2html id marker 2504 \fbox {\parbox{115mm}{\begin{teore} Para toda gram\'... ...egular G existe un AF$\lambda$, A, cumpli\'endose que L(G) = L(A).\end{teore}}}$

Demostración:

Sea

$\begin{displaymath} G = \langle E_{A}, E_{T}, P, S \rangle \end{displaymath}$

una gramática regular en la que sus producciones están en la forma $A \rightarrow aB$ ; $A \rightarrow aB$ ; $A \rightarrow a$ ; $A \rightarrow \lambda$ .

Sea un AF $\lambda$

$\begin{displaymath} A = \langle E, Q, f, q_{0}, F \rangle \end{displaymath}$

con

$\begin{displaymath} E = E_{T}, Q = E_{A} \cup \{X\} \mid X \not \in E_{A}, q_{0} = S, F = \{X\} \end{displaymath}$

y donde la función de transición se define mediante los siguientes pasos,

Si $(A \rightarrow a) \in P$ , entonces $X \in f(A,a)$ ,
Si $(A \rightarrow \lambda ) \in P$ , entonces $X \in f(A,\lambda )$ ,
Si $(A \rightarrow aB) \in P$ , entonces $B \in f(A,a)$ ,
Si $(A \rightarrow B) \in P$ , entonces $B \in f(A,\lambda )$ ,
$\forall \ a \in (E_{T} \cup \{\lambda \}), f(X,a) = \emptyset$ .

Se deja como ejercicio completar la demostración del teorema, comprobando que

c.q.d.

$% latex2html id marker 2524 \fbox {\parbox{115mm}{\begin{propo}Para toda gram\'a... ...\'atica regular lineal a la izquierda, G', tal que $L(G) = L(G')$.\end{propo}}}$

Demostración:

Sea

$\begin{displaymath} G = \langle E_{A}, E_{T}, P, S \rangle \end{displaymath}$

una gramática regular a la derecha y sea un autómata finito asociado a la misma (teorema 8)

$\begin{displaymath} A = \langle E, Q, f, q_{0}, F \rangle . \end{displaymath}$

Sea

$\begin{displaymath} A' = \langle E, Q', f', q_{0}', F' \rangle \end{displaymath}$

el AF $\lambda$ que reconoce $L(A)^{-1}$ (teorema 5). Sea

$\begin{displaymath} G' = \langle E_{A}', E_{T}', P', S' \rangle \end{displaymath}$

la gramática regular a la izquierda construida a partir del AF $\lambda$

de la forma siguiente

$\begin{displaymath} E_{T}' = E, E_{A}' = Q', S' = q_{0} \end{displaymath}$

y el conjunto de producciones de

se define por medio de las reglas,

(i): Si $q \in f'(p,a)$ , entonces $(p \rightarrow qa) \in P', a \in (E \cup \{\lambda \}$ ,
(i): Si $q \in F'$ , entonces $(p \rightarrow \lambda) \in P'$ .

Adicionalmente, para reducir el número de producciones de la nueva gramática se puede aplicar la siguiente última regla

(iii): $\forall \ a \in (E \cup \{\lambda \}),si \ f'(q,a) \subseteq \{q\} \wedge q \not \in F'$ , entonces puede eliminarse de $E_{A}'$ , así como todas las producciones de en las que aparezca el símbolo .

Se deja como ejercicio completar la demostración del teorema, comprobando que

Este obra está bajo una licencia de Creative Commons Attribution 3.0 Ecuador.

El blog de Diego

miércoles, 27 de octubre de 2010

Gramáticas regulares

Gramáticas Regulares.