Introducción a la Teoría de Lenguajes y Autómatas

INSTITUTO TECNOLÓGICO DE JIQUILPAN

 [pic 1]

ING. SISTEMAS COMPUTACIONALES

Tema:

Ensayo Unidad I: Introducción a la Teoría

 de Lenguajes y Autómatas

Alumna:

María Magdalena Rodríguez Avalos   14420518

Asesoría:

                                                Lic. Odiseo

Asignatura: Lenguaje y Autómatas

                                                            JIQUILPAN, MICH., 28/08/2017

Unidad 1: Introducción a la Teoría de Lenguajes y Autómatas

Introducción:

 En el siguiente ensayo se podrá identificar los conceptos teóricos y necesarios, al igual que algunos ejemplos relacionados con los temas de la unidad 1, de la materia de Lenguajes y autómatas 1, por lo cual se realizaron las investigaciones necesarias para  poder comprender mejor los conceptos principales de la unidad, ya que son la base para comenzar con la materia, y nos resulte fácil en el transcurso de las unidades.

1. Alfabeto

Se le llama  alfabeto a un conjunto finito no vacío cuyos elementos se denominan “letras” o “símbolos”. Por lo que  se denomina palabra a toda secuencia finita  de letras formadas por símbolos de un alfabeto. Generalmente se utiliza la letra Σ para identificar  alfabetos, por lo que se  puede definir por la enumeración de los símbolos que contiene.

Ejemplos.

Σ1 = {0, 1}

Σ2 =  { a, b }

Σ3 = {  na, pa, bra, la}

Σ4 =  { , ,  , }

Σ5 =  { a,ab,aab}

Se utilizan meta-símbolos(tal como { , }, =, y la coma )para escribir sobre lo que hablamos, así que siempre se tendrá claro cuando se trate de un símbolo del alfabeto, o si se trata de un meta-símbolo.

Se utilizan subíndices para distinguir diferentes alfabetos, normalmente usamos  minúsculas como alfabeto S= { a,. . . . . . . ,z,}, en los ejemplos, ósea que pueden ser letras desde el principio del alfabeto.

Símbolos:

Un “símbolo” es una entidad abstracta. Los cuales normalmente están formados por varias letras, dígitos, y caracteres como las siguientes:

 Letras (a,  b, c,...Z)

Dígitos (0,1,....9)

Caracteres (+, - , * , /, <, >....).

Longitud de una palabra

Se llama longitud de una palabra x, y se representa por |x|, al número de símbolos que la componen.

Ejemplos: sobre Σ5 ={a,b,c,d}: |λ|=0, |a|=1, |abc|=3

Concatenación.

Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda)

Ejemplos: x =abc, y =da, definidos sobre Σ={a,b,c,d} xy=abcda ; |xy|=|x|+|y|=5

Potencia

Sea i un número natural, y x una palabra. La potencia i-ésima de x, denominada xi, es la operación que consiste en concatenarla consigo misma i veces.

Ejemplos: x =abc

    ⇒ x1=abc     x2=abcabc      x3=abcabcabc

Palabra inversa 

Sea x=A1A2...An con Ai∈Σ una palabra sobre el alfabeto Σ. Se llama palabra refleja o inversa de x, y se representa por x-1, a la palabra AnAn-1...A1. Si x=λ entonces x-1=λ.

Ejemplos: x =abc

             ⇒ x-1=cba

1. Cadena

Es una cadena o palabra sobre un alfabeto Σ. Donde se admite la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ o Є. La cadena vacía desempeña, en la teoría de lenguajes formales, un papel similar al que desempeña el conjunto vacío Ø en la teoría de conjuntos.

Habitualmente, se emplean las letras minúsculas del principio del alfabeto (o dígitos) para designar a los símbolos y las letras minúsculas del final del alfabeto, normalmente w, x , y ,z, para designar cadenas.

Longitud de cadena.

Es el número de símbolos que contiene la cadena. La notación que se utiliza es la que se mostrara en el siguiente ejemplo:

|abcb|=4

| a+2*b |= 5

| 0001111| =6

| if > ab then a = b; |=9

Cadena Vacía.

Una cadena vacía es la única cadena de caracteres de tamaño cero, que puede construirse en cualquier alfabeto. Y la podemos denotar usualmente con letras λ o Є (Griegas).

Concatenación  de cadenas.

 La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. La yuxtaposición se utiliza como el operador de concatenación. Esto es si w y  x son cadenas, entonces wx es la concatenación de estas dos cadenas.  Por lo cual la cadena vacía es la identidad para el operador de concatenación, es decir  Єw= Єw para cada cadena de w.

Ejemplo:

Sea u=ab

        v= ca

        w= bb.

Forman las siguientes cadenas

     uv= abca

     uw = cabb

    (uv) w = abcabb

    U (vw)= abcabb

Universo del discurso.

Es un conjunto de todas las cadenas donde podemos formar con símbolos del alfabeto V le denominamos universo del discurso de V y la representamos de la siguiente manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadena vacía pertenece a W(V).

Ejemplo:

Un afabeto con una sola letra V = { a }, podemos decir que el universo del discurso es:

...