Lenguajes Y Automatas

ALFABETO
El alfabeto, abecedario o abecé de una lengua o idioma es el conjunto ordenado de sus letras. Es también la agrupación, con un orden determinado, de las grafías utilizadas para representarel lenguaje que sirve de sistema de comunicación.
Es el conjunto de letras de un idioma, con un determinado orden. Más precisamente, el alfabeto es un conjunto de letras (caracteres o grafemas) de unsistema de escritura, cada una de las cuales representa aproximadamente un fonema (consonante o vocal).
Un Alfabeto es cualquier conjunto finito, no vacío.

CADENA
Una cadena es una secuenciafinita de símbolos de un determinado alfabeto.
Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:
Abcb es una cadena del alfabeto V2
a+2*b es una cadena delalfabeto V2
000111 es una cadena del alfabeto V3
If a>b then b=a; es una cadena del alfabeto V4
LONGITUD DE CADENA
La longitud de una cadena consiste en el número de símbolos pertenecientes a lacadena. Tomando en cuenta los ejemplos de cadena podemos decir que:
·   |abcb| es de longitud 4
·   |a + 2*b| es de longitud  5
·   |000111| es de longitud  6
·   |If a>b then a=b;| es delongitud  9

CADENA VACÍA
Se denomina cadena vacía, que no tiene símbolos y se denota con l, por lo que su longitud es:
| l | ® 0
CONCATENACIÓN DE CADENAS
Sean A y B dos cadenas cualesquiera, sedenomina concatenación de A y B a una nueva cadena AB constituida por los símbolos de la cadena A seguidos por los de la cadena B.
El elemento neutro de la concatenación es l:
A l =  lA = A

LENGUAJE:Si Σ es un alfabeto, y L ⊆ Σ
Entonces L es un lenguaje.
Ejemplos de Lenguajes:
El conjunto de las palabras de Ingles válidas
El conjunto de los programas escritos en C válidos
El conjunto delas cadenas que consisten de n 0’s
Seguidos de n 1’s
{Ǫ, 01, 0011, 000111}
El conjunto de todas las cadenas con igual número
De ceros que de unos
Ǫ, 01, 10, 0011, 0101, 1010, 1100, . . .
Un...