Оглавление
Взвешенный автомат
-
Определение и применение взвешенных автоматов
- Взвешенные автоматы – это машины, которые принимают входные строки и присваивают веса состояниям.
- Они обобщают детерминированные и недетерминированные конечные автоматы, а также могут использоваться для вероятностного моделирования.
- Взвешенные автоматы применяются в обработке естественного языка и сжатии изображений.
-
Определение взвешенного автомата
- Взвешенный автомат – это кортеж, состоящий из конечного множества состояний, алфавита, переходов, начальных и конечных весов.
- Весомость пути определяется как произведение весов вдоль пути, умноженное на начальные и конечные веса.
- Машина определяет функцию от входной строки к вещественному числу, которая учитывает веса всех путей.
-
Двусмысленность и детерминизм
- Взвешенные автоматы могут иметь несколько путей для одной входной строки, что делает их похожими на недетерминированные автоматы.
- Существуют детерминированные и однозначные взвешенные автоматы, где детерминированные автоматы имеют только один приемлемый путь.
-
Вариации и ограничения
- В определении могут быть опущены нулевые элементы для операции сложения, что приводит к частичной функции.
- Можно разрешить эпсилон-переходы, но это не увеличивает выразительность.
- Некоторые авторы опускают начальные и конечные весовые функции, заменяя их наборами состояний.
- Функция перехода может быть задана матрицей, а не набором переходов.
-
Дополнительные сведения
- Взвешенные автоматы связаны с вероятностными автоматами, марковскими процессами принятия решений и марковскими цепями.
- Существуют ограничения на полукольца, используемые в определении, особенно при изучении разрешимости.