$Q$: Conjunto finito de estados.

$\Sigma$: Alfabeto de entrada.

$\delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)$: Función de transición (no-determinista, puede incluir $\epsilon$-movimientos).

$q_0 \in Q$: Estado inicial.

$F \subseteq Q$: Conjunto de estados finales (o de aceptación).

Equivalencia de Modelos:

Teorema 1: Para cada AFND $M_{ND}$ que reconoce un lenguaje $L$, existe un AFD $M_D$ que también reconoce $L$.
Teorema 2: Un lenguaje $L$ es generado por una Gramática Regular si y sólo si $L$ es reconocido por un Autómata Finito (AFD o AFND).

Lenguaje probabilístico ($L, P$): Dado un alfabeto $\Sigma$, $P$ es una función de probabilidad sobre $\Sigma^*$ tal que:
- $P(x) \ge 0$ para toda $x \in \Sigma^*$.
- $\sum_{x \in L} P(x) = 1$.
- $P(x) = 0$ si $x \notin L$.
Teorema de Wetherell: Un lenguaje es probabilístico si y sólo si es generado por una Gramática Probabilística Incontextual (GPI) y la suma de las probabilidades de todas las cadenas de $L$ es 1.
Gramáticas Regulares Probabilísticas (GRP): $G_\theta = (G, P)$, donde $G=(N, \Sigma, S, P_G)$, y $P: P_G \to ]0,1]$ son las probabilidades de las reglas.
- Condición de normalización: $\forall A \in N, \sum_{A \to \beta \in P_G} P(A \to \beta) = 1$.
- Probabilidad de un árbol de análisis: $P_\theta(x, t_x) = \prod_{r_j \in t_x} P(r_j)$.
- Probabilidad de una cadena: $P_\theta(x) = \sum_{t_x \in T_x} P_\theta(x, t_x)$.
- Probabilidad del mejor árbol: $\hat{P}_\theta(x) = \max_{t_x \in T_x} P_\theta(x, t_x)$.

Regla de clasificación de Bayes: Para clasificar una cadena $x$ en una de $K$ clases $C_1, \dots, C_K$: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} P(C_i|x) $$ Expandiendo con el Teorema de Bayes: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} \frac{P(x|C_i)P(C_i)}{P(x)} $$ Como $P(x)$ es constante para todas las clases, se simplifica a: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} P(x|C_i)P(C_i) $$ Donde $P(x|C_i)$ es la probabilidad de observar la cadena $x$ dado el modelo probabilístico (ej. HMM o GRP) asociado a la clase $C_i$, y $P(C_i)$ es la probabilidad a priori de la clase.

Definición: $M = (\Sigma, Q, \pi, A, B)$.
- $\Sigma$: Alfabeto de símbolos observables.
- $Q$: Conjunto de estados.
- $\pi$: Vector de probabilidades iniciales, $\pi_q = P(q_1 = q)$.
- $A$: Matriz de transición de estados, $A_{q,q'} = P(q_{t+1} = q' | q_t = q)$.
- $B$: Matriz de emisión de símbolos, $B_{q,\sigma} = P(x_t = \sigma | q_t = q)$.
Condiciones de Normalización:
- $0 \le \pi_q \le 1$, $\sum_{q \in Q} \pi_q = 1$.
- $0 \le A_{q,q'} \le 1$, $\sum_{q' \in Q} A_{q,q'} = 1$.
- $0 \le B_{q,\sigma} \le 1$, $\sum_{\sigma \in \Sigma} B_{q,\sigma} = 1$.
Probabilidad de una cadena:
- Probabilidad de $x$ y una secuencia de estados $y$ juntos: $$ P(x, y; M) = \pi_{y_1} \prod_{t=2}^T A_{y_{t-1},y_t} \prod_{t=1}^T B_{y_t, x_t} $$
- Probabilidad de $x$ (marginando sobre todas las secuencias de estados $y$):