Construa um PDA para o complemento de

Gostaria de saber se isso é possível, já que . Portanto, um PDA que pode distinguir uma palavra do resto de pode aceitá-la , o que me parece contraditório. $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$ $w\in\{a^n b^n c^n \mid n \geq 0\}$ $\{a^*b^*c^*\}$

Acho que preciso tirar proveito da natureza não determinística dos PDAs, mas estou sem ideias. Se você pudesse oferecer alguns conselhos, eu agradeceria muito.

formal-languages automata context-free pushdown-automata hauptbenutzer
fonte

Ponto interessante sobre isso parecer contraditório. De fato, as linguagens sem contexto não são fechadas ao aceitar o complemento ... portanto, existem muitos exemplos de linguagens sem contexto que podem ser "aceitas" no sentido em que você alude. Eu não sou um teórico e, como tal, não consigo conciliar isso de verdade, mas talvez alguém possa conversar sobre por que isso não é algo para se preocupar?

precisa saber é o seguinte

Observe que isso generaliza: o complemento de é um CFG.

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

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

Sdcvvc

Pergunta semelhante .

Raphael

Respostas:

Não, isso é livre de contexto. Para aceitar $a^nb^nc^n$ , você precisa garantir que três números sejam iguais. Para aceitar $a^*b^*c^* \setminus a^nb^nc^n$ , você só precisa ter certeza de que você está em um dos três casos seguintes:

O número de s é diferente do número de s; ou $a$ $b$
O número de s é diferente do número de s; ou $a$ $c$
O número de s é diferente do número de s. $b$ $c$

Escreva um PDA para cada um desses casos e, em seguida, combine-os saltando não-deterministicamente para cada um a partir do estado inicial.

Patrick87
fonte

Eu escrevi esses casos, mas estava faltando a ideia de conectá-los. Obrigado!

hauptbenutzer

Na verdade, você precisa apenas de dois casos.

Sdcvvc

@sdcvvc Good point. :)

Patrick87

Para um número diferente de caracteres, considere isso como inspiração:

. Deve ser simples colar

à esquerda deste ou

à direita e transformá-lo em um PDA. Para o caso complicado (do qual você não precisa)

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 31/07