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={ai
bj ci dj / 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.
