Planar regular languagesalx32263.i:Y| 1mits Hhual
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.
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"?
1 Answer
It isn't true that every DFA for this language is non-planar:
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.
