La intersección es el ejemplo más fácil de mostrar directamente.
Los autómatas de estado finito se cierran debajo de la intersección porque siempre podemos crear un estado por pares que represente la operación de los dos autómatas originales, y aceptar una cadena solo si ambos autómatas aceptan. Esto ejecuta efectivamente ambos autómatas en paralelo. Un FSA es muy limitado en la salida de un solo bit, es una relación de un conjunto X con el conjunto {0,1}.
Por otro lado, los transductores de estado finito producen salida. Podemos construir fácilmente un FST [matemático] P [/ matemático] que mapea una cadena [matemática] a ^ nb ^ m [/ matemático] a [matemático] c ^ n [/ matemático] (suponiendo que se permita una salida nula) y un similar [math] Q [/ math] que asigna una cadena [math] a ^ nb ^ m [/ math] a [math] c ^ m [/ math]. Como relaciones regulares, estos se ven como
- ¿Resolver acertijos me hará mejor en matemáticas, física, informática o resolución general de problemas?
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
- ¿Alguna vez eres totalmente experto en matemáticas?
- ¿Cuál es la mejor manera de encontrar números amistosos hasta N?
- ¿Es P vs NP el problema más difícil e importante del Premio del Milenio?
P = {(,), (b,), (bb,),…, (a, c), (ab, c), (abb, c),…, (aa, cc), (aab, cc) , (aabb, cc), …}
Q = {(,), (a,), (aa,),…, (b, c), (ab, c), (aab, c),…, (bb, cc), (abb, cc) , (aabb, cc), …}
Pero [matemáticas] P \ cap Q = \ {(,), (ab, c), (aabb, cc), (aaabbb, ccc), \} [/ matemáticas], esa es la relación entre [matemáticas] a ^ nb ^ n [/ math] y [math] c ^ n [/ math]. Pero sabemos que las máquinas de estado finito no son lo suficientemente potentes como para reconocer [matemáticas] a ^ nb ^ n [/ matemáticas], por lo que no puede haber tal FST.
En este ejemplo, puede ver que no hay forma de ejecutar P y Q en paralelo dentro de la misma máquina: P cuenta las a y omite las b, mientras que Q omite las a y cuenta las b, por lo que la transformación que utilizamos para las FSA no puede ser hecho para trabajar. (Y como muestra el ejemplo, no existe una posible transformación).
Una vez que hemos demostrado que la intersección es imposible, las otras propiedades se derivan de las equivalencias establecidas: por ejemplo, si pudiéramos encontrar complementos, entonces también podríamos encontrar la intersección ya que [matemáticas] P \ cap Q = \ neg (\ neg P \ taza \ neg Q) [/ matemáticas]
