37
$\begingroup$

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\{\; x\in\{a,b\}^* \mid \#_a(x)+2\#_b(x) \equiv 0 \mod 5 \;\}$ has the structure of $K_5$, the complete graph on five nodes. Yuval has shown a similar structure for a related language.

dfa for #a+2#b = 0, mod 5

My question is the following: how do we show that every finite state automaton for this language is non-planar? With Myhill-Nerode like characterizations it probably can be established that the structure of the language is present in the diagram, but how do we make this precise?

And if that can be done, is there a characterization of "planar regular languages"?

Improve this question
$\endgroup$
1
  • $\begingroup$ Also, the problem of deciding whether a regular language can be recognized by a planar DFA seems hard. Its decidability is open, and it has links with open problems in graph theory. $\endgroup$
    – Denis
    Commented Sep 24, 2019 at 9:12

2 Answers 2

Reset to default
37
+100
$\begingroup$

It isn't true that every DFA for this language is non-planar:

Counterexamplediagram of the example

Here is a language that is truly non-planar: $$ \left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}. $$ Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six distinct outgoing edges, which contradicts the known fact that every planar graph has a vertex of degree at most five.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In case someone was wondering like me, the 10 states of the DFA in the illustrations can be $q_{p,r}$ for $p=0,1$ and $r=0,1,2,3,4$, where $q_{p,r}$ stands for words $x$ such that $\#_a(x)\equiv p \pmod 2$ and $\#_a(x)+2\#_b(x) \equiv r \pmod 5$. $\endgroup$
    – John L.
    Commented May 13, 2021 at 13:51
29
$\begingroup$

The concept has been researched before. (Once you know the answer, google for it ...)

First there is old work by Book and Chandra, with the following abstract.

Summary. It is shown that for every finite-state automaton there exists an equivalent nondeterministic automaton with a planar state graph. However there exist finite-state automata with no equivalent deterministic automaton with a planar state graph.

The example and argumentation given is exactly the one by Yuval in his answer!

Moreover they also consider the binary alphabet.

There is a 35-state inherently nonplanar deterministic automaton over a 2-letter alphabet.

This work is continued rather recently by Bonfante and Deloup. They consider topological embeddings. Informally the genus of a graph is the number of holes that have to be added to embed the graph a surface without crossing edges. Graphs with genus zero are planar. Then the genus of a language is the minimal genus of the automata for the language.

Theorem 9 (Genus-Based Hierarchy). There are regular languages of arbitrarily large genus.

In the section "State-minimal automata versus genus-minimal automata" one finds the result, the proof of which is the first example given by Yuval (ten states to make the five state K5 language planar).

Proposition 7. There are deterministic automata with a genus strictly lower than the genus of their corresponding minimal automaton.

G.Bonfante, F.Deloup: The genus of regular languages, Mathematical Structures in Computer Science, 2018. doi 10.1017/S0960129516000037. Also ArXiv 1301.4981 (2013)

R.V. Book, A. K. Chandra, Inherently Nonplanar Automata, Acta informatica 6 (1976) doi 10.1007/BF00263745

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.