O que é complemento de idiomas sem contexto?

11

Eu preciso saber em que classe de CFL está fechada, ou seja, qual conjunto é o complemento de CFL. Eu sei que o CFL não está fechado no complemento e sei que P está fechado no complemento. Como CFL PI pode dizer que o complemento de CFL está incluído em P (certo?). Ainda há uma questão de saber se o complemento de CFL é um subconjunto adequado de P ou o P. inteiro. Eu apreciaria alguma idéia de como mostrar que o complemento de CFL é o P inteiro (se esse for o caso, é claro).

user432
fonte
2
Eu ia postar isso como uma resposta, mas ela não responde a toda a sua pergunta: o complemento de qualquer CFL é R (recursivo), pois os idiomas recursivos são fechados sob complemento e todas as CFLs são R.
Eric
A CFL não ser fechada sob complementação não significa que um 'L' estar na CFL significa que o complemento não está na CFL. Significa apenas que existe um 'L' na CFL tal que o complemento não está na CFL
SHREYANSHU THAKUR
@ Eric O solicitante já sabe que o complemento de qualquer CFL é recursivo. Eles fizeram o muito declaração mais forte que o complemento de qualquer CFL está em P .
David Richerby

Respostas:

17

Pode-se entender sua pergunta de duas maneiras, de acordo com a definição de "o complemento da CFL".

caso A: Complemento de CFL é a classe de todos os idiomas que não estão em CFL. Formalmente, Nesse caso, é muito maior que , ele ainda possui idiomas que não estão em etc. etc. Mas talvez não seja isso que você quis dizer.¯ C F L PR

CFL¯={LLCFL}.
CFL¯PR

case B: Defina a classe complemento-CFL como em palavras, o conjunto de todos os idiomas , de modo que o complemento de seja livre de contexto .L L

coCFL={L¯LCFL},
LL

Nesse caso, o que você escreveu faz sentido: (pelo algoritmo CYK ) e também (execute o mesmo algoritmo, produza a resposta oposta) e desde , então deve ser imediato que , certo?c o C F LP C F L c o C F L c o C F LPCFLPcoCFLPCFLcoCFLcoCFLP

Tocou.
fonte
definição de CFK, tanto quanto eu a entendo: a linguagem L está no coCFK se e somente se o complemento de L estiver no CFK. Por complemento de LI, todas as seqüências possíveis, exceto as de L. O problema que penso é que o complemento não pode ser definido como "execute o mesmo algoritmo e inverta a resposta". Por exemplo: L = (x ^ iy ^ iz ^ i) não é CFL, mas não sei qual algoritmo posso executar para obter a resposta (negativa).
user432
11
portanto, você está se referindo ao caso B. Observe que o complemento de uma CFL pode não ser CFL, mas isso não significa que o algoritmo CYK não funcione da mesma maneira. Quero dizer, executamos a CYK em , que é CFL, e obter uma resposta para cada ou não está em . o oposto disso é a resposta para a pergunta se está ou não em , mesmo que possa ser não CFL. ¯ L x ¯ L x L LLL¯xL¯xLL
Ran G.
11
@ user432 ! coCFLCFL¯
Raphael
11
@RanG é o seu padrão de notação aqui? Eu esperaria que e a classe de idiomas modo que . ¯ C F L = LcoCFL={L:L¯CFL}CFL¯=LLCFL
usul
11
Na verdade, deixe-me mudar a notação de acordo com a sua sugestão, isso fará mais sentido.
Ran G.
3

Uma classe robusta que contém CFL e coCFL é LOGCFL , que contém todos os idiomas que podem ser reduzidos em espaço de log para um idioma sem contexto. Essa classe é intermediária entre NL e AC1 e tem alguns problemas completos naturais. Também pode ser definido em termos de circuitos AC1 restritos. LOGCFL é fechado sob complemento (esta é uma extensão do argumento usado para mostrar que NL = coNL).

Yuval Filmus
fonte
-1

Complemento de CFL poderia ser CFL, mas não necessariamente é. O complemento de CFL é recursivo (R) e recursivamente enumerável (RE). Por quê? Todas as CFLs são R e RE. As línguas R são fechadas sob complemento (mas RE não). Nesse contexto, o complemento de CFL é R, que é inerentemente ER.

loyola
fonte
O autor da questão já disse que eles sabem que o complemento de qualquer PCP está em P . Essa é uma afirmação muito mais forte do que ser recursiva ou ER. É como se o autor da pergunta tivesse mencionado uma pessoa que não pode andar e você respondeu com uma prova de que ela não pode correr na velocidade do som.
David Richerby