Paso 1: prueba la definición. Un conjunto es regular si hay una expresión regular que lo describe. Vea si puede encontrar uno.
Paso 1a: Un conjunto puede describirse mediante una expresión regular si y solo si es el conjunto reconocido por algún autómata finito. Vea si puede encontrar uno. A veces, el autómata es más fácil que la expresión regular, a veces al revés. De aquí proviene la idea de “cantidad finita de memoria”: un autómata finito solo puede recordar una cantidad constante de datos y, por ejemplo, no puede realizar un seguimiento del número de a en una cadena que puede tener arbitrariamente muchos como. (Puede realizar un seguimiento del número de a hasta un número, digamos 200, pero si la cadena tiene más de 200 a solo puede recordar “más de 200”. Por supuesto, puede reemplazar 200 con el número que desee).
Paso 2: Si no puede probar que el idioma es regular, tal vez pueda probar que no lo es. El lema de Pumping para los lenguajes regulares proporciona una propiedad que debe tener cada lenguaje regular (si lo piensa, verá que esa propiedad proviene de la restricción de memoria finita: piense en p como la cantidad de memoria que su autómata finito puede manejar, y si necesita procesar una cadena más grande, tiene que tirar algunos datos, lo que significa que dará la misma respuesta en diferentes cadenas). Si puede probar que su idioma no tiene esta propiedad, entonces no es regular.
- ¿Cuál es tu fórmula matemática discreta favorita?
- ¿Qué tan eficientemente la computadora Quantum puede resolver el problema P vs NP?
- ¿Existe una función que crece más rápido que cualquier función computable, pero que crece a un ritmo fundamentalmente más lento que el de la función Busy Beaver?
- Criptografía: ¿Cómo describirías la diferencia entre la longitud de la contraseña y la longitud de la clave de una criptografía como AES?
- ¿La comunidad académica evita los intentos de resolver un problema NP-difícil en tiempo polinómico?
Paso 3: El lema de bombeo es solo de una manera: un lenguaje que tiene la propiedad que dice que aún puede no ser regular. Si no puede encontrar un autómata finito o una expresión regular para demostrar que su conjunto es regular, ni mostrar que no satisface la propiedad del lema de bombeo para demostrar que no lo es, intente algo como el teorema de Myhill – Nerode, que encontré navegando brevemente en Wikipedia Sin embargo, no tengo experiencia en el uso. Tenga en cuenta que esto nuevamente está estrechamente relacionado con autómatas finitos y memoria limitada.
