В моем классе студент спросил, можно ли нарисовать все конечные автоматы без пересекающихся граней (кажется, все мои примеры это делали). Конечно, ответ отрицательный, очевидный автомат для языка имеет структуру , полный граф на пяти узлах , Юваль показал похожую структуру для родственного языка.
Мой вопрос заключается в следующем: как нам показать, что каждый конечный автомат для этого языка неплоский? С помощью характеристик, подобных Myhill-Nerode, вероятно, можно установить, что структура языка представлена на диаграмме, но как мы это уточним?
И если это можно сделать, есть ли характеристика «плоских регулярных языков»?
regular-languages
finite-automata
planar-graphs
Хендрик Ян
источник
источник
Ответы:
Это не правда, что каждый DFA для этого языка неплоский:
Вот язык, который действительно неплоский:{ x ∈ { σ1, … , Σ6}*|||Σя = 16я #σя( х ) ≡ 0(мод7 ) } .
Возьми любую планарную FSA для этого языка. Если мы удалим все недостижимые состояния, мы все равно получим планарный граф. Каждое достижимое состояние имеет шесть различных исходящих ребер, что противоречит известному факту, что каждый плоский граф имеет вершину степени не более пяти.
источник
Концепция была исследована ранее. (Как только вы знаете ответ, Google для этого ...)
Во-первых, это старая работа Книги и Чандры со следующим резюме.
Приведенный пример и аргументация - именно тот, который Ювал в своем ответе!
Кроме того, они также считают двоичный алфавит.
Эту работу продолжают сравнительно недавно Бонфанте и Делуп. Они рассматривают топологические вложения. Неформально род графа - это число отверстий, которые нужно добавить, чтобы внедрить граф в поверхность без пересечения ребер. Графики с нулевым родом плоские. Тогда род языка является минимальным родом автоматов для языка.
В разделе «Автоматы с минимальным состоянием по сравнению с автоматами с минимальным родом» вы найдете результат, доказательством которого является первый пример, приведенный Ювалом (десять штатов, делающих план языка K5 с пятью состояниями).
G.Bonfante, F.Deloup: Род регулярных языков, Математические структуры в информатике, 2018. doi 10.1017 / S0960129516000037 . Также ArXiv 1301.4981 (2013)
Р. В. Книга, А. К. Чандра, Непланарные автоматы по своей природе, Acta informatica 6 (1976) doi 10.1007 / BF00263745
источник