Os idiomas decidíveis são fechados nas seguintes operações:
1. União: Se L1 e L2 são idiomas decidíveis, L1 ∪ L2 também será decidível.
*
Explicação: Podemos construir uma máquina de Turing (TM) que decide L1 ∪ L2. A TM, na entrada 'W', simula o TMS para L1 e L2 em sequência.
* Primeiro, simule o TM para L1. Se aceitar, aceite 'W'.
* Se a TM para L1 rejeitar, simule a TM para L2. Se aceitar, aceite 'W'.
* Se o TM para L2 rejeitar, rejeite 'W'.
*
Ponto de chave: Como L1 e L2 são decidíveis, seus respectivos TMs * sempre * param (aceitando ou rejeitando). Isso garante que nossa TM decida sindical também sempre pare.
2. Interseção: Se L1 e L2 são idiomas decidíveis, L1 ∩ L2 também será decidível.
*
Explicação: Semelhante à união, podemos construir uma MT que decide L1 ∩ L2.
* Simule o TM para L1. Se rejeitar, rejeite 'W'.
* Se o TM para L1 aceitar, simule a tm para L2. Se aceitar, aceite 'W'.
* Se o TM para L2 rejeitar, rejeite 'W'.
3. Complemento: Se L é uma linguagem decidível, então L '(o complemento de L) também é decidível.
*
Explicação: Podemos construir uma tm para L 'simplesmente trocando os estados aceitados e rejeitados da MT que decide L.
* Dado o TM para L, crie uma nova TM que seja idêntica, exceto:se a TM original aceitar, o novo TM rejeita. Se a TM original rejeitar, a nova TM aceitar.
* aspecto crucial: Isso funciona * apenas * porque a TM original é uma decisão e sempre parte. Se a TM original pudesse fazer um loop, essa operação não resultaria em uma decisão para o complemento.
4. Concatenação: Se L1 e L2 forem idiomas decidíveis, também é decidível L1L2 (a concatenação de L1 e L2).
*
Explicação: * Na entrada `W`, tente todas as maneiras possíveis de dividir` w` em duas partes, `x` e` y`, tal que `w =xy`.
* Para cada divisão, simule o TM para L1 em `x` e o TM para L2 em` y`.
* Se o TM para L1 aceitar `x` * e * o TM para L2 aceita` y`, então aceite `W`.
* Se todas as divisões possíveis foram tentadas e nenhuma satisfaz a condição acima, rejeite `W`.
*
Importante: Como L1 e L2 são decidíveis, essas simulações sempre param. Como tentamos todas as divisões possíveis, a MT geral também sempre interrompe.
5. Kleene Star: Se L é uma linguagem decidível, também é decidível L* (a estrela de Kleene de L).
*
Explicação: Isso é semelhante à concatenação, mas permitimos várias concatenações (incluindo zero).
* Na entrada `w`, para` i =0` para `| w |`:(onde `| w |` é o comprimento de `w`)
* Experimente todas as maneiras possíveis de dividir `W` em` i` partes, `x1, x2, ..., xi`, tal que` w =x1x2 ... xi`.
* Para cada divisão, simule o TM para L em cada `xj`.
* Se o tm para L aceitar cada `xj` (para todos` j` de 1 a `i`), aceite` w`.
* Se todos os valores possíveis de `i` e todas as divisões possíveis foram tentadas e nenhum satisfaz a condição acima, rejeite 'W'.
*
Insight de chave: Como o comprimento de qualquer corda em L* não pode ser maior que o comprimento da entrada `W`, podemos limitar o número de divisões que precisamos tentar. A simulação é interrompida depois de considerar todas as divisões possíveis.
6. Reversão: Se L é uma linguagem decidível, então eu r
(A reversão de L) também é decidível.
*
Explicação: Construa uma MT que faça o seguinte:
* Reverta a string de entrada `w` para obter` w
r
`.
* Simule a tm para l em `w
r
`.
* Se a tm para l aceitar `w
r
`, então aceite` w`. Caso contrário, rejeite `w`.
7. Diferença: Se L1 e L2 são idiomas decidíveis, L1 - L2 também será decidível. (L1 - L2 contém todas as cordas em L1 que * não * em L2).
*
Explicação: L1 - L2 =L1 ∩ L2 '. Como os idiomas decidíveis são fechados sob complemento e interseção, eles também são fechados sob diferença.
8. Prefixo: Se L é uma linguagem decidível, então prefixo (l) ={x | Para alguns y, xy ∈ L} é decidível.
*
Explicação: * Na entrada `x`, para todos os` y` tais que `| xy | <=| x | + Some_constant`, (onde `algum_constant` é o comprimento máximo das seqüências para testar),
* Simule a tm para l em `xy`
* Se o TM aceitar, aceite `x`
* Rejeitar se nenhuma das simulações acima aceitar.
Por que o fechamento é importante? As propriedades de fechamento são fundamentais para entender o poder e as limitações das classes formais de idiomas. Saber que uma classe de idiomas é fechada sob determinadas operações nos permite:
*
Construa linguagens mais complexas: Podemos combinar idiomas decidíveis mais simples usando essas operações e ter certeza de que o idioma resultante também é decidível.
*
Prove Propriedades do idioma: As propriedades de fechamento podem ser usadas em provas indutivas para demonstrar que um determinado idioma pertence a uma classe específica.
*
Algoritmos de design: Os algoritmos que demonstram o fechamento servem como plantas para implementar analisadores e reconhecedores para idiomas complexos.
*
Entenda a hierarquia de decidabilidade: Eles ajudam a esclarecer a relação entre diferentes classes de idiomas (por exemplo, regular, livre de contexto, decidível, reconhecível por Turing).
Em resumo, as propriedades de fechamento das línguas decidíveis são uma pedra angular da teoria da computação. Eles demonstram que os idiomas decidíveis são uma classe de idiomas robustos e bem-comportados.
