Construya un PDA para el complemento de

Me pregunto si esto es posible, ya que $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$ . Por lo tanto, un PDA que puede distinguir una palabra del resto de podría aceptarla , lo que me parece contradictorio. $w\in\{a^n b^n c^n \mid n \geq 0\}$ $\{a^*b^*c^*\}$

Supongo que necesito aprovechar la naturaleza no determinista de los PDA, pero no tengo ideas. Si pudiera ofrecer algún consejo, lo agradecería mucho.

formal-languages automata context-free pushdown-automata Hauptbenutzer
fuente

Punto interesante al respecto que parece contradictorio. De hecho, los lenguajes sin contexto no se cierran tomando el complemento ... por lo que hay muchos ejemplos de lenguajes sin contexto que podrían ser "aceptados" en el sentido al que alude. No soy un teórico y, como tal, realmente no puedo conciliar esto, pero tal vez alguien más pueda intervenir sobre por qué esto no es algo de qué preocuparse.

Patrick87

Tenga en cuenta que esto generaliza: el complemento de es un CFG.

{a^{n} b^{n} c^{n} d^{n} e^{n}}

$\{a^n b^n c^n d^n e^n\}$

sdcvvc

Pregunta similar .

Raphael

Respuestas:

No, esto no tiene contexto. Para aceptar $a^nb^nc^n$ , debe asegurarse de que tres números sean iguales. Para aceptar $a^*b^*c^* \setminus a^nb^nc^n$ , solo necesita asegurarse de estar en uno de los siguientes tres casos:

El número de $a$ s es diferente del número de $b$ s; o
El número de s es diferente del número de $a$ $c$ s; o
El número de s es diferente del número de $b$ $c$ s.

Escriba un PDA para cada uno de estos casos, luego combínelos saltando de manera no determinista a cada uno desde el estado inicial.

Patrick87
fuente

Había escrito bien estos casos, pero me faltaba la idea de conectarlos. ¡Gracias!

hauptbenutzer

En realidad solo necesitas dos casos.

sdcvvc

@sdcvvc Buen punto. :)

Patrick87

Para diferentes números de caracteres, considere esto como inspiración:

. Debería ser simple pegar

a la izquierda de esto o

a la derecha y convertir esto en un PDA. Para el caso complicado (que no necesita)

S \to x S y | X | Y; X \to x | x X; Y \to y | y Y

$S → xSy | X | Y ; X → x | xX ; Y → y | yY$

a^{+}

$a^+$

c^{+}

$c^+$

S \to a S c | A | C; A \to a B | a A; C \to B c | C c; B \to ε | b B

Jonas Kölker