Zwykłe języki planarne

32

W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę , kompletny wykres na pięciu węzłach . Yuval pokazał podobną strukturę dla pokrewnego języka. $\{\; x\in\{a,b\}^* \mid \#_a(x)+2\#_b(x) \equiv 0 \mod 5 \;\}$ $K_5$

Moje pytanie brzmi: w jaki sposób pokazujemy, że każdy automat skończony dla tego języka jest niepłaski? W przypadku charakterystyk podobnych do Myhill-Nerode prawdopodobnie można ustalić, że struktura języka jest obecna na schemacie, ale jak to zrobić?

A jeśli można to zrobić, czy istnieje charakterystyka „zwykłych języków planarnych”?

regular-languages finite-automata planar-graphs

— Hendrik Jan
źródło

Problem decydowania, czy zwykły język może zostać rozpoznany przez planarny DFA, wydaje się trudny. Jego rozstrzygalność jest otwarta i ma powiązania z otwartymi problemami w teorii grafów.

— Denis

29

Nie jest prawdą, że każdy DFA dla tego języka nie jest planarny:

Oto język, który jest naprawdę nieplanarny:

{x \in {σ_{1}, \dots, σ_{6}}^{*} | \sum_{ja = 1}^{6} ja #_{σ_{ja}} (x) \equiv 0 (\mod 7)} .

$\left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}.$

— Yuval Filmus
źródło

21

Ta koncepcja była wcześniej badana. (Gdy znasz odpowiedź, wyszukaj ją w Google ...)

Najpierw stara praca Booka i Chandry, z następującym streszczeniem.

Podsumowanie. Pokazano, że dla każdego automatu skończonego istnieje równoważny automat niedeterministyczny z płaskim wykresem stanu. Istnieją jednak automaty skończone bez równoważnego automatu deterministycznego z płaskim planem graficznym.

Podany przykład i argumentacja jest dokładnie taka, jak Yuval w swojej odpowiedzi!

Ponadto rozważają również binarny alfabet.

Istnieje 35-stanowy z natury nieplanarny automat deterministyczny nad 2-literowym alfabetem.

Praca ta jest kontynuowana dość niedawno przez Bonfante i Deloup. Rozważają osadzenia topologiczne. Nieformalnie rodzajem wykresu jest liczba otworów, które należy dodać, aby osadzić wykres na powierzchni bez przekraczania krawędzi. Wykresy z rodzajem zero są płaskie. Zatem rodzaj języka jest minimalnym rodzajem automatów dla danego języka.

Twierdzenie 9 (Hierarchia oparta na rodzaju). Istnieją regularne języki o dowolnie dużym rodzaju.

W sekcji „Automaty minimalne stanowe a automaty minimalne rodzajowe” można znaleźć wynik, czego dowodem jest pierwszy przykład podany przez Yuvala (dziesięć stanów, aby uczynić pięciostanowy język języka K5 planarnym).

Twierdzenie 7. Istnieją deterministyczne automaty z rodzajem ściśle niższym niż rodzaj odpowiadającego im automatu minimalnego.

G.Bonfante, F.Deloup: Rodzaj języków regularnych, Struktury matematyczne w informatyce, 2018. doi 10.1017 / S0960129516000037 . Również ArXiv 1301.4981 (2013)

RV Book, AK Chandra, Inherently Nonplanar Automata, Acta informatica 6 (1976) doi 10.1007 / BF00263745

— Hendrik Jan
źródło