¿Qué es el complemento de los lenguajes sin contexto?

Necesito saber bajo qué clase de CFL está cerrada, es decir, qué conjunto es complemento de CFL. Sé que CFL no está cerrado bajo complemento, y sé que P está cerrado bajo complemento. Dado que CFL PI puede decir que el complemento de CFL está incluido en P (¿verdad?). Todavía existe la duda de si el complemento de CFL es un subconjunto apropiado de P o de todo P. Agradecería cualquier idea sobre cómo mostrar que el complemento de CFL es todo P (si ese es el caso, por supuesto). $\subsetneq$

complexity-theory formal-languages context-free closure-properties sets usuario432
fuente

Iba a publicar esto como respuesta, pero no responde a toda su pregunta: el complemento de cualquier CFL es R (recursivo), ya que los lenguajes recursivos están cerrados bajo el complemento y todas las CFL son R.

Eric

El hecho de que CFL no se cierre con complementación no significa que una 'L' en CFL significa que su complemento no está en CFL. Simplemente significa que existe una 'L' en CFL, de modo que su complemento no está en CFL

SHREYANSHU THAKUR

@Eric El autor de la pregunta ya sabe que el complemento de cualquier CFL es recursivo. Han hecho la gran declaración más fuerte que el complemento de cualquiera de CFL está en P .

David Richerby

Respuestas:

Uno puede entender su pregunta de dos maneras, de acuerdo con la definición de "el complemento de CFL".

caso A: El complemento de CFL es la clase de todos los idiomas que no están en CFL. Formalmente, En ese caso, es mucho más grande que , incluso tiene lenguajes que no están en , etc. Pero tal vez eso no sea lo que quisiste decir.

\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$

caso B: defina la clase de complemento-CFL como en palabras, el conjunto de todos los idiomas , de modo que el complemento de esté libre 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$

En ese caso, lo que escribió tiene sentido: (por el algoritmo CYK ), y también (ejecute el mismo algoritmo, genere la respuesta opuesta), y desde , entonces debería ser inmediato que , ¿verdad? $CFL \subsetneq P$ $co{CFL} \subseteq P$ $CFL \neq co{CFL}$ $co{CFL}\subsetneq P$

Sonó.
fuente

definición de CFK hasta donde yo entiendo: el lenguaje L está en coCFK si y solo si el complemento de L está en CFK. Por complemento de L me refiero a todas las cadenas posibles, excepto las cadenas en L. El problema que creo es que el complemento no se puede definir como "ejecutar el mismo algoritmo e invertir la respuesta" Por ejemplo: L = (x ^ iy ^ iz ^ i) no es CFL, pero no sé qué algoritmo puedo ejecutar para obtener la respuesta (negativa).

user432

entonces se está refiriendo al caso B. Tenga en cuenta que el complemento de un CFL podría no ser CFL, pero eso no significa que el algoritmo CYK no funcione de la misma manera. Quiero decir, ejecutamos el CYK en , que es CFL, y obtener una respuesta para cada si es o no se encuentra en . lo opuesto a eso es la respuesta a la pregunta de si está en o no , aunque no sea 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, ¿es tu notación estándar aquí? Esperaría y la clase de idiomas tal 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

En realidad, déjame cambiar la notación según tu sugerencia, tendrá más sentido.

Ran G.

Una clase robusta que contiene CFL y coCFL es LOGCFL , que contiene todos los idiomas reducibles en espacio de registro a un lenguaje sin contexto. Esta clase es intermedia entre NL y AC1, y tiene algunos problemas naturales completos. También se puede definir en términos de circuitos AC1 restringidos. LOGCFL se cierra bajo complemento (esta es una extensión del argumento utilizado para mostrar que NL = coNL).

Yuval Filmus
fuente

-1

El complemento de CFL podría ser CFL, pero no necesariamente lo es. El complemento de CFL es tanto recursivo (R) como recursivamente enumerable (RE). ¿Por qué? Todas las CFL son R y RE. Los lenguajes R están cerrados bajo complemento (pero RE no). En ese contexto, el complemento de CFL es R, que es inherentemente RE.

loyola
fuente

El autor de la pregunta ya ha dicho que saben que el complemento de cualquiera PPC está en P . Esa es una declaración mucho más fuerte que que es recursiva o RE. Es como si el autor de la pregunta mencionara a una persona que no puede caminar y usted haya respondido con una prueba de que no puede correr a la velocidad del sonido.

David Richerby