1. Unión: Si L1 y L2 son idiomas decidibles, entonces L1 ∪ L2 también es decidible.
* Explicación: Podemos construir una máquina Turing (TM) que decida L1 ∪ L2. El TM, en la entrada 'W', simula el TMS para L1 y L2 en secuencia.
* Primero, simule el TM para L1. Si acepta, entonces acepte 'W'.
* Si el TM para L1 rechaza, simule el TM para L2. Si acepta, entonces acepte 'W'.
* Si el TM para L2 rechaza, entonces rechace 'W'.
* Punto clave: Dado que L1 y L2 son decidibles, sus respectivos TMS * siempre * se detienen (aceptando o rechazando). Esto asegura que nuestro TM de decisión de la Unión también siempre se detenga.
2. Intersección: Si L1 y L2 son idiomas decidibles, entonces L1 ∩ L2 también es decidible.
* Explicación: Similar a la Unión, podemos construir un TM que decida L1 ∩ L2.
* Simule el TM para L1. Si rechaza, entonces rechace 'W'.
* Si el TM para L1 acepta, entonces simule el TM para L2. Si acepta, entonces acepte 'W'.
* Si el TM para L2 rechaza, entonces rechace 'W'.
3. Complemento: Si L es un lenguaje decidible, entonces L '(el complemento de L) también es decidible.
* Explicación: Podemos construir un TM para L 'simplemente intercambiando los estados de aceptación y rechazo de la TM que decide L.
* Dado el TM para L, cree un nuevo TM que sea idéntico, excepto:si el TM original acepta, el nuevo TM rechaza. Si el TM original rechaza, el nuevo TM acepta.
* aspecto crucial: Esto funciona * solo * porque el TM original es un decisivo y siempre se detiene. Si el TM original podría recorrer, esta operación no daría como resultado un decisivo para el complemento.
4. Concatenación: Si L1 y L2 son idiomas decidibles, entonces L1L2 (la concatenación de L1 y L2) también es decidible.
* Explicación:
* En la entrada `W`, intente todas las formas posibles de dividir` W` en dos partes, `x` y` y`, tal que `w =xy`.
* Para cada división, simule el TM para L1 en `X` y el TM para L2 en` Y`.
* Si el TM para L1 acepta `x` * y * el TM para L2 acepta` y`, entonces acepte `W`.
* Si todas las divisiones posibles se han probado y ninguna satisface la condición anterior, entonces rechace 'W'.
* IMPORTANTE: Dado que L1 y L2 son decidibles, estas simulaciones siempre se detienen. Debido a que intentamos todas las divisiones posibles, el TM general también siempre se detiene.
5. Kleene Star: Si L es un lenguaje decidible, entonces L* (la estrella Kleene de L) también es decidible.
* Explicación: Esto es similar a la concatenación, pero permitimos múltiples concatenaciones (incluida cero).
* En entrada `W`, para` i =0` a `| w |`:(donde `| w |` es la longitud de 'W`)
* Intente todas las formas posibles de dividir `W` en` I` partes, `x1, x2, ..., xi`, tal que` w =x1x2 ... xi`.
* Para cada división, simule el TM para L en cada `xj`.
* Si el TM para L acepta cada `xj` (para todos` j` de 1 a `i`), entonces acepte` W`.
* Si todos los valores posibles de `I` y todas las divisiones posibles se han probado y ninguna satisface la condición anterior, entonces rechace 'W'.
* Insight clave: Dado que la longitud de cualquier cadena en L* no puede ser mayor que la longitud de la entrada `W`, podemos limitar el número de divisiones que debemos probar. La simulación se detiene después de considerar todas las divisiones posibles.
6. Reversión: Si L es un lenguaje decidible, entonces l
* Explicación: Construya un TM que haga lo siguiente:
* Invertir la cadena de entrada `W` para obtener` w
* Simule el TM para L en `w
* Si el TM para L acepta `w
7. Diferencia: Si L1 y L2 son idiomas decidibles, entonces L1 - L2 también es decidible. (L1 - L2 contiene todas las cadenas en L1 que * no * en L2).
* Explicación: L1 - L2 =L1 ∩ L2 '. Dado que los idiomas decidibles están cerrados bajo el complemento y la intersección, también están cerrados bajo diferencia.
8. Prefijo: Si L es un lenguaje decidible, entonces prefijo (l) ={x | Para algunos y, xy ∈ L} es decidible.
* Explicación:
* En entrada `x`, para todas las posibles` y` tal que `| xy | <=| x | + some_constant`, (donde `some_constant` es la longitud máxima de las cadenas para probar),
* Simule el TM para L en `xy`
* Si el TM acepta, acepta `X`
* Rechazar si ninguna de las simulaciones anteriores acepta.
¿Por qué es importante el cierre?
Las propiedades de cierre son fundamentales para comprender el poder y las limitaciones de las clases de idiomas formales. Saber que una clase de idiomas está cerrada bajo ciertas operaciones nos permite:
* Construya idiomas más complejos: Podemos combinar lenguajes decidibles más simples utilizando estas operaciones y estar seguros de que el lenguaje resultante también es decidible.
* Probar propiedades del lenguaje: Las propiedades de cierre se pueden usar en pruebas inductivas para demostrar que un lenguaje determinado pertenece a una clase específica.
* Algoritmos de diseño: Los algoritmos que demuestran el cierre sirven como planos para implementar analizadores y reconocedores para idiomas complejos.
* Comprender la jerarquía de decidabilidad: Ayudan a aclarar la relación entre las diferentes clases de idiomas (por ejemplo, regular, sin contexto, decidible, reconocible).
En resumen, las propiedades de cierre de los idiomas decidibles son una piedra angular de la teoría de la computabilidad. Demuestran que los idiomas decidibles son una clase de idiomas robustas y bienestares.