Я сходу не нашёл решения, может кто навскидку знает, куда копать?
Вкратце, ситуация следующая.
Допустим, у нас есть некоторая грамматика (G1), заданная через НКА.
Теперь у нас есть некоторая другая грамматика (G2), тоже заданная через НКА.
Если бы нас интересовала эквивалентность, то мы бы её проверили за полиномиальное время через минимизацию ДКА и их эквивалентность.
Но нас интересует нестрогая эквивалентность: L1>=L2. Т.е. предполагаем, что G2 описывает подъязык языка G1. Быть может, полный, а может быть, и нет.
Есть ли алгоритм, который это проверяет?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Я сходу не нашёл решения, может кто навскидку знает, куда копать? S>Вкратце, ситуация следующая. S>Допустим, у нас есть некоторая грамматика (G1), заданная через НКА. S>Теперь у нас есть некоторая другая грамматика (G2), тоже заданная через НКА. S>Если бы нас интересовала эквивалентность, то мы бы её проверили за полиномиальное время через минимизацию ДКА и их эквивалентность. S>Но нас интересует нестрогая эквивалентность: L1>=L2. Т.е. предполагаем, что G2 описывает подъязык языка G1. Быть может, полный, а может быть, и нет. S>Есть ли алгоритм, который это проверяет?
Copilot так ответил, насколько правильно не могу сказать, так как таких тонкостей в практике не касался, но вроде выглядит правдободобно:
Да, существует алгоритм для проверки того, является ли язык, описываемый одной грамматикой (G2), подъязыком языка, описываемого другой грамматикой (G1). Этот процесс можно выполнить с использованием автоматов следующим образом:
1. **Построение ДКА**: Преобразуйте оба недетерминированных конечных автомата (НКА) в детерминированные конечные автоматы (ДКА). Это можно сделать с помощью алгоритма детерминизации, который преобразует НКА в эквивалентный ДКА.
2. **Минимизация ДКА**: Минимизируйте оба ДКА, чтобы упростить дальнейшие операции. Минимизация ДКА позволяет получить эквивалентный автомат с минимальным числом состояний.
3. **Построение дополнения**: Постройте дополнение для ДКА, описывающего язык G2. Это делается путем инверсии принимающих и непринимающих состояний в ДКА G2.
4. **Пересечение языков**: Постройте пересечение ДКА, описывающего язык G1, и дополнения ДКА для языка G2. Это можно сделать с помощью построения произведения автоматов.
5. **Проверка пустоты**: Проверьте, является ли язык, описываемый пересечением, пустым. Если пересечение пусто, это означает, что язык G2 является подъязыком языка G1 (L1 >= L2).
Этот алгоритм позволяет проверить, является ли один язык подмножеством другого, используя операции над автоматами. Важно отметить, что все шаги, включая детерминизацию, минимизацию, построение дополнения и пересечение, могут быть выполнены за полиномиальное время относительно размера автоматов.
Q>3. **Построение дополнения**: Постройте дополнение для ДКА, описывающего язык G2. Это делается путем инверсии принимающих и непринимающих состояний в ДКА G2.
Вот я так и подумал, что это делается через операции над минимализированными ДКА. Но с наскоку не смог придумать, как проверить, что язык, реализуемый одним ДКА, является подмножеством языка другого ДКА.
Синклер, наверное, рассчитывал, что эта задача проще задачи проверки эквиавалентности ДКА. А оказывается, сложнее.
P.S.
О! Мысля родилась.
А что, если построить третий автомат, объединяющий первые два, и все три минимизировать? Тогда если третий, объединенный, автомат сведется к какому-то из двух исходных, то тот, к которому сведется, он то ли, как раз, искомый, то ли наоборот — это надо подумать. А если не сведется, то ответ точно отрицательный.
Здравствуйте, Pzz, Вы писали: Pzz>Синклер, наверное, рассчитывал, что эта задача проще задачи проверки эквиавалентности ДКА. А оказывается, сложнее.
Нет, не рассчитывал. У нас задача как раз такая, что нужно уметь сравнивать языки, и именно что на нестрогое неравенство.
Pzz>А что, если построить третий автомат, объединяющий первые два, и все три минимизировать? Тогда если третий, объединенный, автомат сведется к какому-то из двух исходных, то тот, к которому сведется, он то ли, как раз, искомый, то ли наоборот — это надо подумать. А если не сведется, то ответ точно отрицательный.
Ну, алгоритм, предложенный копилотом, выглядит на первый взгляд работоспособным.
Дальше надо смотреть — либо ваша идея изоморфна копилотовской с точностью до порядка действий, либо у одной из них будет более хорошая асимптотика/коэффициенты при О-оценках.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Ну, алгоритм, предложенный копилотом, выглядит на первый взгляд работоспособным. S>Дальше надо смотреть — либо ваша идея изоморфна копилотовской с точностью до порядка действий, либо у одной из них будет более хорошая асимптотика/коэффициенты при О-оценках.
У копилота, по-видимому, лучше коэффициенты (он экономит одну минимизацию ДКА), но то, что он предлагает ОЧЕНЬ сложно аккуратно написать.
А вот то, что предлагаю я, добавляет очень мало сложности, потому, что минимизацию ДКА и его нормализацию (чтобы свести возможные развороты графа к стандартному виду) писать в любом случае придется, а больше мне, вроде, ничего хитрого и не нужно.
Здравствуйте, Pzz, Вы писали: Pzz>А вот то, что предлагаю я, добавляет очень мало сложности, потому, что минимизацию ДКА и его нормализацию (чтобы свести возможные развороты графа к стандартному виду) писать в любом случае придется, а больше мне, вроде, ничего хитрого и не нужно.
Не очень понятно. Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Обе операции работают поверх произведения автоматов, отличаются только наборами терминальных/нетерминальных вершин.
Почему вы думаете, что ваш подход будет проще?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
Pzz>>А вот то, что предлагаю я, добавляет очень мало сложности, потому, что минимизацию ДКА и его нормализацию (чтобы свести возможные развороты графа к стандартному виду) писать в любом случае придется, а больше мне, вроде, ничего хитрого и не нужно. S>Не очень понятно. Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная). S>Обе операции работают поверх произведения автоматов, отличаются только наборами терминальных/нетерминальных вершин.
Я не очень понимаю, как строится инверсия автомата. Возможно, если бы я это знал, то имел бы другое мнение.
Объединение автоматов вроде как правда тривиальная операция (ну ОК, для тех, кто пробовал строить ДКА). Просто объединяем узлы и еще раз минимизируем.
Здравствуйте, Pzz, Вы писали:
Pzz>Я не очень понимаю, как строится инверсия автомата. Возможно, если бы я это знал, то имел бы другое мнение.
Инвертируются флаги терминальности у всех состояний. Автомат перестаёт принимать все слова, которые были в исходном автомате, и начинает принимать все остальные слова.
Pzz>Объединение автоматов вроде как правда тривиальная операция (ну ОК, для тех, кто пробовал строить ДКА). Просто объединяем узлы и еще раз минимизируем. https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D1%8F%D0%BC%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%94%D0%9A%D0%90#
Объединение, пересечение, и разность — одна и та же операция. Отличаются только флаги терминальности состояний.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Q>Copilot так ответил, насколько правильно не могу сказать, так как таких тонкостей в практике не касался, но вроде выглядит правдободобно:
Да, спасибо. Это — правильный ответ!
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
Pzz>>Я не очень понимаю, как строится инверсия автомата. Возможно, если бы я это знал, то имел бы другое мнение. S>Инвертируются флаги терминальности у всех состояний. Автомат перестаёт принимать все слова, которые были в исходном автомате, и начинает принимать все остальные слова.
А откуда при этом у бывших терминальных состояний берется таблица переходов?
Здравствуйте, Pzz, Вы писали:
Pzz>А откуда при этом у бывших терминальных состояний берется таблица переходов?
Оппа, не уехал мой ответ
У терминальных состояний есть таблица переходов. Из них все переходы ведут в ∅ — специальное нетерминальное состояние.
Оно вводится для того, чтобы в DFA из любого состояния по любому символу был переход. Запрещённые переходы мы и уводим в ∅. И из ∅ по любому символу мы остаёмся в ∅.
При построении инверсии DFA, ∅ становится терминальным состоянием.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Иногда нетривиальная.
(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти)
Там как раз выполняются эти же операции на каждом шаге — ищется разность мн-в. ))
Да, Копилот правильно описал нахождение разности мн-в, но неправильно описал алгоритм целиком, бгг...
Т.е. незачем разбивать этот алгоритм этапы, где одним из этапов будет построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.
Здравствуйте, vdimas, Вы писали: V>Иногда нетривиальная. V>(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти)
Нет. Такого не может быть. Инверсный автомат содержит ровно столько же состояний и столько же переходов, сколько основной (независимо от того, что вы понимаете под "инверсией").
Но вы можете убедить меня контрпримером.
V>https://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90
Какую из двух "стандартных" реализаций, упомянутых по ссылке, вы имеете в виду? V>Там как раз выполняются эти же операции на каждом шаге — ищется разность мн-в. ))
V>Да, Копилот правильно описал нахождение разности мн-в, но неправильно описал алгоритм целиком, бгг...
V>Т.е. незачем разбивать этот алгоритм этапы, где одним из этапов будет построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.
Какой из автоматов в ответе копилота вы называете "промежуточным"?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
V>>Иногда нетривиальная. V>>(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти) S>Нет. Такого не может быть. Инверсный автомат содержит ровно столько же состояний и столько же переходов, сколько основной (независимо от того, что вы понимаете под "инверсией"). S>Но вы можете убедить меня контрпримером.
А если из терминального состояния исходного автомата есть переходы?
Например, на практике лексеры работают по "жадному" алгоритму, т.е. ДКА не останавливается по достижению терминального состояния, а лишь запоминает его и продолжает работу.
Останавливается только когда попадает в ошибочное состояние.
Тогда последнее запомненное терминальное состояние + позиция курсора в нём даёт лексему и её код.
Допустим, дан алфавит из 3-х символов a, b, c.
Из терминального состояния Sfx есть переход в терминальное или нетерминальное состояние Sfx--a-->Snx, тогда инверсный автомат должен добавить переходы Sfx--b-->Snx, Sfx--c-->Snx.
Такое дополнение требуется для каждого терминального состояния, из которого есть переходы в другие валидные состояния.
Что тут может помочь — это минимизация не только состояний, но и алфавита, т.е. табличная замена одного алфавита на другой, где по одним и тем же символам автомат из всех состояний переходит в одни и те же следующие состояния. Тогда инверсный автомат может вырасти несильно.
Но минимизация алфавита — тоже достаточно затратная операция, хотя зачастую даёт выигрыш в памяти в представлении таблицы переходов и я эту минимизацию регулярно использую. Например, в одном из проектов построение ДКА, который парсит строковые представления енумов, тогда алфавит сужается до используемого в идентификаторах енумов множества символов, а остальные заменяются на специальный символ "ненужный".
В случае других способов представления таблицы переходов, скажем, отсортированным списком или в коде сгенерены переходы по switch-case (что после компиляции в бинарнике зачастую выражается в такой же поиск по отсортированному списку) минимизация алфавита не требуется.
Никакую, показан принцип.
Для сравнения на "больше" само сравнение требуется немного модифицировать, т.е. во всех состояниях множество переходов второго автомата должно являться подмножеством первого или быть пустым.
V>>Т.е. незачем разбивать этот алгоритм этапы, где одним из этапов будет построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки. S>Какой из автоматов в ответе копилота вы называете "промежуточным"?
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Sinclair, Вы писали:
V>>>Иногда нетривиальная. V>>>(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти) S>>Нет. Такого не может быть. Инверсный автомат содержит ровно столько же состояний и столько же переходов, сколько основной (независимо от того, что вы понимаете под "инверсией"). S>>Но вы можете убедить меня контрпримером.
V>А если из терминального состояния исходного автомата есть переходы?
Они всегда есть — в состояние ∅. См. замечание в разделе "Проверка на эквивалентность":
для реализации оба автомата обязательно должны иметь дьявольские состояния.
V>Допустим, дан алфавит из 3-х символов a, b, c. V>Из терминального состояния Sfx есть переход в терминальное или нетерминальное состояние Sfx--a-->Snx, тогда инверсный автомат должен добавить переходы Sfx--b-->Snx, Sfx--c-->Snx. V>Такое дополнение требуется для каждого терминального состояния, из которого есть переходы в другие валидные состояния.
Нет, не требуется. В инверсном автомате — ровно те же состояния, только их смысл меняется на обратный. В частности, ∅ становится терминальным состоянием.
V>Что тут может помочь — это минимизация не только состояний, но и алфавита, т.е. табличная замена одного алфавита на другой, где по одним и тем же символам автомат из всех состояний переходит в одни и те же следующие состояния. Тогда инверсный автомат может вырасти несильно. V>В случае других способов представления таблицы переходов, скажем, отсортированным списком или в коде сгенерены переходы по switch-case (что после компиляции в бинарнике зачастую выражается в такой же поиск по отсортированному списку) минимизация алфавита не требуется.
В случае, когда хранится полная таблица переходов, инверсия ничего не изменит — в частности, есть слоты для переходов из Sfx по b и с.
В случае, когда таблица представлена отсортированным списком, минимизация алфавита для инверсного автомата не поможет — там и так алфавит "минимален", и ни по каким из символов автомат не переходит в одни и те же состояния.
V>Никакую, показан принцип.
Эмм. Принцип там не приведён. Приведено два совершенно разных решения.
V>Инверсный.
Инверсный автомат совершенно необязательно строить явно. Можно просто реализовать операцию A × ¬ B как то же умножение в котором инвертированы состояния B. В частности, если из состояния Ai есть переход по x, а в Bj такого перехода нету, то в A × ¬ B из (Ai, Bj) по x мы переходим в терминальное состояние (Ai, ∅). То есть ни в A, ни в B нам не нужно добавлять дьявольское состояние и достраивать таблицу переходов до размера |Q|*|Σ|.
Такая реализация изоморфна подразумеваемому вами алгоритму проверки через BFS. Асимптотика у него линейная по размеру таблицы переходов, O(|Σ||Q|)
Первый же вариант, приведённый там, по асимптотике хуже — там O(|Σ||Q|log(|Q|).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
