Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, Sinclair, Вы писали:

V>>>Иногда нетривиальная.
V>>>(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти)
S>>Нет. Такого не может быть. Инверсный автомат содержит ровно столько же состояний и столько же переходов, сколько основной (независимо от того, что вы понимаете под "инверсией").
S>>Но вы можете убедить меня контрпримером.

V>А если из терминального состояния исходного автомата есть переходы?
Они всегда есть — в состояние ∅. См. замечание в разделе "Проверка на эквивалентность":

для реализации оба автомата обязательно должны иметь дьявольские состояния.

V>Допустим, дан алфавит из 3-х символов a, b, c.
V>Из терминального состояния Sf_x есть переход в терминальное или нетерминальное состояние Sf_x--a-->Sn_x, тогда инверсный автомат должен добавить переходы Sf_x--b-->Sn_x, Sf_x--c-->Sn_x.
V>Такое дополнение требуется для каждого терминального состояния, из которого есть переходы в другие валидные состояния.
Нет, не требуется. В инверсном автомате — ровно те же состояния, только их смысл меняется на обратный. В частности, ∅ становится терминальным состоянием.

V>Что тут может помочь — это минимизация не только состояний, но и алфавита, т.е. табличная замена одного алфавита на другой, где по одним и тем же символам автомат из всех состояний переходит в одни и те же следующие состояния. Тогда инверсный автомат может вырасти несильно.
V>В случае других способов представления таблицы переходов, скажем, отсортированным списком или в коде сгенерены переходы по switch-case (что после компиляции в бинарнике зачастую выражается в такой же поиск по отсортированному списку) минимизация алфавита не требуется.
В случае, когда хранится полная таблица переходов, инверсия ничего не изменит — в частности, есть слоты для переходов из Sf_x по b и с.
В случае, когда таблица представлена отсортированным списком, минимизация алфавита для инверсного автомата не поможет — там и так алфавит "минимален", и ни по каким из символов автомат не переходит в одни и те же состояния.

V>Никакую, показан принцип.
Эмм. Принцип там не приведён. Приведено два совершенно разных решения.

V>Инверсный.
Инверсный автомат совершенно необязательно строить явно. Можно просто реализовать операцию A × ¬ B как то же умножение в котором инвертированы состояния B. В частности, если из состояния A[sub]i есть переход по x, а в B[sub]j такого перехода нету, то в A × ¬ B из (A[sub]i, B[sub]j) по x мы переходим в терминальное состояние (A[sub]i, ∅). То есть ни в A, ни в B нам не нужно добавлять дьявольское состояние и достраивать таблицу переходов до размера |Q|*|Σ|.
Такая реализация изоморфна подразумеваемому вами алгоритму проверки через BFS. Асимптотика у него линейная по размеру таблицы переходов, O(|Σ||Q|)
Первый же вариант, приведённый там, по асимптотике хуже — там O(|Σ||Q|log(|Q|).

Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, Sinclair, Вы писали:

V>>>Иногда нетривиальная.
V>>>(от размера алфавита зависит и от исходной грамматики, т.е. инверсный автомат может быть намного тяжелее целевого в памяти)
S>>Нет. Такого не может быть. Инверсный автомат содержит ровно столько же состояний и столько же переходов, сколько основной (независимо от того, что вы понимаете под "инверсией").
S>>Но вы можете убедить меня контрпримером.

V>А если из терминального состояния исходного автомата есть переходы?
Они всегда есть — в состояние ∅. См. замечание в разделе "Проверка на эквивалентность":

для реализации оба автомата обязательно должны иметь дьявольские состояния.

V>Допустим, дан алфавит из 3-х символов a, b, c.
V>Из терминального состояния Sf_x есть переход в терминальное или нетерминальное состояние Sf_x--a-->Sn_x, тогда инверсный автомат должен добавить переходы Sf_x--b-->Sn_x, Sf_x--c-->Sn_x.
V>Такое дополнение требуется для каждого терминального состояния, из которого есть переходы в другие валидные состояния.
Нет, не требуется. В инверсном автомате — ровно те же состояния, только их смысл меняется на обратный. В частности, ∅ становится терминальным состоянием.

V>Что тут может помочь — это минимизация не только состояний, но и алфавита, т.е. табличная замена одного алфавита на другой, где по одним и тем же символам автомат из всех состояний переходит в одни и те же следующие состояния. Тогда инверсный автомат может вырасти несильно.
V>В случае других способов представления таблицы переходов, скажем, отсортированным списком или в коде сгенерены переходы по switch-case (что после компиляции в бинарнике зачастую выражается в такой же поиск по отсортированному списку) минимизация алфавита не требуется.
В случае, когда хранится полная таблица переходов, инверсия ничего не изменит — в частности, есть слоты для переходов из Sf_x по b и с.
В случае, когда таблица представлена отсортированным списком, минимизация алфавита для инверсного автомата не поможет — там и так алфавит "минимален", и ни по каким из символов автомат не переходит в одни и те же состояния.

V>Никакую, показан принцип.
Эмм. Принцип там не приведён. Приведено два совершенно разных решения.

V>Инверсный.
Инверсный автомат совершенно необязательно строить явно. Можно просто реализовать операцию A × ¬ B как то же умножение в котором инвертированы состояния B. В частности, если из состояния A_i есть переход по x, а в B_j такого перехода нету, то в A × ¬ B из (A_i, B_j) по x мы переходим в терминальное состояние (A_i, ∅). То есть ни в A, ни в B нам не нужно добавлять дьявольское состояние и достраивать таблицу переходов до размера |Q|*|Σ|.
Такая реализация изоморфна подразумеваемому вами алгоритму проверки через BFS. Асимптотика у него линейная по размеру таблицы переходов, O(|Σ||Q|)
Первый же вариант, приведённый там, по асимптотике хуже — там O(|Σ||Q|log(|Q|).