Autómata finito no determinista - Nondeterministic finite automaton

NFA para (0 | 1) ^*  1 (0 | 1) ³ .
Un DFA para ese idioma tiene al menos 16 estados.

En la teoría de los autómatas , una máquina de estados finitos se denomina autómata finito determinista (DFA), si

• cada una de sus transiciones está determinada de forma única por su estado de origen y símbolo de entrada, y
• Se requiere leer un símbolo de entrada para cada transición de estado.

Un autómata finito no determinista ( NFA ), o una máquina de estados finitos no determinista , no necesita obedecer estas restricciones. En particular, cada DFA es también un NFA. A veces, el término NFA se usa en un sentido más estricto, refiriéndose a un NFA que no es un DFA, pero no en este artículo.

Usando el algoritmo de construcción de subconjuntos , cada NFA se puede traducir a un DFA equivalente; es decir, un DFA que reconoce el mismo lenguaje formal . Al igual que los DFA, los NFA solo reconocen los idiomas normales .

Los NFA fueron introducidos en 1959 por Michael O. Rabin y Dana Scott , quienes también mostraron su equivalencia con los DFA. Los NFA se utilizan en la implementación de expresiones regulares : la construcción de Thompson es un algoritmo para compilar una expresión regular en un NFA que puede realizar de manera eficiente la coincidencia de patrones en cadenas. Por el contrario, el algoritmo de Kleene se puede utilizar para convertir un NFA en una expresión regular (cuyo tamaño es generalmente exponencial en el autómata de entrada).

NFA se han generalizado en múltiples formas, por ejemplo, no determinista autómatas finitos con varepsilon mueve , transductores de estados finitos , autómatas de pila , autómatas alterna , ω-autómatas , y autómatas probabilístico . Además de los DFA, otros casos especiales conocidos de NFA son los autómatas finitos inequívocos (UFA) y los autómatas finitos autoverificables (SVFA).

Introducción informal

Hay varias explicaciones informales que son equivalentes.

• Un NFA, similar a un DFA , consume una cadena de símbolos de entrada. Para cada símbolo de entrada, pasa a un nuevo estado hasta que se hayan consumido todos los símbolos de entrada. En cada paso, el autómata elige arbitrariamente una de las transiciones aplicables. Si existe alguna "ejecución afortunada", es decir, alguna secuencia de opciones que conducen a un estado de aceptación después de consumir completamente la entrada, se acepta. De lo contrario, es decir, si ninguna secuencia de elección puede consumir toda la entrada y conducir a un estado de aceptación, la entrada se rechaza.
• Una vez más, una NFA consume una serie de símbolos de entrada, uno por uno. En cada paso, siempre que sean aplicables dos o más transiciones, se "clona" a sí mismo en un número apropiado de copias, cada una siguiendo una transición diferente. Si no se aplica ninguna transición, la copia actual está en un callejón sin salida y "muere". Si, después de consumir la entrada completa, alguna de las copias está en un estado de aceptación, la entrada se acepta, de lo contrario, se rechaza.

Definicion formal

Para una introducción más elemental de la definición formal, vea la teoría de autómatas .

Autómata

Un NFA se representa formalmente por un 5-tupla , , que consiste en ${\ Displaystyle (Q, \ Sigma, \ Delta, q_ {0}, F)}$

• un conjunto finito de estados .${\ displaystyle Q}$
• un conjunto finito de símbolos de entrada .${\ Displaystyle \ Sigma}$
• una función de transición  : .${\ Displaystyle \ Delta}$${\ Displaystyle Q \ times \ Sigma \ rightarrow {\ mathcal {P}} (Q)}$
• un estado inicial (o de inicio ) .${\ Displaystyle q_ {0} \ in Q}$
• un conjunto de estados distingue como aceptar (o finales ) estados .${\ Displaystyle F}$ ${\ Displaystyle F \ subseteq Q}$

Aquí, denota el conjunto de potencias . ${\ Displaystyle {\ mathcal {P}} (Q)}$${\ displaystyle Q}$

Lenguaje reconocido

Dado un NFA , su idioma reconocido se denota y se define como un conjunto de todas las cadenas sobre el alfabeto que son aceptadas por . ${\ Displaystyle M = (Q, \ Sigma, \ Delta, q_ {0}, F)}$${\ Displaystyle L (M)}$${\ Displaystyle \ Sigma}$${\ Displaystyle M}$

En vaga correspondencia con las explicaciones informales anteriores , existen varias definiciones formales equivalentes de una cadena aceptada por : ${\ Displaystyle w = a_ {1} a_ {2} ... a_ {n}}$${\ Displaystyle M}$

• ${\ Displaystyle w}$se acepta si existe una secuencia de estados`` en tal que: ${\ Displaystyle r_ {0}, r_ {1}, ..., r_ {n}}$${\ displaystyle Q}$
  1. ${\ Displaystyle r_ {0} = q_ {0}}$
  2. ${\ Displaystyle r_ {i + 1} \ in \ Delta (r_ {i}, a_ {i + 1})}$, por ${\ Displaystyle i = 0, \ ldots, n-1}$
  3. ${\ Displaystyle r_ {n} \ in F}$.

En palabras, la primera condición dice que la máquina arranca en el estado de inicio . La segunda condición dice que dado cada carácter de cadena , la máquina pasará de un estado a otro de acuerdo con la función de transición . La última condición dice que la máquina acepta si la última entrada de hace que la máquina se detenga en uno de los estados de aceptación. Para ser aceptado por , no se requiere que cada secuencia de estado termine en un estado de aceptación, es suficiente si uno lo hace. De lo contrario, es decir , si es imposible pasar de un estado a otro siguiendo , se dice que el autómata rechaza la cuerda. El conjunto de cadenas acepta es el idioma reconocido por y este idioma se denota por .${\ Displaystyle q_ {0}}$${\ Displaystyle w}$${\ Displaystyle \ Delta}$${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle M}$${\ Displaystyle q_ {0}}$${\ Displaystyle F}$${\ Displaystyle w}$${\ Displaystyle M}$ ${\ Displaystyle M}$${\ Displaystyle L (M)}$

• Alternativamente, se acepta si , donde se define de forma recursiva por: ${\ Displaystyle w}$${\ Displaystyle \ Delta ^ {*} (q_ {0}, w) \ cap F \ not = \ emptyset}$${\ Displaystyle \ Delta ^ {*}: Q \ times \ Sigma ^ {*} \ rightarrow {\ mathcal {P}} (Q)}$
  1. ${\ Displaystyle \ Delta ^ {*} (r, \ epsilon) = \ {r \}}$donde está la cadena vacía, y${\ Displaystyle \ epsilon}$
  2. ${\ Displaystyle \ Delta ^ {*} (r, xa) = \ bigcup _ {r '\ in \ Delta ^ {*} (r, x)} \ Delta (r', a)}$para todos .${\ Displaystyle x \ in \ Sigma ^ {*}, a \ in \ Sigma}$

En palabras, es el conjunto de todos los estados accesibles desde el estado consumiendo la cadena . La cadena se acepta si se puede alcanzar algún estado de aceptación desde el estado inicial consumiendo .${\ Displaystyle \ Delta ^ {*} (r, x)}$${\ Displaystyle r}$${\ Displaystyle x}$${\ Displaystyle w}$${\ Displaystyle F}$${\ Displaystyle q_ {0}}$${\ Displaystyle w}$

Estado inicial

La definición de autómata anterior utiliza un solo estado inicial , que no es necesario. A veces, los NFA se definen con un conjunto de estados iniciales. Existe una construcción sencilla que traduce un NFA con múltiples estados iniciales a un NFA con un solo estado inicial, lo que proporciona una notación conveniente.

Ejemplo

El diagrama de estado para M . No es determinista, ya que en el estado p la lectura de un 1 puede conducir ap o q .	Todas las carreras posibles de M en la cadena de entrada "10".
Todas las carreras posibles de M en la cadena de entrada "1011". Etiqueta de arco: símbolo de entrada, etiqueta de nodo : estado, verde : estado de inicio, rojo : estado (s) de aceptación.

El siguiente autómata , con un alfabeto binario, determina si la entrada termina con un 1. Sea dónde se puede definir la función de transición mediante esta tabla de transición de estado (ver imagen superior izquierda): ${\ Displaystyle M}$${\ Displaystyle M = (\ {p, q \}, \ {0,1 \}, \ Delta, p, \ {q \})}$${\ Displaystyle \ Delta}$

Aporte Estado	0	1
${\ Displaystyle p}$	${\ Displaystyle \ {p \}}$	${\ Displaystyle \ {p, q \}}$
${\ Displaystyle q}$	${\ Displaystyle \ emptyset}$	${\ Displaystyle \ emptyset}$

Dado que el conjunto contiene más de un estado, no es determinista. El idioma de puede describirse mediante el idioma regular dado por la expresión regular . ${\ Displaystyle \ Delta (p, 1)}$${\ Displaystyle M}$${\ Displaystyle M}$ (0|1)*1

Todas las secuencias de estado posibles para la cadena de entrada "1011" se muestran en la imagen inferior. La cadena es aceptada por ya que una secuencia de estado satisface la definición anterior; no importa que otras secuencias no lo hagan. La imagen se puede interpretar de dos formas: ${\ Displaystyle M}$

• En términos de la explicación anterior de "carrera afortunada", cada camino en la imagen denota una secuencia de opciones de .${\ Displaystyle M}$
• En términos de la explicación de "clonación", cada columna vertical muestra todos los clones de en un momento dado, múltiples flechas que emanan de un nodo indican clonación, un nodo sin flechas que emanan indica la "muerte" de un clon.${\ Displaystyle M}$

La posibilidad de leer la misma imagen de dos formas también indica la equivalencia de ambas explicaciones anteriores.

• Considerando la primera de las definiciones formales anteriores , se acepta "1011" ya que al leerlo puede atravesar la secuencia de estados , lo que satisface las condiciones 1 a 3.${\ Displaystyle M}$${\ Displaystyle \ langle r_ {0}, r_ {1}, r_ {2}, r_ {3}, r_ {4} \ rangle = \ langle p, p, p, p, q \ rangle}$
• Con respecto a la segunda definición formal, el cálculo de abajo hacia arriba muestra que , por lo tanto , por lo tanto , por lo tanto , y por lo tanto ; dado que ese conjunto no está separado de , se acepta la cadena "1011".${\ Displaystyle \ Delta ^ {*} (p, \ epsilon) = \ {p \}}$${\ Displaystyle \ Delta ^ {*} (p, 1) = \ Delta (p, 1) = \ {p, q \}}$${\ Displaystyle \ Delta ^ {*} (p, 10) = \ Delta (p, 0) \ cup \ Delta (q, 0) = \ {p \} \ cup \ {\}}$${\ Displaystyle \ Delta ^ {*} (p, 101) = \ Delta (p, 1) = \ {p, q \}}$${\ Displaystyle \ Delta ^ {*} (p, 1011) = \ Delta (p, 1) \ cup \ Delta (q, 1) = \ {p, q \} \ cup \ {\}}$${\ Displaystyle \ {q \}}$

Por el contrario, la cadena "10" es rechazada por (todas las secuencias de estado posibles para esa entrada se muestran en la imagen superior derecha), ya que no hay forma de alcanzar el único estado de aceptación , leyendo el símbolo 0 final. Si bien se puede alcanzar después de consumir el "1" inicial, esto no significa que se acepte la entrada "10"; más bien, significa que se aceptaría una cadena de entrada "1". ${\ Displaystyle M}$${\ Displaystyle q}$${\ Displaystyle q}$

Equivalencia a DFA

Un autómata finito determinista (DFA) puede verse como un tipo especial de NFA, en el que para cada estado y símbolo, la función de transición tiene exactamente un estado. Por lo tanto, está claro que todos los lenguajes formales que pueden ser reconocidos por un DFA pueden serlo por una NFA.

Por el contrario, para cada NFA, hay un DFA tal que reconoce el mismo lenguaje formal. El DFA se puede construir usando la construcción de powerset .

Este resultado muestra que los NFA, a pesar de su flexibilidad adicional, no pueden reconocer idiomas que no pueden ser reconocidos por algunos DFA. También es importante en la práctica para convertir NFA más fáciles de construir en DFA ejecutables de manera más eficiente. Sin embargo, si la NFA tiene n estados, la DFA resultante puede tener hasta estados, lo que a veces hace que la construcción no sea práctica para las NFA grandes. ${\ Displaystyle 2 ^ {n}}$

NFA con movimientos ε

El autómata finito no determinista con movimientos ε (NFA-ε) es una generalización adicional a NFA. Este autómata sustituye la función de transición por la que permite la cadena vacía ε como posible entrada. Las transiciones sin consumir un símbolo de entrada se denominan transiciones ε. En los diagramas de estado, generalmente se etiquetan con la letra griega ε. Las transiciones ε proporcionan una forma conveniente de modelar los sistemas cuyos estados actuales no se conocen con precisión: es decir, si estamos modelando un sistema y no está claro si el estado actual (después de procesar alguna cadena de entrada) debe ser q o q ', entonces podemos agregar una transición ε entre estos dos estados, poniendo así el autómata en ambos estados simultáneamente.

Definicion formal

Un NFA-ε se representa formalmente por un 5-tupla , , que consiste en ${\ Displaystyle (Q, \ Sigma, \ Delta, q_ {0}, F)}$

• un conjunto finito de estados ${\ displaystyle Q}$
• un conjunto finito de símbolos de entrada llamado alfabeto ${\ Displaystyle \ Sigma}$
• una función de transición ${\ Displaystyle \ Delta: Q \ times (\ Sigma \ cup \ {\ epsilon \}) \ rightarrow {\ mathcal {P}} (Q)}$
• un estado inicial (o de inicio )${\ Displaystyle q_ {0} \ in Q}$
• un conjunto de estados distingue como aceptar (o finales ) estados .${\ Displaystyle F}$ ${\ Displaystyle F \ subseteq Q}$

Aquí, denota el conjunto de potencias de y ε denota una cadena vacía. ${\ Displaystyle {\ mathcal {P}} (Q)}$${\ displaystyle Q}$

ε-cierre de un estado o conjunto de estados

Para un estado , denotemos el conjunto de estados a los que se puede acceder siguiendo las transiciones ε en la función de transición , es decir, si hay una secuencia de estados tal que ${\ Displaystyle q \ in Q}$${\ Displaystyle E (q)}$${\ Displaystyle q}$${\ Displaystyle \ Delta}$${\ Displaystyle p \ en E (q)}$${\ Displaystyle q_ {1}, ..., q_ {k}}$

• ${\ Displaystyle q_ {1} = q}$,
• ${\ Displaystyle q_ {i + 1} \ in \ Delta (q_ {i}, \ varepsilon)}$para cada uno , y${\ Displaystyle 1 \ leq i <k}$
• ${\ Displaystyle q_ {k} = p}$.

${\ Displaystyle E (q)}$se conoce como el ε-cierre de . ${\ Displaystyle q}$

ε-cierre también se define para un conjunto de estados. El ε-cierre de un conjunto de estados`` de un NFA se define como el conjunto de estados alcanzables desde cualquier estado en las siguientes ε-transiciones. Formalmente, para , definir . ${\ Displaystyle P}$${\ Displaystyle P}$${\ Displaystyle P \ subseteq Q}$${\ Displaystyle E (P) = \ bigcup \ límites _ {q \ in P} E (q)}$

Aceptando estados

Sea una cadena sobre el alfabeto . El autómata acepta la cadena si existe una secuencia de estados, con las siguientes condiciones: ${\ Displaystyle w = a_ {1} a_ {2} ... a_ {n}}$${\ Displaystyle \ Sigma}$${\ Displaystyle M}$ ${\ Displaystyle w}$${\ Displaystyle r_ {0}, r_ {1}, ..., r_ {n}}$${\ displaystyle Q}$

1. ${\ Displaystyle r_ {0} \ en E (q_ {0})}$
2. ${\ Displaystyle r_ {i + 1} \ in E (r ')}$donde para cada uno , y${\ Displaystyle r '\ in \ Delta (r_ {i}, a_ {i + 1})}$${\ Displaystyle i = 0, ..., n-1}$
3. ${\ Displaystyle r_ {n} \ in F}$.

En palabras, la primera condición dice que la máquina comienza en el estado que se puede alcanzar desde el estado de inicio a través de transiciones ε. La segunda condición dice que después de la lectura , la máquina realiza una transición de de a , y luego toma cualquier número de varepsilon transiciones de acuerdo con pasar de a . La última condición dice que la máquina acepta si la última entrada de hace que la máquina se detenga en uno de los estados de aceptación. De lo contrario, se dice que el autómata rechaza la cuerda. El conjunto de cadenas acepta es el idioma reconocido por y este idioma se denota por . ${\ Displaystyle q_ {0}}$${\ Displaystyle a_ {i}}$${\ Displaystyle \ Delta}$${\ Displaystyle r_ {i}}$${\ Displaystyle r '}$${\ Displaystyle \ Delta}$${\ Displaystyle r '}$${\ Displaystyle r_ {i + 1}}$${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle M}$ ${\ Displaystyle M}$${\ Displaystyle L (M)}$

Ejemplo

El diagrama de estado de M

Sea un NFA-ε, con un alfabeto binario, que determina si la entrada contiene un número par de 0 o un número par de 1. Tenga en cuenta que 0 apariciones también es un número par de apariciones. ${\ Displaystyle M}$

En notación formal, supongamos que la relación de transición puede definirse mediante esta tabla de transición de estado : ${\ Displaystyle M = (\ {S_ {0}, S_ {1}, S_ {2}, S_ {3}, S_ {4} \}, \ {0,1 \}, \ Delta, S_ {0} , \ {S_ {1}, S_ {3} \})}$${\ Displaystyle \ Delta}$

${\ Displaystyle M}$puede verse como la unión de dos DFA : uno con estados y el otro con estados . El idioma de puede describirse mediante el idioma regular dado por esta expresión regular . Definimos usando movimientos ε pero se puede definir sin usar movimientos ε. ${\ Displaystyle \ {S_ {1}, S_ {2} \}}$${\ Displaystyle \ {S_ {3}, S_ {4} \}}$${\ Displaystyle M}$ ${\ displaystyle (1 ^ {*} (01 ^ {*} 01 ^ {*}) ^ {*}) \ cup (0 ^ {*} (10 ^ {*} 10 ^ {*}) ^ {*} )}$${\ Displaystyle M}$${\ Displaystyle M}$

Equivalencia a NFA

Para demostrar que NFA-ε es equivalente a NFA, primero tenga en cuenta que NFA es un caso especial de NFA-ε, por lo que queda por mostrar que para cada NFA-ε, existe un NFA equivalente.

Sea un NFA-ε. El NFA es equivalente a , donde para cada y , . ${\ Displaystyle A = (Q, \ Sigma, \ Delta, q_ {0}, F)}$${\ Displaystyle A '= (Q, \ Sigma, \ Delta', E (q_ {0}), F)}$${\ Displaystyle A}$${\ Displaystyle a \ in \ Sigma}$${\ Displaystyle q \ in Q}$${\ Displaystyle \ Delta '(q, a) = E (\ Delta (q, a))}$

Por tanto, NFA-ε es equivalente a NFA. Dado que NFA es equivalente a DFA, NFA-ε también es equivalente a DFA.

Propiedades de cierre

NFA compuesto aceptando la unión de los idiomas de algunos NFA dados N ( s ) y N ( t ) . Para una cadena de entrada w en la unión del lenguaje, el autómata compuesto sigue una transición ε desde q al estado inicial (círculo de color izquierdo) de un subautomatón apropiado - N ( s ) o N ( t ) - que, siguiendo w , puede alcanzar un estado de aceptación (círculo de color derecho); a partir de ahí, se puede alcanzar el estado f mediante otra transición ε. Debido a las transiciones ε, el NFA compuesto es propiamente no determinista incluso si tanto N ( s ) como N ( t ) fueran DFA; viceversa, construir un DFA para el lenguaje de unión (incluso de dos DFA) es mucho más complicado.

Se dice que las NFA se cierran bajo un operador ( binario / unario ) si las NFA reconocen los idiomas que se obtienen al aplicar la operación en los idiomas reconocibles de la NFA. Las NFA se cierran en virtud de las siguientes operaciones.

• Unión (ver foto)
• Intersección
• Concatenación
• Negación
• Cierre Kleene

Dado que los NFA son equivalentes a un autómata finito no determinista con movimientos ε (NFA-ε), los cierres anteriores se prueban utilizando las propiedades de cierre de NFA-ε. Las propiedades de cierre anteriores implican que las NFA pueden reconocer idiomas regulares .

Los NFA se pueden construir a partir de cualquier expresión regular utilizando el algoritmo de construcción de Thompson .

Propiedades

La máquina se inicia en el estado inicial especificado y lee una cadena de símbolos de su alfabeto . El autómata usa la función de transición de estado Δ para determinar el siguiente estado usando el estado actual, y el símbolo que acaba de leer o la cadena vacía. Sin embargo, "el siguiente estado de un NFA depende no sólo del evento de entrada actual, sino también de un número arbitrario de eventos de entrada posteriores. Hasta que ocurran estos eventos posteriores, no es posible determinar en qué estado se encuentra la máquina". Si, cuando el autómata ha terminado de leer, está en un estado de aceptación, se dice que la NFA acepta la cadena, de lo contrario se dice que la rechaza.

El conjunto de todas las cadenas aceptadas por una NFA es el idioma que acepta la NFA. Este idioma es un idioma regular .

Para cada NFA se puede encontrar un autómata finito determinista (DFA) que acepta el mismo lenguaje. Por lo tanto, es posible convertir un NFA existente en un DFA con el fin de implementar una máquina (quizás) más simple. Esto se puede realizar utilizando la construcción del conjunto de potencias , lo que puede conducir a un aumento exponencial en el número de estados necesarios. Para obtener una prueba formal de la construcción del conjunto de alimentación, consulte el artículo de construcción del conjunto de alimentación .

Implementación

Hay muchas formas de implementar una NFA:

• Convierta al DFA equivalente. En algunos casos, esto puede causar una explosión exponencial en el número de estados.
• Mantenga una estructura de datos establecida de todos los estados en los que podría estar actualmente el NFA. En el consumo de un símbolo de entrada, una los resultados de la función de transición aplicada a todos los estados actuales para obtener el conjunto de los estados siguientes; si se permiten movimientos ε, incluya todos los estados alcanzables por dicho movimiento (ε-cierre). Cada paso requiere como máximo s ² cálculos, donde s es el número de estados del NFA. Sobre el consumo del último símbolo de entrada, si uno de los estados actuales es un estado final, la máquina acepta la cadena. Una cadena de longitud n se puede procesar en el tiempo O (ns ² ) y el espacio O ( s ).
• Crea varias copias. Para cada decisión de n vías, la NFA crea hasta copias de la máquina. Cada uno entrará en un estado separado. Si, al consumir el último símbolo de entrada, al menos una copia de la NFA está en el estado de aceptación, la NFA aceptará. (Esto también requiere almacenamiento lineal con respecto al número de estados NFA, ya que puede haber una máquina para cada estado NFA).${\ Displaystyle n-1}$
• Propague los tokens explícitamente a través de la estructura de transición de la NFA y haga coincidir cada vez que un token alcance el estado final. Esto a veces es útil cuando la NFA debe codificar un contexto adicional sobre los eventos que desencadenaron la transición. (Para una implementación que utiliza esta técnica para realizar un seguimiento de las referencias de objetos, eche un vistazo a Tracematches).

Aplicación de NFA

Los NFA y DFA son equivalentes en el sentido de que si un idioma es reconocido por un NFA, también lo es por un DFA y viceversa. El establecimiento de tal equivalencia es importante y útil. Es útil porque construir un NFA para reconocer un idioma dado es a veces mucho más fácil que construir un DFA para ese idioma. Es importante porque los NFA pueden usarse para reducir la complejidad del trabajo matemático requerido para establecer muchas propiedades importantes en la teoría de la computación . Por ejemplo, es mucho más fácil probar las propiedades de cierre de los lenguajes normales utilizando NFA que DFA.

Ver también

• Autómata finito determinista
• Autómata finito no determinista bidireccional
• Autómata de empuje
• Máquina de Turing no determinista

Notas

Referencias

• MO Rabin y D. Scott, "Autómatas finitos y sus problemas de decisión", IBM Journal of Research and Development , 3 : 2 (1959) pp. 115-125.
• Michael Sipser, Introducción a la teoría de la computación . PWS, Boston. 1997. ISBN  0-534-94728-X . (ver sección 1.2: No determinismo, págs. 47–63.)
• John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN  0-201-02988-X . (Ver capítulo 2.)