Aplicaciones
De los autómatas finitos:
- Software para el diseño y verificación de circuitos digitales.
- Analizador léxico de un compilador.
- Software para explorar textos.
- Software para comprobar el funcionamiento de un sistema con varios estados diferentes.
De las gramáticas:
- Descripciones de analizadores sintácticos (parsers), análisis sintáctico.
- Descripción de formatos de documentos (XML, lenguajes de programación, etc).
De las expresiones regulares:
- Especificación de patrones de cadenas.
- Diseño de software de verificación de un formulario web.
Definiciones
Alfabetos y palabras
Ejemplo: $\Sigma = \set{0, 1}$
La cadena vacía ($\lambda$, $\epsilon$) es la que no contiene ningún símbolo.
Recordar que $|w|$ es el número de símbolos de la cadena $w$.
Ejemplo: $a = ‘0110101’$
Ejemplo: $\Sigma^{2} = \set{‘00’, ‘01’, ‘10’, ‘11’}$
El cierre de un alfabeto contiene todas las posibles cadenas que se pueden formar con él, salvo la cadena vacía.
$$ \Sigma^{+} = \Sigma^1 \cup \Sigma^2 \ldots $$El cierre de un alfabeto contiene todas las posibles cadenas que se pueden formar con él, incluyendo la cadena vacía.
$$ \Sigma^{*} = \set{\lambda} \cup \Sigma^1 \cup \Sigma^2 \ldots = \set{\lambda} \cup \Sigma^{+}$$Si la secuencia de símbolos $A_1 \ldots A_n$ es la cadena $a$, y $B_1 \ldots B_m$ es la cadena $b$, entonces la concatenación se define como:
$$ ab = A_1 \ldots A_n B_1 \ldots B_m $$Ejemplo: $a = ‘00’, b = ‘11’ \implies ab = ‘0011’$
Ejemplo: $a = ‘01’ \implies a^3 = ‘010101’$
Si la secuencia de símbolos $A_1 \ldots A_n$ es la cadena $a$, entonces la cadena inversa $a^{-1}$ se forma invirtiendo el orden de los símbolos:
$$ a^{-1} = A_n \ldots A_1 $$Ejemplo: $a = ‘01’ \implies a^{-1} = ‘10’$
Lenguajes
Cualquier conjunto de cadenas del alfabeto $\Sigma$ será un lenguaje de $\Sigma$.
$$ L \subseteq \Sigma^{*}$$El alfabeto sobre el que se define debe ser finito, pero los lenguajes pueden tener un infinito número de cadenas.
Ejemplos:
- Lenguaje vacío: $L = \varnothing$
- Lenguaje con solo la cadena vacía: $L = \set{\lambda}$
- El número de
0es igual al de1: $L = \set{ w | |w|_0 = |w|_1 }$
==> Ejemplos de cadenas: $‘0011’, ‘10’, ‘1010’$ - $L = \set{0^n 1^n | n \ge 1}$
==> Ejemplos de cadenas: $‘01’, ‘0011’, ‘000111’$ - $L = \set{a^i b^j c^k | j = i+k \quad \forall i,j,k > 0}$
==> Ejemplos de cadenas: $‘aabbbc’, ‘abc’, ‘aaabbbbbcc’$
| Operaciones con lenguajes | |
|---|---|
| $L_1 \cup L_2$ | Contiene todas las palabras que pertenecen a cualquiera de ellos. |
| $L_1 \cap L_2$ | Contiene todas las palabras que pertenecen a ambos. |
| $L_1 - L_2$ | Contiene todas las palabras que pertenecen a $L_1$ pero no a $L_2$. |
| $L_1 \cdot L_2$ | Contiene todas las palabras que se pueden formar por la concatenación de una palabra de $L_1$ y otra de $L_2$. |
| $L^i$ | La potencia $i$-ésima es la concatenación $i$ veces consigo mismo. |
| $L^-$ | La reflexión se forma por la aplicación de la reflexión a todas las cadenas. |
Gramáticas
Es decir, define las sentencias que lo forman, proporcionando formas válidas en que se pueden combinar los símbolos del alfabeto.
Chomsky hizo una clasificación de las gramáticas:
- G0 o Tipo 0: gramáticas sin restricciones (GSR)
- G1 o Tipo 1: gramáticas sensibles al contexto (GSC)
- G2 o Tipo 2: gramáticas independientes del contexto (GIC)
- G3 o Tipo 3: gramáticas regulares
Autómata
Dada una cadena de símbolos presentados a su entrada, produce una cadena de símbolos a su salida, en función de dichas entradas y los estados internos por los que transita la máquina.
Por ejemplo, el autómata de un interruptor de luz:
stateDiagram-v2
direction LR
q0: Off
q1: On
[*] --> q0
q0 --> q1: Pulsar
q1 --> q0: Pulsar
Tiene dos posibles entradas: presionar el botón o no presionar el botón; y produce dos posibles respuestas: encender la luz o apagar la luz, en función de si antes estaba apagada la luz o encendida.
Relación entre máquina, lenguaje y gramática
- Una máquina es una representación de la gramática
- Una gramática describe un lenguaje, determina sus características
- Una máquina reconoce un lenguaje
flowchart TB
L[Lenguaje]
G[Gramática]
M[Máquina]
G <-- Equivale --> M
M -- Genera / Reconoce --> L
G -- Genera / Describe --> L
Y la correspondencia entre los diferentes tipos de gramáticas y las máquinas es la siguiente:
| Gramática | Lenguaje | Máquina | Complejidad |
|---|---|---|---|
| Tipo 0: G0 - Sin restricciones | Recursivamente enumerable | Máquina de Turing | Indecibible |
| Tipo 1: G1 - Sensible al contexto | Sensible al contexto | Autómata linealmente acotado | Exponencial |
| Tipo 2: G2 - Independiente de contexto | Independiente del contexto | Autómata con pila | Polinómica |
| Tipo 3: G3 - Regulares | Regular | Autómata finito | Lineal |
Jerarquía de Chomsky
$$ L_{\text{RE}} \subset L_{\text{REC}} \subset L_{\text{CS}} \subset L_{\text{CF}} \subset L_{\text{DCF}} \subset L_{\text{REG}} $$- Máquina de Turing
- $L_{\text{RE}}$: Lenguaje Recursivamente Enumerable
- $L_{\text{REC}}$: Lenguaje Recursivo
- Autómata linealmente acotado
- $L_{\text{CS}}$: Lenguaje Dependiente de Contexto
- Autómata con pila
- $L_{\text{CF}}$: Lenguaje Independiente de Contexto (Context Free)
- Autómata finito
- $L_{\text{DCF}}$: Lenguaje Determinista Independiente de Contexto
- $L_{\text{REGs}}$: Lenguaje regular