Autómatas y Lenguajes formales

Están constituidos por:

Símbolo

Entidad abstracta que no se define formalmente.

Ejemplo: 2, 5, $, V

Palabra

Representa una cadena finita de símbolos.

Ejemplo X="12"

Longitud de una palabra

Está conformada por el número de símbolos que conforman dicha palabra.

Ejemplo: Sea la cadena X="514", su longitud será lXl=l514l=5

Palabra vacia

Cadena que no tiene símbolos se denota por "€" y "^"

Ejemplo: Sea T="", entonces T=€

Conceptos Basicos

Alfabeto

Conjunto finito de símbolos y no vacío.

Ejemplo: Alfabeto Español

Alfabeto ∑

Conjunto finito de símbolos y no vacío.

Ejemplo: ∑= {5,6,7,8}, entonces 6€∑

Universo de un alfabeto ∑

Todas las palabras que se pueden formar con símbolos, contienen elementos indefinidos.

Ejemplo: Si ∑= {2,3,4,5}. Sera W(∑)= {ʌ,2,3,4,5, 23, 24,25, ...}

Permiten realizar operaciones como:

Concatenación

M1 y M2 son 2 cadenas la concatenación se da al añadir a la cadena M1 la palabra M2.

Potencia

La potencia i-ésima de una palabra V, corresponde a la concatenación i veces de la palabra V con ella misma.

Reflexión

Sea la palabra F= X1, X2, .. Xn se tiene que la cadena inversa de F denotada por Fl, se forma invirtiendo los simbolos de la palabra F= Xn, . . X2, X1.