La respuesta de Justin Rising le da la idea correcta: no puede construir un autómata que pueda simular cualquier autómata que reciba como entrada, porque independientemente del tamaño de su autómata, siempre puedo pedirle que simule uno más grande. En realidad, esta es también la esencia de la prueba formal que se presenta a continuación: el punto principal de la prueba es que ninguna cantidad finita de memoria es suficiente.
La respuesta de Quora User está en el camino correcto, pero hay algunos detalles formales que vale la pena corregir.
Como dice correctamente en los detalles de la pregunta, un lenguaje universal para el conjunto de todos los idiomas regulares puede definirse como el idioma de todas las cadenas de la forma “código de una palabra de entrada de autómata # aceptada por ese autómata”.
- ¿Hay ejemplos fractales que usen entradas aleatorias externas de alguna manera en las iteraciones?
- ¿Qué es la teoría de Ramsey y cómo se relaciona con la informática?
- ¿Cómo funcionan los ajustes del algoritmo del generador de sueños?
- ¿Se pueden programar las computadoras con 0,1 y 2? ¿Qué tal 0,1,2 y 3? ¿O son todos los programas manipulaciones de 0 y 1? Nuevos detalles añadidos para explicar.
- ¿Las matemáticas son importantes en la programación?
Formalmente, tomemos lenguajes regulares sobre {0,1}, y escojamos cualquier codificación particular de autómatas finitos deterministas con el alfabeto de entrada {0,1} en cadenas sobre {0,1}. Sea c (A) el código del autómata A. Ahora, el idioma universal para este conjunto de idiomas sería el idioma.
[matemáticas] U = \ {c (A) #w \ mid w \ en L (A) \} [/ matemáticas]
Se puede demostrar que este lenguaje no es regular. Una posibilidad de cómo hacerlo es, de hecho, utilizando el teorema de Myhill-Nerode. Necesitamos demostrar que la relación de equivalencia de Myhill-Nerode determinada por el lenguaje U tiene infinitas clases de equivalencia. Esto se puede hacer de la siguiente manera: seleccione infinitos DFA A_i de modo que ninguno de ellos reconozca el mismo idioma. Entonces ninguna de las palabras “c (A_i) #” es equivalente (porque para dos autómatas hay una palabra aceptada por uno pero no por el otro).
