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.

formal-languages automata context-free pushdown-automata 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

Odpowiedzi:

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