Reflexión sobre autómatas finitos

¿Qué sabe un AF? #

Para procesar una cadena lo único que sabe un autómata es:

  1. La posición de la cadena que ya analizó
  2. El estado en el que se encuentra

¿Qué le pasa al espacio de \(\Sigma^*\) mientras procesamos una cadena? #

Nos movemos entre los conjuntos de cadenas aceptadas y cadenas rechazadas. El espacio lo podemos dividir en dos partes: cuando estamos en una estado no final y cuando estamos en un estado final.

Por ejemplo, para el lenguaje de cadenas con número par de bes ( aquí como expresión regular y aquí como autómata finito), habría el conjunto de estados se separaría en dos uno asociado a \(q_0 \) y otro a \( q_1 \) .

Ilustración de partición de sigma para lenguaje número par de bes

comments powered by Disqus