AUTOMATAS Y LENGUAJES

DEFINICIONES PREVIAS
Símbolo: Es un conjunto que se deja como verdad, los símbolos son letras, dígitos, caracteres o cadenas de letras y/o caracteres asi como también las palabras reservadas de algún lenguaje de programación. Por ejemplo:
A,b,c,#,%,0,1,+,*,then, end, else.

Vocabulario o Alfabeto: Es un conjunto finito de símbolos. El alfabeto esta representado por el símbolo V y se define por enumeración en forma ascendente. Para decir que un símbolo pertenece a cierto alfabeto se denota por el símbolo Є. Ejemplo:
V1 {A, B, C, D, E,}
V2 {a, b, c, 0, 1, 2}
V3 {if, then, end, a, b, =, ;, >}

Cadena: Es la secuencia de símbolos de un determinado alfabeto, por ejemplo: utilizando los alfabetos del tiempo anterior
abc es una cadena del alfabeto V2
if a>b then b=a; es una cadena del alfabeto V3

Longitud de Cadena: Es el numero de símbolos que tiene la cadena. Por ejemplo:
|abcd| 4
|if a>b then b=a;| 9

Cadena vacía: Es aquella que no tiene símbolos y se representa con el símbolo λ y su longitud es cero. Ejemplo:
|λ| 0

Concatenación de cadenas: Es aquella en donde dos cadenas α y β forman una nueva αβ integrados pos los símbolos de la cadena α seguidos por los de la β. El elemento neutro de la concatenación es λ. Ejemplo:
αλ = λα = α

Universo del discurso: Es el conjunto finito de todas las cadenas que se pueden formar con los símbolos de un alfabeto y se representa W(V). la cadena vacía también pertenece a W(V). Ejemplo:
del alfabeto V={a}
W(V)={λ, a, aa, aaa, aaaa, ……}

Lenguaje: Es un subconjunto del universo del discurso o también se puede definir como un conjunto de palabras de un determinado alfabeto. Ejemplo: sobre el alfabeto {0, 1}. Este lenguaje tiene infinitas cadenas. Algunas cadenas de este lenguaje serian
λ
0
1
0011
010
0110
000000101101
111111

Lenguaje vacio: Es un conjunto vacio que se denota por {0}. Hay que tener cuidado de no confundirlo con una cadena vacía {λ} ya que en este caso el numero de elementos (Cardinal) es diferente. Ejemplo:
Cardinal ({0}) = 0
Cardinal ({λ}) = 1

Gramática: Es el conjunto de cadenas de símbolos que constituyen un lenguaje.

Autómata: Es una construcción lógica que recibe una entrada y produce una salida. En caso de los procesadores de lenguaje un autómata es una construcción lógica que recibe como entrada una cadena de símbolos y produce una salida indicando si dicha cadena pertenece o no a un determinado lenguaje.