Я читаю " Объединение регулярных языков и сложность описания " Галины Йирасковой, 2009 г., о сложности состояний, возникающей в результате объединения двух регулярных языков (Галина Жираскова), но я не могу понять, каковы будут практические последствия сложности состояний , Первая тривиальная мысль, которая меня поразила, заключалась в том, что более высокая сложность потребует больше времени и места на машине. Это верно? Также есть ли другие места, где сложность состояния важна и значительна?
Редактировать: Сложность состояний обычного языка - это наименьшее количество состояний в любом детерминированном конечном автомате (dfa), принимающем язык. Недетерминированная сложность состояний регулярного языка определяется как наименьшее число состояний в любом недетерминированном конечном автомате (nfa) для языка.
Ответы:
Сложность состояния на самом деле заключается в кратком описании объекта (в данном случае обычного языка), а не в вычислительной сложности. Общая тема называется «описательная сложность» в литературе и частично основана на классической статье Мейера и Фишера 1971 года, озаглавленной «Экономика выражения с помощью автоматов, грамматик и формальных систем» (см. Http: // people). .csail.mit.edu / meyer / economy-of-description.pdf ). Это все еще активная область с ежегодной конференцией (DCFS - сложность описания формальных систем).
Что касается приложений, в любом месте, где ваша программа по существу полагается на конечный автомат (например, парсеры), было бы хорошо иметь этот конечный автомат как можно меньшим.
источник
Позвольте мне добавить конкретный пример к превосходному ответу Джеффри Шаллита.
Предположим, вы хотите создать словарь Scrabble (TM). Вы можете придумать несколько способов представления словаря, например, список слов, попытки (деревья букв) или детерминированные автоматы. Согласно [1], сведение к минимуму времени [= DFA] дает удивительную экономию пространства; количество узлов уменьшено с 117 150 до 19 853. Лексикон, представленный в виде необработанного списка слов, занимает около 780 Кбайт, в то время как наш dawg может быть представлен в 175 Кбайт.
Как видите, сложность состояния действительно имеет значение в этом случае, особенно если вы хотите написать эффективную программу, как это делали авторы.
[1] Аппель и Джекобсон Самая быстрая в мире программа по скрэбблу , сообщения ACM 31 , 572-578 (1988).
источник
Доказательство того, что можно решить, имеет ли произвольная детерминированная контекстно-свободная грамматика (или, что то же самое, детерминированный пуш-ап автомат) эквивалентный конечный автомат, описывающий тот же язык, по существу является доказательством сложности состояний конечных автоматов, описывающих детерминированные контекстно-свободные языки: оценка размера этих конечных автоматов в терминах детерминированных автоматов дает ограничения на длину процедуры принятия решения.
Подробности см. В статье « Регулярность и связанные с ней проблемы для детерминированных пуш-автоматов » Лесли Г. Валианта.
источник