Cleiver Manzanilla                                   

Desde su nacimiento, la teoría de autómatas ha encontrado aplicación en muy diversos campos. Esto se debe a que resulta muy natural considerar, tanto los autómatas como las máquinas secuenciales, sistemas capaces de transmitir (procesar) información.

En definitiva, esto es equiparable a cualquier sistema existente en la naturaleza, que recibe señales de su entorno, reacciona ante ellas y emite así nuevas señales al ambiente que le rodea.

• Algunos de los campos donde ha encontrado aplicación la teoría de autómatas son:

– Teoría de la Comunicación

– Teoría de Control

– Lógica de los circuitos secuenciales

– Ordenadores

– Teoría lógica de los sistemas evolutivos y auto-reproductivos

– Reconocimiento de patrones

– Fisiología del sistema nervioso

– Traducción automática de lenguajes

– etc

Lenguajes Formales

Las gramáticas han sido clasificadas de acuerdo a particularidades y restricciones propias, una de ellas y la más acertada es la formula dada por Noam Chomsky, quien clasificó las gramáticas, dando origen a la Jerarquía de Chomsky en función de la forma de reglas de derivación o producción.

Características de Los Tipos de Gramáticas

Gramáticas Regulares	Gramáticas Sensibles al Contexto	Gramáticas Independientes del Contexto(GIC)
-Genera cadenas a partir de una cadena vacía. -Las cadenas que puede generar el autómata son todas aquellas que pertenecen al lenguaje representado por el autómata L(M). -Todas las cadenas inician con una „a‟, luego viene una serie de a‟s o b‟s y finalmente termina con una b‟.	-Es importante tomar en cuenta la ubicación de los símbolos no terminales en la regla de derivación (que preceden y suceden a cada símbolo Terminal. -Deben mantener su ubicación en el lado derecho de la regla de producción. -Se caracteriza porque las partes Izquierdas y Derechas tienen que tener una parte común y se admite como regla compresora la regla S→ε.	-Es una cuádrupla G = (N, ∑ , S, P), donde: N: es una colección finita (no vacía) de símbolos no terminales. ∑: es un alfabeto. S: es un no terminal llamado símbolo inicial. P: un conjunto de producciones.

Ejemplo de Gramática Regular:

Por ejemplo las siguientes gramáticas G1 y G2, son gramáticas regulares lineales a derecha y lineales a izquierda respectivamente, que generan el lenguaje L = {a2n / n ≥ 0}

G1 = ({A, B}, {a}, P1, S1)                                     G2 = ({C, D}, {a}, P2, S2)

Donde P1 es el cjto.                                                 Donde P2 es el cjto.

S1 → ε                                                                      S2 → ε

S1 → aA                                                                   S2 → Ca

A → aB                                                                    C → Da

A → a                                                                       C → a

B → aA                                                                     D → Ca

Ejemplo de Gramática Sensible al Contexto:

L5={aⁱ b^j cⁱ d^j / i, j ≥0 }

G5=<{A, B, C}, {a, b, c}, S5, P5> donde P5 contiene las siguientes producciones:

S5→ ε                                    DC→CD

S5→ A                                   bC→bc

A→aAC                                 cC→cc

A→ac                                                cD→cd

A→B                                     dD→dd

B→bBD                                 bD→bd

B→ bD

Ejemplo de Gramática Independiente del Contexto(GIC):

Una simple gramática libre de contexto es:

S → aSb | ε

Donde | es un o lógico y es usado para separar múltiples opciones para el mismo no terminal, ε indica una cadena vacía.