Linguistica Matemática

Notas de Clases
Carrera: Analista de Sistemas.

Cátedra: Fundamentos de Ciencias de la Computación.

Lingüística Matemática
1.-Introducción a la teoría de Lenguajes Formales
1.1.-Alfabetos, Palabras y Lenguajes.

ALFABETO: Conjunto finito no vacío de símbolos diferentes
Los símbolos, también llamados caracteres, son entidades abstractas indivisibles carentes de
estructura y significadopropio, que nos permitirán construir otras entidades más complejas que
serán objeto de estudio de esta asignatura.
Los símbolos más usados por el ser humano son las letras y los dígitos decimales.
Para poder representar formalmente estas entidades identificaremos a cada símbolo con un
“nombre”. Es importante no confundir el símbolo con el nombre del mismo.
Ejemplo: si al símbolo “$“lollamamos “Peso”, pero en otro contexto podría llamarse “Dollar”, y
el símbolo sigue siendo el mismo.
Para describir un hecho o entidad se utilizan conjuntos de símbolos que en general llamados
datos. Por otro lado una información es un conjunto de datos significativos, es decir datos
que cumplen con los siguientes requisitos: reconocibles, íntegros, inequívocos y relevantes.
Aunque es obvio, elrequisito más importante para que un conjunto de datos sea significativo es
que debe ser reconocible, o sea que se los pueda entender. Por lo tanto es fundamental
conocer el conjunto total de símbolos con el que se forman los datos, esto es el ALFABETO
utilizado para representar los mismos.
Ejemplo: el conjunto (0,1) constituye el alfabeto BINARIO, con el que se represen tan los datosinternamente en un computador. Otros ejemplos informáticos son los códigos ASCII y EBCDIC
que constituyen los alfabetos más usados para la representación externa de datos en el ámbito
computacional.
PALABRA sobre un ALFABETO: Secuencia finita de símbolos pertenecientes a ese
alfabeto.

Una palabra sobre un alfabeto  dado, también denominada cadena o string, constituye lo que
formalmente se conocecomo un arreglo con repeticiones de elementos de .
Ejemplo: 13302 es una palabra sobre el conjunto de dígitos.
Dentro de este contexto definiremos la palabra vacía como aquella secuencia que no contiene
símbolo alguno y la denominaremos de ahora en adelante  (lambda)
Definiremos los siguientes conceptos considerando una palabra w sobre un alfabeto .



Un PREFIJO de w es una secuenciaformada por cero o más símbolos
iniciales consecutivos.
Un SUFIJO de w es una secuencia formada por cero o más símbolos finales

Notas de Clases
Carrera: Analista de Sistemas.

UNPA –Unidad Académica Caleta
Olivia

Cátedra: Fundamentos de Ciencias de la Computación.
Profesora: Ing. Viviana B Mercado



consecutivos.
Una SUBCADENA de w es cualquier secuencia de símbolos obtenida.mediante la eliminación de un prefijo y/o un sufijo de w.

Por lo tanto se cumple que w y  son prefijos, sufijos y subcadena de w. También se cumple
que todo prefijo o sufijo de w es a la vez una subcadena de w.
Ejemplo: Suponiendo la palabra w = aeio del alfabeto
 ( todas las letras ), tenemos que:
Los prefijos de w son: ,a, ae, aei, aeio
Los sufijos de w son: , o, io, eio, aeio
Lassubcadenas de w son: , a, e, i, o, ae, ei, io, aei, eio, aoio
Si  es un alfabeto, entonces la notación * representa al conjunto de todas las palabras w
formadas por símbolos de un alfabeto  , es decir el Conjunto Universal de los arreglos con
repeticiones de símbolos pertenecientes a  , incluyendo la palabra vacía . Por otro lado la
notación *’ se refiere al conjunto universal excepto lapalabra vacía, es decir que:
+
 = * - {  }
LENGUAJE Formal: Cualquier subconjunto L del Conjunto Universal de palabras sobre un
alfabeto . Es decir, L  *

En esta definición el Lenguaje, desde un punto de vista estrictamente matemático, no le asigna
significado alguno a las palabras que lo componen sino que simplemente las describe.
Ejemplo:
 El conjunto de todas las oraciones...