Alfabetos Y Lenguajes

Instituto Tecnológico de Tuxtla Gutiérrez

Teoría de la Computación

Introducción
Tema: Cadenas, Lenguajes y Autómatas.
Por contraposición al lenguaje propio de los seres vivos y en especial ellenguaje
humano, considerados lenguajes naturales, se denomina lenguaje formal a los
lenguajes «artificiales» propios de las matemáticas o la informática, los
lenguajes artificiales son llamados lenguajesformales (incluyendo lenguajes de
programación).
En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un
conjunto de palabras (cadenas de caracteres) de longitud finita en loscasos más
simples o expresiones válidas (formuladas por palabras) formadas a partir de un
alfabeto (conjunto de caracteres) finito. El nombre lenguaje se justifica porque
las estructuras que con estese forman tienen reglas para la formación de
expresiones válidas (gramática) e interpretación de estas expresiones semántica
(significado) en una forma muy similar a los lenguajes usados por el serhumano.
La idea básica es considerar a un lenguaje como un conjunto compuesto por
cadenas de longitud finita formadas por símbolos tomados de un alfabeto. Es
decir, dado un alfabeto
, decimos que
,(para
un dado, que llamamos longitud de ) es una cadena construida con
símbolos de . Si
tenemos la cadena llamada vacia, y denotada por . Al
conjunto formado por de todas las cadenas que se puedenconstruir con las
letras de dicho alfabeto se le llama lenguaje universal y se le denota por * . Es
evidente que el número de elementos de * es infinito numerable. Entre las
cadenas, como elementos de * , sedefine una operación, llamada
concatenación, mediante la cual a dos cadenas dadas
cadena

obtenida por yuxtaposición de
*, e
, sería :

* se le asocia otra

; es decir, si
*, entonces la cadena

.Llamamos lenguaje construido con el alfabeto , a cualquier subconjunto L de
*. Diremos que un lenguaje es finito, si es finito el número de cadenas de que
consta; en otro caso diremos que es infinito....