Что такое конечный датчик?

Question

Может кто-нибудь сказать мне, что такое датчик конечного состояния?

Я прочитал статью Википедии и ничего не понимаю.

Answer 1

Преобразователь конечного состояния (FST) - это автомат конечного состояния (FSA, FA), который выдает выходные данные, а также считывает входные данные, что означает, что он полезен для анализа (в то время как «голый» FSA может использоваться только для распознавания,то есть сопоставление с образцом).

FST состоит из конечного числа состояний, которые связаны переходами, помеченными парой вход / выход.FST запускается в заданном начальном состоянии и переходит к различным состояниям в зависимости от входных данных, в то же время производя выходные данные в соответствии с таблицей переходов.

FST полезны в NLP и распознавании речи, поскольку обладают хорошими алгебраическими свойствами, большинствоПримечательно, что они могут быть свободно объединены (образуют алгебру) под композицией, которая реализует реляционную композицию на регулярных отношениях (представьте это как недетерминированную композицию функций), оставаясь при этом очень компактной.FST могут выполнять разбор регулярных языков в строки за линейное время.

В качестве примера я однажды реализовал морфологический разбор в виде набора FST.Мой основной FST для глаголов превратил бы обычный глагол, скажем, «гулял», в «прогулка + ПРОШЛОЕ».У меня также был FST для глагола «быть», который превращал бы «есть» в «быть + НАСТОЯЩЕЕ + 3-е» (3-е лицо), и аналогично для других неправильных глаголов.Все FST были объединены в один с использованием компилятора FST, который создавал один FST, который был намного меньше суммы его частей и работал очень быстро.FST могут быть созданы различными инструментами, которые принимают расширенный синтаксис регулярного выражения.

Answer 2

Датчик конечного состояния, по сути, является автоматом конечного состояния, который работает на двух (или более) лентах. Наиболее распространенный способ думать о преобразователях - это своего рода «переводчик». Они читают с одной из лент и пишут на другой. Это, например, преобразователь, который переводит a с в b с:

a:b на дуге означает, что при этом переходе преобразователь считывает a с первой ленты и записывает b на вторую.

Ссылка: Конечные датчики состояния

Answer 3

Проще говоря, я понимаю, что FST - это, по сути, «вещь», которая перемещается из одного состояния в другое на основе входной ленты и записывает на другую выходную ленту. Лента по сути представляет собой набор входных данных, таких как символы в строке.

Весь FST представлен набором состояний и связей между ними. Ссылка «активируется», когда ее входные условия правильные, а затем возвращает следующее состояние отрегулированной ленте.

Например, допустим, FST начинается с ленты abc в состоянии 1. Ссылка на состояние 2 соответствует a и изменяет ее на b. Это активируется, устанавливает выходную ленту на b и передает оставшееся bc в состояние 2. Как вы можете видеть, каждое состояние активируется, только если есть ссылка на него, чье входное условие было правильным оставшиеся вводятся в следующее состояние и записываются на отдельную ленту вывода. Каждый FST проходит по ленте один раз и выводит на другую ленту один раз.

Чтобы получить более четкое представление о них прочитайте и посмотрите на диаграммы в этой статье ( оригинальная неработающая ссылка ).