Конечно-автомат с двумя лентами (вход, выход)

Введение

Конечная машина с двумя лентами (вход, выход)

Конечный преобразователь состояний (FST) – это конечная машина с двумя лентами памяти, в соответствии с терминологией, используемой для машин Тьюринга: входная лента и выходная лента. Это отличается от обычного конечного автомата, который имеет только одну ленту. FST является типом конечного автомата (FSA), который осуществляет отображение между двумя множествами символов. FST более универсален, чем FSA. FSA определяет формальный язык, определяя множество допустимых строк, в то время как FST определяет отношение между множествами строк. FST считывает множество строк на входной ленте и генерирует множество соответствий на выходной ленте. FST можно рассматривать как преобразователь или установщик соответствия между строками в множестве. В морфологическом анализе, например, на вход FST подается строка букв, а на выходе FST генерирует строку морфем.

Обзор

Автомат можно сказать, что распознает строку, если рассматривать содержимое его ленты как входные данные. Иными словами, автомат вычисляет функцию, которая отображает строки в множество {0,1}. Альтернативно, можно сказать, что автомат генерирует строки, что означает рассматривать его ленту как выходную ленту. С этой точки зрения, автомат генерирует формальный язык, который представляет собой набор строк. Оба взгляда на автоматы эквивалентны: функция, которую вычисляет автомат, является точно индикаторной функцией множества строк, которые он генерирует. Класс языков, генерируемых конечными автоматами, известен как класс регулярных языков. Две ленты преобразователя обычно рассматриваются как входная и выходная ленты. С этой точки зрения, преобразователь (или трансдуктор) преобразует содержимое своей входной ленты в выходную ленту, принимая строку на входной ленте и генерируя другую строку на выходной ленте. Он может делать это недетерминированно и может выдавать более одного результата для каждой входной строки. Преобразователь также может не выдавать результат для данной входной строки, в этом случае говорят, что он отклоняет входные данные. В общем случае, преобразователь вычисляет отношение между двумя формальными языками. Каждый конечно-автоматный преобразователь строк соотносит входной алфавит Σ с выходным алфавитом Γ. Отношения R на Σ*×Γ*, которые могут быть реализованы в виде конечно-автоматных преобразователей, называются рациональными отношениями. Рациональные отношения, являющиеся частичными функциями, то есть связывающие каждую входную строку из Σ* максимум с одной Γ*, называются рациональными функциями. Конечно-автоматные преобразователи часто используются для фонологического и морфологического анализа в исследованиях и приложениях обработки естественного языка. Среди пионеров в этой области – Рональд Каплан, Лаури Карттунен, Мартин Кей и Киммо Коскеньеми. Распространенный способ использования преобразователей – так называемая «каскадная» схема, в которой преобразователи для различных операций объединяются в один преобразователь путем многократного применения оператора композиции (определенного ниже).

An automaton can be said to recognize a string if we view the content of its tape as input. In other words, the automaton computes a function that maps strings into the set {0,1}. Alternatively, we can say that an automaton generates strings, which means viewing its tape as an output tape. On this view, the automaton generates a formal language, which is a set of strings. The two views of automata are equivalent: the function that the automaton computes is precisely the indicator function of the set of strings it generates. The class of languages generated by finite automata is known as the class of regular languages. The two tapes of a transducer are typically viewed as an input tape and an output tape. On this view, a transducer is said to transduce (i. e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape. It may do so nondeterministically and it may produce more than one output for each input string. A transducer may also produce no output for a given input string, in which case it is said to reject the input. In general, a transducer computes a relation between two formal languages. Each string to string finite state transducer relates the input alphabet Σ to the output alphabet Γ. Relations R on Σ*×Γ* that can be implemented as finite state transducers are called rational relations. Rational relations that are partial functions, i. e. that relate every input string from Σ* to at most one Γ*, are called rational functions. Finite state transducers are often used for phonological and morphological analysis in natural language processing research and applications. Pioneers in this field include Ronald Kaplan, Lauri Karttunen, Martin Kay and Kimmo Koskenniemi. A common way of using transducers is in a so called "cascade", where transducers for various operations are combined into a single transducer by repeated application of the composition operator (defined below).

Стохастический FST

Стохастические FST (также известные как вероятностные FST или статистические FST) предположительно представляют собой разновидность взвешенных FST.

Дополнительные свойства конечных преобразователей

Можно определить, пустое ли отношение [T] преобразователя T. Можно определить, существует ли строка y такая, что x[T]y для заданной строки x. Невозможно определить, эквивалентны ли два преобразователя. Однако эквивалентность определима в частном случае, когда отношение [T] преобразователя T является (частичной) функцией. Если задать алфавит меток, конечные автоматы преобразователей изоморфны недетерминированным конечным автоматам (НКА) над этим алфавитом, и, следовательно, могут быть детерминизированы (преобразованы в детерминированные конечные автоматы над этим алфавитом) и впоследствии минимизированы до минимального числа состояний.

Приложения

FST используются на этапе лексического анализа компиляторов для связывания семантических значений с обнаруженными лексемами. Контекстно-зависимые правила переписывания вида a → b / c d, применяемые в лингвистике для моделирования фонологических правил и звуковых изменений, вычислительно эквивалентны конечным преобразователям состояний, при условии, что применение нерекурсивно, то есть правило не должно переписывать один и тот же фрагмент текста дважды. Взвешенные FST нашли применение в обработке естественного языка, включая машинный перевод, и в машинном обучении. Реализация для определения частей речи доступна в качестве одного из компонентов библиотеки OpenGrm.