Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Екі таспалы шекті күйдегі машина (кіріс, шығыс)
Finite state machine with two tapes (input, output)
Шекті күйдегі түрлендіргіш (FST) – Тьюринг машиналарындағы терминологияға сәйкес, екі жад таспасы бар шекті күйдегі машина: кіріс таспасы және шығыс таспасы. Бұл бір таспалы қарапайым шекті күй автоматынан (FSA) өзгеше. FST – екі символдар жиыны арасында байланыс орнатуға мүмкіндік беретін шекті күй автоматының (FSA) бір түрі. FST, FSA-ға қарағанда көбірек мүмкіндіктерге ие. FSA ресми тілді қабылданған жолдар жиынтығы арқылы анықтайды, ал FST жолдар жиынтықтары арасындағы қатынасты анықтайды. FST кіріс таспасындағы жолдар жиынтығын оқып, шығыс таспасында қатынастар жиынтығын құрайды. FST-ны жиынтықтағы жолдар арасындағы аудармашы немесе байланыстырушы құрал деп қарастыруға болады. Мысалы, морфологиялық талдауда, FST-ге әріптерден тұратын жол берілсе, FST морфемалардың тізбесін шығарады.
A finite state transducer (FST) is a finite state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite state automaton, which has a single tape. An FST is a type of finite state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines a relation between sets of strings. An FST will read a set of strings on the input tape and generates a set of relations on the output tape. An FST can be thought of as a translator or relater between strings in a set. In morphological parsing, an example would be inputting a string of letters into the FST, the FST would then output a string of morphemes.
Шолу
Автоматтың таспасының мазмұнын кіріс ретінде қарастырсақ, автомат тізбекті таниды деуге болады. Басқаша айтқанда, автомат тізбектерді {0,1} жиынына бейнелейтін функцияны есептейді. Керісінше, автомат тізбектерді жасайды деуге болады, яғни таспасын шығыс таспасы ретінде қарастыруға болады. Осы көзқарас бойынша, автомат формальды тілді, атап айтқанда тізбектер жиынын жасайды. Автоматтардың екі көрінісі эквивалентті: автомат есептейтін функция – ол жасайтын тізбектер жиынының индикатор функциясымен сәйкес келеді. Шекті автоматтармен жасалатын тілдер класы ресми тілдер класы деп аталады. Трансдуктордың екі таспасы әдетте кіріс таспасы және шығыс таспасы ретінде қарастырылады. Осы көзқарас бойынша, трансдуктор кіріс таспасындағы тізбекті қабылдап, шығыс таспасында басқа тізбекті жасай отырып, кіріс таспасының мазмұнын түрлендіреді (яғни аударады). Ол бұл процесті детерминистік емес түрде жүзеге асыруы мүмкін және әрбір кіріс тізбегі үшін бірнеше шығыс нұсқаларын жасауы мүмкін. Трансдуктор берілген кіріс тізбегі үшін ешқандай шығыс жасамаса, онда ол кірісті қабылдамайды деп есептеледі. Жалпы алғанда, трансдуктор екі формальды тіл арасындағы қатынасты есептейді. Кез келген тізбек-тізбек шекті күйдегі трансдуктор кіріс алфавиті Σ-ні шығыс алфавиті Γ-мен байланыстырады. Σ*×Γ* бойынша анықталған және шекті күйдегі трансдуктор ретінде іске асырыла алатын қатынастар рационалды қатынастар деп аталады. Рационалды қатынастардың ішінде, әрбір кіріс тізбегін Σ*-ден ең көп дегенде бір Γ*-ге байланыстыратын, яғни ішінара функциялар рационалды функциялар деп аталады. Шекті күйдегі трансдукторлар табиғи тілді өңдеудегі зерттеулер мен қолданбаларда фонологиялық және морфологиялық талдау үшін жиі қолданылады. Осы саладағы алғашқы зерттеушілер Рональд Каплан, Лаури Карттунен, Мартин Кей және Киммо Коскеньеми болды. Трансдукторларды қолданудың кең таралған тәсілі – "каскад" деп аталатын әдіс, онда әртүрлі операцияларға арналған трансдукторлар композиция операторын (төменде анықталған) қайталап қолдану арқылы бір трансдукторға біріктіріледі.
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-тің бір түрі болуы мүмкін.
Stochastic FSTs (also known as probabilistic FSTs or statistical FSTs) are presumably a form of weighted FST.
Шекті күйдегі трансформаторлардың қосымша қасиеттері
Трансформатордың [T] қатынасы бос екенін анықтауға болады. Берілген x жолы үшін x[T]y түрінде y жолының бар-жоқтығын анықтауға болады. Екі трансформатордың эквивалентті екендігі шешілмейді. Дегенмен, егер трансформатордың [T] қатынасы (ішінара) функция болса, эквиваленттілік арнайы жағдайда шешіледі. Егер белгілер алфавитін анықтаса, шекті күйдегі трансформаторлар осы алфавит бойынша NDFA-ға изоморфты болады, сондықтан оларды детерминизациялауға болады (осы алфавит бойынша детерминистік шекті автоматтарға түрлендіруге болады) және одан кейін күйлер санын ең аз деңгейге дейін азайтуға болады.
It is decidable whether the relation [T] of a transducer T is empty. It is decidable whether there exists a string y such that x[T]y for a given string x. It is undecidable whether two transducers are equivalent. Equivalence is however decidable in the special case where the relation [T] of a transducer T is a (partial) function. If one defines the alphabet of labels , finite state transducers are isomorphic to NDFA over the alphabet , and may therefore be determinized (turned into deterministic finite automata over the alphabet ) and subsequently minimized so that they have the minimum number of states.
Қолданбалар
FST-лер компиляторлардың лексикалық талдау кезеңінде анықталған таңбаларды семантикалық мәнмен байланыстыру үшін қолданылады. Лингвистикада дыбыстану ережелерін және дыбыс өзгерісін модельдеу үшін қолданылатын a → b / c d түріндегі контекстке тәуелді қайта жазу ережелері, қолданылуы рекурсивті болмаса, яғни ереже бірдей таңба тізбегін екі рет қайта жазуға рұқсат етілмесе, шекті күйдегі түрлендіргіштермен есептеу жағынан теңдес келеді. Салмақты FST-лер табиғи тілді өңдеуде, соның ішінде машиналық аудармада және машиналық оқытуда қолданыс тапты. Сөздердің сөз түрлерін анықтаудың бір бөлігін іске асыру OpenGrm кітапханасының бір құрамында кездеседі.
FSTs are used in the lexical analysis phase of compilers to associate semantic value with the discovered tokens. Context sensitive rewriting rules of the form a → b / c d, used in linguistics to model phonological rules and sound change, are computationally equivalent to finite state transducers, provided that application is nonrecursive, i. e. the rule is not allowed to rewrite the same substring twice. Weighted FSTs found applications in natural language processing, including machine translation, and in machine learning. An implementation for part of speech tagging can be found as one component of the OpenGrm library.