Automatas clase 1

Lenguajes

Nota: Este resumen no pretende reemplazar las clases teóricas. Sólo fue confeccionado a los efectos de facilitar al alumno una guía acerca de los contenidos del curso.

Alfabeto(): Conjunto finito de símbolos donde un símbolo es un ente abstracto que no se define formalmente (así como no se definen los puntos en geometría).
Ejemplos de alfabetos:
Alfabeto de dígitos decimales1={0,1,2,3,4,5,6,7,8,9};
Alfabeto de dígitos binarios 2={0,1}
Alfabeto de las caracteres 3={a,b,…z,A,…Z, ?,!…,*,$}


Cadena
Una cadena  es una sucesión finita de símbolos, sobre un alfabeto .
Una cadena es simplemente representada como =s1s2…sn donde s1,s2,.. sn 
El símbolo si , 1 i  n, ocurre en la posición i de la cadena.
Por convención,  denota la cadena vacía (lacadena que no tiene símbolos).

Ejemplo1
Las cadenas 1,234 sobre B={a,b} se definen como:
1 = abab
2 =bbbb
3 = abbba
4 = 

Operaciones sobre cadenas

Sean dos cadenas sobre el alfabeto 
1=a1a2…an y 2 =b1b2…bm 1 ,2 *

Longitud de la cadena 1
|| denota la longitud de la cadena 
|| = n

Longitud sobre un elemento:
||adenota la cantidad de elementos ‘a’ que tiene la cadena

Igualdad de cadenas1y 2
12 si se cumple que || = || y (i: 1 i n: ai= bi )

Reversa de la cadena1
1R denota la reversa de la cadena 1
 Si 1=a1a2.....an entonces1R=an….a2a1

Concatenación de las cadenas 1 y 2
1.2 denota la concatenación que consiste de todos los símbolos de 1seguidos por los símbolos de 2. (el punto puede omitirse)
Si 1=a1a2.....an y 2=b1b2.....bn entonces
1.2 = a1a2…anb1b2…bm

Propiedades de la concatenación:
1) 1 . 2 es una cadena sobre 
2) 
3) 
4) No es conmutativa (aunque podría ser que para algunos casos sí lo sea)
5) R R R

Potencia k-ésimade la cadena1
1k denota la concatenación de la hilera 1una cierta cantidad informada de veces k
 i=0 ,
i .i-1 i>0

así
10 =
11 =1
12 =1.1
…
1k =1.1.1.1 ( k-veces 

Propiedad
|n| = n *||

Clausuras de una cadena
Clausura reflexiva { 0  1  2 , 3 , .....}

Clausura positiva { 1  2 , 3 , 4 .....}


Ejemplos de operaciones con las cadenas 1, 2 , 3 , 4 del ejemplo 1.
Longitud 1| = abab| = 4
4| = | = 0
Reversa 1R =baba
Concatenación 1.2 = ababbbbb
2.4 = bbbb
2.2 = bbbbbb
Potencia 23= 22.2 =bbbbbbbbbbbb
14=abababababababab


Clausura sobre el alfabeto *
El conjunto de todas las posibles cadenas sobre un alfabeto ,se describe como * también llamado Clausura de Kleene.
i=
*=  i
i=0
donde i es el conjunto de todas las cadenas de longitud i sobre 

En el ejemplo para el alfabeto ={a, b} calcular *
0 ={
1={a, b 
2={ aa, ab, ba, bb
3={ aaa,aab,aba,abb,baa,bab,bba,bbb}
…

Luego
*=0 1 2 3….= {, , a, b, aa, ab, ba, bb, aaa,aab,aba,abb,baa,bab,bba,bbb,…}

Nota: Las cadenas 123 , 4  *


Lenguaje
Un lenguaje L sobre un alfabeto  es un subconjunto de *, es decir un conjunto de cadenas sobre . L  *.

Por ejemplo los siguientes son Lenguajes sobre  ={0, 1}

L1 =  Lenguaje finito vacío
L2 = {} =  Lenguaje finito que contiene sólo la cadena vacía.
 neutro de la concatenación
L3 = {0, 1} Lenguaje finitoque contiene sólo las cadenas de longitud 1
L4 = {0, 00, 000, 0000,…} Lenguaje infinito que consiste de cadenas con cualquier
cantidad de símbolos 0.
L5 = {0 n1 n / n  1} = {01, 0011, 000111, 00001111,…}
Lenguaje infinito que consiste de cadenas que comienzan
con una cantidad de símbolos 0, seguidos por la misma cantidad de símbolos 1.

Operaciones con Lenguajes

Sean dos...