Skonstruuj PDA jako uzupełnienie

Zastanawiam się, czy to w ogóle możliwe, ponieważ . Dlatego PDA, który potrafi odróżnić słowo od reszty równie dobrze może je zaakceptować , co wydaje mi się sprzeczne. $\{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^*\}$

Chyba muszę skorzystać z niedeterministycznej natury palmtopów, ale brakuje mi pomysłów. Jeśli mógłbyś zaoferować jakąś radę, byłbym bardzo wdzięczny.

— hauptbenutzer
źródło

Ciekawe, że wydaje się to sprzeczne. Rzeczywiście, języki bezkontekstowe nie są zamknięte przy przyjmowaniu uzupełnienia ... więc istnieje wiele przykładów języków bezkontekstowych, które można „zaakceptować” w takim znaczeniu, w jakim się do nich odnosi. Nie jestem teoretykiem i jako taki nie mogę tak naprawdę pogodzić się z tym, ale może ktoś inny może się zastanowić, dlaczego nie ma się czym martwić?

— Patrick87,

Zauważ, że to się uogólnia: dopełnieniem jest CFG.

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

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

— sdcvvc

Podobne pytanie .

— Raphael

Nie, to jest pozbawione kontekstu. Aby zaakceptować , musisz upewnić się, że trzy liczby są równe. Aby zaakceptować , musisz tylko upewnić się, że jesteś w jednym z następujących trzech przypadków: $a^nb^nc^n$ $a^*b^*c^* \setminus a^nb^nc^n$

Ilość s jest różna od liczby S; lub $a$ $b$
Ilość s jest różna od liczby S; lub $a$ $c$
Liczba s jest różna od liczby s. $b$ $c$

Napisz PDA dla każdego z tych przypadków, a następnie połącz je, przeskakując niedeterministycznie do każdego ze stanu początkowego.

— Patrick87
źródło

Dobrze spisałem te sprawy, ale brakowało mi pomysłu ich połączenia. Dziękuję Ci!

— hauptbenutzer

Właściwie potrzebujesz tylko dwóch skrzynek.

— sdcvvc

@sdcvvc Dobra uwaga. :)

— Patrick87

W przypadku innej liczby znaków rozważ to jako inspirację: . Powinno być proste przyklejenie po lewej stronie tego lub po prawej stronie i przekształcenie go w PDA. W trudnym przypadku (którego nie potrzebujesz) .

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