Automatas

LENGUAJES, GRÁMATICAS Y
AUTÓMATAS

Unidad 7

LENGUAJES, GRÁMATICAS Y AUTÓMATAS

LENGUAJES, GRÁMATICAS, AUTÓMATAS
Después de un “arduo” recorrido hemos llegado al último tema del programa, que está muy relacionado con las
ciencias de la computación. Vivimos en la era de las comunicaciones, y día a día nos encontramos con problemas
que podemos llamar “de entrada” y “de salida”. Nosreferimos a acciones que realizamos, por ejemplo, cuando
subimos al colectivo: las monedas que introducimos en la máquina constituyen la “ entrada “ y el boleto la “salida”.
Otro ejemplo cotidiano lo constituye la computadora: la entrada son los datos, la información, y la salida es el
resultado que se obtiene después de haberlos procesado. En todos esos casos, se utilizan tipos de lenguajesmediante los cuales las máquinas pueden procesar la información de entrada y realizar las acciones para la
operación de salida.
En esta unidad recurriremos a muchos de los conceptos ya estudiados para abordar un tema nuevo que son las
máquinas de estado finito o circuitos secuenciales ( recordemos que ya vimos circuitos no secuenciales, las redes
de compuertas, en álgebra de Boole)
Para elloabordaremos primero el concepto de lenguaje formal y de gramática.

Según el Webster´s New Coollegiate Dictionary, un lenguaje es un conjunto de palabras y métodos paraa
combinar palabras, que es usado y entendido por un extenso grupo de personass1.

Con frecuencia a lenguajes de tal tipo se los llama lenguajes naturales para distinguirlos de los formales, que son los
que se aplican para modelarun lenguaje natural y “comunicarse” con la computadora. Sin embargo, ambos tipos de
lenguajes tienen algunas cuestiones en común como por ejemplo un alfabeto y reglas gramaticales.
Concretando, los lenguajes pueden clasificarse en naturales y formales.
Los lenguajes naturales se caracterizan por:
- una semántica, es decir, un significado
- una sintaxis, es decir, un conjunto de reglasgramaticales.
Son ejemplos de este tipo de lenguaje, los lenguajes de seres humanos, tales como: chino, español, inglés.
Los lenguajes formales se caracterizan por tener reglas gramaticales preestablecidas. Son ejemplo de este tipo de
lenguaje los lenguajes de programación. Nos ocuparemos en esta unidad de tratar sus particularidades.
Para entender el significado del concepto lenguaje vamos a definirprimero otros tales como alfabeto, letra y palabra.

Un alfabetoo es un conjunto no vacío y finito de símbolos. Los símbolos del alfabeto son las letras, strings o
caracteres. Suele indicarse con la letra V.

1

, USA, 2008, ISBN 978-0-87779-916-0

1

Unidad 7

LENGUAJES, GRÁMATICAS Y AUTÓMATAS

Tengamos en cuenta que un alfabeto, como todo conjunto, debe estar bien definido, esdecir no deben quedar
dudas acerca de cuáles son los elementos que lo componen, por ejemplo si el alfabeto fuera {a, b, ab} se
plantearían dudas acerca del elemento ab, ¿es un elemento del conjunto?, ¿se construyó usando a, b?; esas
dudas no pueden existir.
Los elementos que pertenecen al conjunto Alfabeto se denominan letras, por ejemplo la letra e forma parte de los
alfabetos que se usan enlos idiomas español, italiano, inglés, entre otros.
Para el alfabeto V= {a, b}, tanto la a, como la b son letras, simplemente por ser elementos del ese conjunto.

Toda secuencia finita de letras de un alfabeto se denomina palabra.

Por ejemplo para el alfabeto V={0,1} -que muchas veces se denomina alfabeto binario- son palabras 1101,
001110. Podemos indicarlas w=1101, z=001110.
Al conjuntode todas las palabras que se pueden construir con las letras de un alfabeto se lo indica V*; tengamos
en cuenta que si bien el alfabeto es finito, V* no lo es.
Por ejemplo: Sea V = {a, b}, el alfabeto formado por los símbolos a y b.
v = ababbaaaw = bbbbx = aaaaason palabras de V*.
Llamamos O a la palabra nula., es decir aquella que no tiene letras.
Algo para tener en cuenta es que convenimos...