O que é complemento de idiomas sem contexto?

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). $\subsetneq$

complexity-theory formal-languages context-free closure-properties sets user432
fonte

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:

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.

\bar{C F L} = {L ∣ L \notin C F L} .

$\overline{CFL} = \{ L \mid L\notin CFL\}.$

\bar{C F L}

$\overline{CFL}$

P

$P$

R

$R$

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 .

c o C F L = {\bar{L} ∣ L \in C F L},

$co{CFL} = \{ \bar{L} \mid L \in CFL\},$

L

$L$

L

$L$

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? $CFL \subsetneq P$ $co{CFL} \subseteq P$ $CFL \neq co{CFL}$ $co{CFL}\subsetneq P$

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

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

$L$

\bar{L}

$\overline L$

x

$x$

\bar{L}

$\overline L$

x

$x$

L

$L$

L

$L$

Ran G.

@ user432 !

coCFL \neq \bar{CFL}

$\text{coCFL} \neq \overline{\text{CFL}}$

Raphael

@RanG é o seu padrão de notação aqui? Eu esperaria que e a classe de idiomas modo que .

c o C F L = {L : \bar{L} \in C F L}

$coCFL = \{ L : \bar{L} \in CFL\}$

\bar{C F L} =

$\overline{CFL} =$

L

$L$

L \notin C F L

$L \not \in CFL$

usul

Na verdade, deixe-me mudar a notação de acordo com a sua sugestão, isso fará mais sentido.

Ran G.

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