Conceptos Fundamentales de la Teoría de Autómatas
Alfabeto: conjunto de símbolos finito y no vacío:
\Sigma = { 0,1 } \text{, el alfabeto binario} \\
\Sigma = \{ a,b,\ldots,z \} \text{, el conjunto de todas las letras minúsculas}El conjunto de todos los caracteres ASCII.
El conjunto de todos los caracteres ASCII imprimibles.
Cadena de caracteres – palabra: secuencia finita de símbolos seleccionados de algún alfabeto:
01101 y 111 son cadenas del alfabeto binario.
Cadena vacía; cadena que presenta cero apariciones de símbolos y se puede construir con cualquier alfabeto, se designa por:
\varepsilon
Longitud de una cadena: número de posiciones ocupadas por símbolos dentro de una cadena, comúnmente se dice que la longitud de la cadena es el número de símbolos aunque no es estrictamente correcto:
\begin{aligned}
w = 001 \rightarrow |w| & = 3 \\
|001| & = 3 \\
|01101| & = 5 \\
| \varepsilon | & = 0
\end{aligned}Potencias de un alfabeto: la notación exponencial permite expresar el conjunto de todas las cadenas de una determinada longitud sobre un alfabeto:
\Sigma^k
conjunto de cadenas de longitud k tales que cada uno de los simbolos de las palabras pertenecen al alfabeto:
\begin{aligned}
\Sigma^0 & = \{ \varepsilon \} \\
\Sigma = \{ 0,1 \} \rightarrow \Sigma^1 & = \{ 0, 1 \} \\
\Sigma^2 & = \{ 00, 01, 10, 11 \} \\
\Sigma^3 & = \{ 000, 001, 010, 011, 100, 101, 110, 111 \}
\end{aligned}El conjunto de todas las cadenas de un alfabeto se designa por:
\begin{aligned}
\Sigma^* & = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots \\
\Sigma^+ & = \Sigma^1 \cup \Sigma^2 \cup \cdots \\
\Sigma^* & = \Sigma^+ \cup \{ \varepsilon \}
\end{aligned}Concatenación de Cadenas: es la cadena formada a partir de la copia de una cadena (x) seguida de la copia de otra (y), si la primera se compone de i símbolos y la segunda de j símbolos entonces la cadena xy se compondrá de i+j́ símbolos:
\begin{aligned}
x & = a_1 a_2 \cdots a_i & \wedge y & = b_1 b_2 \cdots b_j \\
\wedge |x| & = i & \wedge |y| & = j \\
& \rightarrow \\
& xy = a_1 a_2 \cdots a_i b_1 b_2 \cdots b_j \\
& |xy| = i+j
\end{aligned}\varepsilon w = w \varepsilon = w
\begin{aligned}
x & = 01101 \\
y & = 110 \\
xy & = 01101110 \\
yx & = 11001101
\end{aligned}Lenguaje: es un conjunto de cadenas seleccionadas de Σ*
L \subseteq \Sigma^*
El lenguaje de todas las cadenas que constan de n ceros seguidos de n unos, con n mayor o igual que 0:
\{ \varepsilon, 01, 0011, 000111, \dots \}El conjunto de cadenas formadas por el mismo número de ceros que de unos:
\{ \varepsilon, 01, 10, 0011, 0101, 1001, \dots \}El conjunto de números binarios cuyo valor es un número primo:
\{ 10, 11, 101, 111, 1011, \dots \}El lenguaje vacio (∅) es un lenguaje de cualquier alfabeto, pero:
\empty \neq \{ \varepsilon \}Definición de lenguaje mediante descripciones de conjuntos:
\begin{aligned}
& \{ w | w \text{ consta de un número igual de ceros que de unos} \} \\
& \{ w | w \text{ es un entero binario primo} \} \\
& \{ w | w \text{ es un programa en C sintácticamente correcto} \} \\
& \{ 0^n1^n | n \geq 1 \} \\
& \{ 0^i1^j | 0 \leq i \leq j \}
\end{aligned}Hopcroft, J., Motwani, R. y Ullman, J. 2007. Introducción a la teoría de autómatas, lenguajes y computación. Perason Educación: Madrid.