As linguagens livres de contexto em fechadas sob complemento?

20

As linguagens sem contexto não são fechadas sob complemento, sabemos disso.

Tanto quanto eu entendo, linguagens sem contexto que são um subconjunto de para algumas letras estão fechadas no complemento (!?)aba,b

Aqui está o meu argumento. Cada linguagem CF tem uma imagem Parikh semi-linear . Conjuntos semilineares são fechados sob complemento. O conjunto de vetores que representam o conjunto semi-linear pode ser facilmente transformado em uma gramática linear.π ( L ) = { ( m , n ) a m b nL }Lπ(L)={(m,n)ambnL}

Questão. Existe uma referência facilmente acessível a esse fato?

Tecnicamente, esses idiomas são chamados de limitados , ou seja, um subconjunto de para algumas palavras . w 1 , , w kw1wkw1,,wk

Minha motivação para esta pergunta é de uma pergunta recente sobre a ausência de contexto de . Seu complemento dentro de parece mais fácil de manusear.um * b *{anbmn2m}ab

Hendrik Jan
fonte
Você verificou "A teoria matemática das línguas livres de contexto", de Ginsburg? Aparentemente, o Teorema 5.4.2 fornece a caracterização de linguagens limitadas sem contexto a que você está se referindo, e aposto que Ginsburg mencionaria a implicação para complementar as linguagens limitadas sem contexto (no caso bidimensional).
perfil completo de Yuval Filmus

Respostas:

12

Essa caracterização de linguagens livres de contexto delimitadas é devida a Ginsburg ("A teoria matemática das linguagens livres de contexto") e aparece como Corolário 5.3.1 em seu livro. Para geral, existem algumas restrições nos conjuntos semilineares, mas para essas restrições são sempre satisfeitas e, portanto, é fácil deduzir que o complemento dessa linguagem (dentro de ) é contextualizado. livre.k 2 w 1 w 2kk2w1w2

Ginsburg menciona essas implicações em seu livro.

Corolário 5.6.1 Se e são [sem contexto], e palavras, então é um idioma [sem contexto]. M 2 w 1 w 2 M 1M 2M1w1w2M2w1w2M1M2

Corolário 5.6.2 Se e são [sem contexto], e palavras, então e são idiomas [sem contexto]. M 2 w 1 w 2 M 1 - M 2 M 2 - M 1M1w1w2M2w1w2M1M2M2M1

Yuval Filmus
fonte
2

Outra prova usa a seguinte caracterização comprovada nesta resposta :

A linguagem é livre de contexto se for definível na aritmética de Presburger.A{aibj:(i,j)A}A

Claramente é definível na aritmética do Presburger se for definível na aritmética do Presburger.¯ AAA¯

Isso mostra que se os idiomas são livres de contexto, todas as expressões booleanas nos idiomas (envolvendo união, interseção e complementação) também são livres de contexto.Liab

Yuval Filmus
fonte