Como provar que linguagens sensíveis ao contexto são fechadas sob interseção e complemento?

Esta é uma pergunta do exame do nosso curso "Autômatos e línguas formais". Há uma pergunta em que é solicitado que prove ou refute que qualquer operação de "complemento relativo" entre duas linguagens sensíveis ao contexto também produzirá uma linguagem sensível ao contexto.

Das propriedades de fechamento sensíveis ao contexto Wikipedia e princeton.edu . Eu sei que esses idiomas estão fechados sob interseção e complemento.

Passei muito tempo encontrando a prova formal dessas declarações. Onde / como posso encontrar as provas? Ou como prová-los sozinho? Alguém pode me indicar uma referência? Alguém pode postar aqui as provas?

formal-languages closure-properties context-sensitive arty
fonte

Sua pergunta não é específica o suficiente para este site. Conte-nos o que você tentou e onde ficou preso. O objetivo da educação é aprender a resolver problemas, não como fazer outras pessoas resolverem seus problemas.

Reinierpost

Eu não acho que você esteja certo, minha pergunta é muito rigorosa. Observei que não consigo encontrar uma referência que comprove algumas das propriedades de fechamento do LCS. Eu não pedi para resolver a pergunta original desde que eu postei a solução também ...

arty

Acho que você pode estar certo de que a pergunta exata não está sendo respondida lá.

Reinierpost

Respostas:

A primeira propriedade de fechamento, fechamento sob interseção, é uma prova de bricolage se você escolher o modelo certo para as linguagens sensíveis ao contexto. Ao defini-los com a ajuda de autômatos com limites lineares, é possível executar dois desses autômatos sucessivamente para testar (não-deterministicamente) a aceitação da interseção.

Segundo, o fechamento sob complemento é difícil! Costumava ser um famoso problema aberto até ser resolvido de forma independente por Immerman e Szelepcsényi. É uma prova bastante surpreendente de como provar o complemento de um autômato não determinístico. A técnica é chamada contagem indutiva e funciona para famílias maiores de classes de complexidade: NSPACE ( $s(n)$ ) = co-NSPACE ( $s(n)$ ), onde sensível ao contexto é igual a espaço não determinístico linear .

Hendrik Jan
fonte

Muito obrigado, agora, quando tenho essa referência, procurarei livros. você pode explicar o que você quer dizer com "modelo certo para as linguagens sensíveis ao contexto" para fazer você mesmo uma prova?

arty

@arty Como você sabe, a CSL pode ser definida usando gramáticas sensíveis ao contexto ou autômatos limitados lineares. Para algumas tarefas, a escolha do modelo é crucial. Eu gosto do LBA porque eles são fáceis de "programar".

Hendrik Jan

@ Jan simplesmente não tinha certeza do significado da palavra "modelo" - agora entendo que é o modelo de representação da CSL. apenas para informá-lo, não há outro lugar na web quando essas informações estão disponíveis. Eu acho que sua entrada vai ajudar um monte de estudantes de ciência da computação e pós-graduados (como eu) que gostariam de obter algum conhecimento extra

arty