Page 18 - Revista FIUDE 2014

L = { 01, 10, 11, 000} es un lenguaje formado por
2
cuatro cadenas cuyo alfabeto es ∑ .
2
Algunos lenguajes son más complejos que otros.

L = { a, aa, ba, aaa, aba, baa, bba, … } es el lenguaje de todas las
3
cadenas cuyo alfabeto es ∑ que terminan en el símbolo ‘a’.
3
L = { 0#0, 1#1, 00#00, 01#01, 10#10, 11#11, … } es el lenguaje de
4
todas las cadenas cuyo alfabeto es ∑ que tienen un símbolo # en su centro y que a ambos lados del #
4
tienen la misma subcadena, la cual está formada por símbolos 0 y 1.

Estos últimos dos lenguajes L y L son lenguajes infinitos pues contienen una cantidad infinita de símbolos
4
3
y por lo tanto son más complejos que los lenguajes L y L que tenían una cantidad acotada y conocida
1
2
de símbolos.
En la Teoría de la Computación, los lenguajes se clasifican de acuerdo a su complejidad.
El científico Noam Chomsky definió tal clasificación de lenguajes mediante la denominada Jerarquía de
Chomsky en 1956.

Esta jerarquía establece que los lenguajes se pueden clasificar en cuatro grandes tipos:
• Lenguajes Regulares, generables mediante autómatas finitos.
• Lenguajes Independientes de Contexto, generables mediante autómatas de pila.
• Lenguajes Dependientes de Contexto, generables mediante autómatas linealmente acotados.
• Lenguajes Recursivamente Enumerables, generables mediante máquinas de Turing.

Todos estos autómatas que se mencionaron (finitos, de pila, linealmente acotados y máquinas de Turing)
son herramientas que se pueden utilizar para reconocer lenguajes.

El primer tipo de autómata, los autómatas finitos, se comportan como un tipo especial de máquina de
estados finita, la cual tiene una cantidad finita y conocida de estados.

Estas máquinas son modelos matemáticos computacionales que se pueden utilizar para todo tipo de
tareas como el modelado de flujos de trabajo, de circuitos electrónicos, protocolos de comunicación y
también se utilizan en la teoría de la computación.

La máquina en un momento concreto está en un único estado y puede pasar a otro estado por intermedio
de una transición (que lleva a la máquina de un estado a otro).

Dicha transición se ejecuta como respuesta a una entrada o un evento producido sobre la máquina.

Una Máquina de Estados Finita

Un ejemplo de máquina de estados finita es un controlador de una puerta automática.

Típicamente en la entrada a un supermercado suelen encontrarse puertas automáticas que se abren o
se cierran dependiendo de si un sensor ubicado encima de las puertas registra que hay una persona del
otro lado de la puerta automática o no.

El comportamiento de cómo debe actuar la puerta automática (si debe abrirse o cerrarse, permanecer
abierta o permanecer cerrada) puede estar dictaminado por una máquina de estados finita.

Reflexiones sobre Ingeniería