Finite-state transducer (original) (raw)
Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Akzeptor eine Ausgabe erzeugt. Er überführt (übersetzt) eine Quellsprache in eine Zielsprache. Da die formalen Eigenschaften dieser Sprachen variieren können, unterscheidet man verschiedene Untertypen, die im Folgenden näher beschrieben werden.
| Property | Value |
|---|---|
| dbo:abstract | Un transductor d'estats finits, o transductor finit, és un autòmat finit (o màquina d'estats finits) amb dues cintes, una d'entrada i una d'eixida. Açò contrasta amb un autòmat finit habitual, que només té una cinta. Podem dir que l'autòmat reconeix una cadena si aquesta es troba en la seva cinta d'entrada. En altres paraules, l'autòmat computa una funció que converteix una cadena en un element del conjunt {0,1}. D'altra banda, podem dir que un autòmat genera cadenes, a partir de la seva cinta d'eixida. Des d'aquest punt de vista, l'autòmat genera un llenguatge formal, que no és més que un conjunt de cadenes. Els dos punts de vista de l'autòmat són equivalents: la funció que computa l'autòmat és la funció indicadora del conjunt de cadenes reconegudes. La classe de llenguatges generats per un autòmat finit es coneix amb el nom de llenguatges regulars. Les dues cintes d'un transductor són vistes típicament com una cinta d'entrada i una altra d'eixida. Des d'aquest punt de vista, un transductor transdueix (açò és, tradueix) el contingut de la seva cinta d'entrada a la seva cinta d'eixida, acceptat cadenes en la seva cinta d'entrada i generant altres cadenes en la seva cinta d'eixida. Pot fer-ho de forma no-determinística, cosa que produirà més d'una eixida per a cada cadena d'entrada. Un transductor també pot no produir cap eixda per a una cadena d'entrada donada; en aquest cas es diu que rebutja l'entrada. En general, un transductor computa una relació entre dos llenguatges formals. La classe de relacions computades per un transductor d'estats finits es coneix com a classe de . Els transductors d'estats finits són utilitzats habitualment en anàlisi morfològiques, en l'àrea d'investigació de processament del llenguatge natural i en les seves aplicacions. (ca) Konečný převodník (anglicky finite-state transducer, FST) je konečný automat se dvěma paměťovými páskami podle terminologie používané pro Turingovy stroje: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného konečného automatu, který má jen jednu pásku. Konečný převodník je typem konečného automatu, který provádí převod mezi dvěma množinami symbolů. Konečné převodníky lze považovat za zobecnění konečných automatů; zatímco konečný automat definuje formální jazyk určením množiny přijímaných řetězců, konečný převodník definuje relaci mezi množinami řetězců. Konečný převodník čte řetězce ze vstupní pásky a generuje množinu relací na výstupní pásce. Na konečný převodník lze pohlížet jako na překladač nebo zařízení pro určení vztahů mezi množinami řetězců. Při morfologické analýze může být vstupem konečného převodníku řetězec symbolů, a konečný převodník produkuje řetězec morfémů. (cs) Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Akzeptor eine Ausgabe erzeugt. Er überführt (übersetzt) eine Quellsprache in eine Zielsprache. Da die formalen Eigenschaften dieser Sprachen variieren können, unterscheidet man verschiedene Untertypen, die im Folgenden näher beschrieben werden. (de) 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 relations 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. (en) Un transductor de estados finitos, o transductor finito, es un autómata finito (o máquina de estados finitos) con dos cintas, una de entrada y otra de salida. Esto contrasta con un autómata finito habitual, que tiene solamente una cinta. Podemos decir que el autómata reconoce una cadena si esta se encuentra en su cinta de entrada. En otras palabras, el autómata computa una función que convierte una cadena en un elemento del conjunto (0,1). Por otra parte, podemos decir que un autómata genera cadenas a partir de su cinta de salida. Desde este punto de vista, el autómata genera un lenguaje formal, que no es más que un conjunto de cadenas. Los dos puntos de vista del autómata son equivalentes: la función que computa el autómata es la función indicadora del conjunto de cadenas reconocidas. La clase de lenguajes generados por un autómata finito se conoce con el nombre de lenguajes regulares Típicamente las dos cintas de un transductor se ven como una cinta de entrada y otra de salida. Desde este punto de vista, un transductor se dice que transduce (traduce) el contenido de la cinta de entrada a la cinta de salida, mediante la aceptación de una cadena en la cinta de entrada, y la generación de otra cadena en la cinta de salida. Esta transducción se puede realizar de forma no determinista y entonces se producirá más de una salida por cada cadena de entrada. Un transductor también puede no producir ninguna salida para una cadena de entrada, y en este caso se dice que el transductor rechaza la entrada. En general, un transductor establece una relación entre dos lenguajes formales. La clase de relaciones computadas por un transductor de estados finitos se conoce como una clase de relaciones racionales. Los transductores de estados finitos se utilizan normalmente en análisis morfológico y en la investigación y aplicaciones de procesamiento del lenguaje natural. (es) En informatique théorique, en linguistique, et en particulier en théorie des automates,un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie. Ceci permet des transformations de langages, et aussi des utilisations variées telles que notamment l'analyse syntaxique des langages de programmation, et l'analyse morphologique ou l'analyse phonologique en linguistique. Une des propriétés remarquables des transducteurs finis est qu'ils transforment les langages rationnels en langages rationnels, et les langages algébriques en langages algébriques. (fr) Transdutor de estados finitos é um máquina de estados finitos com duas fitas: uma fita de entrada e uma fita de saída. Isto contrasta com um autômato finito comum (ou aceitador de estado finito), que tem apenas uma única fita. (pt) Конечный автомат с выходом — разновидность детерминированного конечного автомата, дополненная выходным алфавитом и функцией выходов. (ru) |
| dbo:wikiPageExternalLink | http://hfst.github.io/ http://jsalatas.ictpro.gr/java-fst-framework-api-review/ http://openfst.org/ http://vcsn.lrde.epita.fr/ http://www.cis.uni-muenchen.de/~schmid/tools/SFST/ http://www.cs.nyu.edu/~mohri/pub/fla.pdf http://www.cs.nyu.edu/~mohri/pub/twins.pdf http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html https://archive.org/details/finitestatelangu00roch%7Curl-access= https://archive.org/details/finitestatelangu00roch/page/n15 https://archive.org/details/speechlanguagepr00jura%7Curl-access= https://archive.org/details/speechlanguagepr00jura/page/n206 https://web.stanford.edu/~laurik/fsmbook/home.html https://www.youtube.com/watch%3Fv=F_dTuHS6Wbk https://code.google.com/archive/p/foma/ http://www.ling.helsinki.fi/~koskenni/doc/Two-LevelMorphology.pdf |
| dbo:wikiPageID | 1071289 (xsd:integer) |
| dbo:wikiPageLength | 19526 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099044260 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Powerset_construction dbr:Moore_machine dbr:Natural_language_processing dbr:Nondeterministic_finite_automaton dbr:Morphological_dictionary dbr:Deterministic_finite_automaton dbr:Relation_(mathematics) dbr:Characterization_(mathematics) dbr:University_of_Helsinki dbr:Decidability_(logic) dbr:Lexical_analysis dbr:Compilers dbr:Concatenation dbr:Ronald_Kaplan dbr:Empty_string dbr:Morphemes dbr:Morphology_(linguistics) dbr:Machine_learning dbr:Composition_of_relations dbr:Partial_function dbr:Phonology dbr:Mealy_machine dbr:Transitive_closure dbr:Tree_transducer dbr:Lauri_Karttunen dbr:Linguistics dbr:Log_semiring dbc:Finite_automata dbr:Finite-state_automaton dbr:Finite_set dbr:Foma_(software) dbr:Directed_graph dbr:Formal_language dbr:Kimmo_Koskenniemi dbr:Part-of-speech_tagging dbr:Projection_(mathematics) dbr:Regular_language dbr:Boolean_semiring dbr:Karlsruhe_Institute_of_Technology dbr:Automaton dbr:Martin_Kay dbr:Sound_change dbr:If_and_only_if dbr:Indicator_function dbr:Kleene_closure dbr:Semiring dbr:Machine_translation dbr:Turing_machine dbr:Phonological_rule dbr:Undecidable_problem dbr:Union_(set_theory) dbr:Nondeterministic_finite_automata dbr:Finite-state_machine dbr:Nondeterministic_algorithm dbr:Subset dbr:Tropical_semiring dbr:Determinization dbr:Twins_property |
| dbp:float | right (en) |
| dbp:video | Finite State Transducers // Karlsruhe Institute of Technology, YouTube video (en) |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Citation dbt:Citation_needed dbt:Citation_style dbt:Cite_book dbt:Cite_journal dbt:External_media dbt:Math dbt:More_footnotes dbt:Multiple_issues dbt:Mvar dbt:NumBlk dbt:Primary_source_inline dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Short_description dbt:EquationRef dbt:EquationNote dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Finite_automata |
| rdf:type | owl:Thing |
| rdfs:comment | Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Akzeptor eine Ausgabe erzeugt. Er überführt (übersetzt) eine Quellsprache in eine Zielsprache. Da die formalen Eigenschaften dieser Sprachen variieren können, unterscheidet man verschiedene Untertypen, die im Folgenden näher beschrieben werden. (de) Transdutor de estados finitos é um máquina de estados finitos com duas fitas: uma fita de entrada e uma fita de saída. Isto contrasta com um autômato finito comum (ou aceitador de estado finito), que tem apenas uma única fita. (pt) Конечный автомат с выходом — разновидность детерминированного конечного автомата, дополненная выходным алфавитом и функцией выходов. (ru) Un transductor d'estats finits, o transductor finit, és un autòmat finit (o màquina d'estats finits) amb dues cintes, una d'entrada i una d'eixida. Açò contrasta amb un autòmat finit habitual, que només té una cinta. Podem dir que l'autòmat reconeix una cadena si aquesta es troba en la seva cinta d'entrada. En altres paraules, l'autòmat computa una funció que converteix una cadena en un element del conjunt {0,1}. D'altra banda, podem dir que un autòmat genera cadenes, a partir de la seva cinta d'eixida. Des d'aquest punt de vista, l'autòmat genera un llenguatge formal, que no és més que un conjunt de cadenes. Els dos punts de vista de l'autòmat són equivalents: la funció que computa l'autòmat és la funció indicadora del conjunt de cadenes reconegudes. La classe de llenguatges generats per (ca) Konečný převodník (anglicky finite-state transducer, FST) je konečný automat se dvěma paměťovými páskami podle terminologie používané pro Turingovy stroje: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného konečného automatu, který má jen jednu pásku. Konečný převodník je typem konečného automatu, který provádí převod mezi dvěma množinami symbolů. Konečné převodníky lze považovat za zobecnění konečných automatů; zatímco konečný automat definuje formální jazyk určením množiny přijímaných řetězců, konečný převodník definuje relaci mezi množinami řetězců. (cs) 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 relations between sets of strings. (en) Un transductor de estados finitos, o transductor finito, es un autómata finito (o máquina de estados finitos) con dos cintas, una de entrada y otra de salida. Esto contrasta con un autómata finito habitual, que tiene solamente una cinta. Podemos decir que el autómata reconoce una cadena si esta se encuentra en su cinta de entrada. En otras palabras, el autómata computa una función que convierte una cadena en un elemento del conjunto (0,1). Por otra parte, podemos decir que un autómata genera cadenas a partir de su cinta de salida. Desde este punto de vista, el autómata genera un lenguaje formal, que no es más que un conjunto de cadenas. Los dos puntos de vista del autómata son equivalentes: la función que computa el autómata es la función indicadora del conjunto de cadenas reconocidas. La (es) En informatique théorique, en linguistique, et en particulier en théorie des automates,un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie. Ceci permet des transformations de langages, et aussi des utilisations variées telles que notamment l'analyse syntaxique des langages de programmation, et l'analyse morphologique ou l'analyse phonologique en linguistique. (fr) |
| rdfs:label | Transductor d'estats finits (ca) Konečný převodník (cs) Transduktor (Informatik) (de) Transductor de estados finitos (es) Finite-state transducer (en) Transducteur fini (fr) Transdutor de estados finitos (pt) Конечный автомат с выходом (ru) |
| rdfs:seeAlso | dbr:Rational_series |
| owl:sameAs | yago-res:Finite-state transducer http://d-nb.info/gnd/4529256-5 wikidata:Finite-state transducer http://bs.dbpedia.org/resource/Konačni_transduktor dbpedia-ca:Finite-state transducer dbpedia-cs:Finite-state transducer dbpedia-de:Finite-state transducer dbpedia-es:Finite-state transducer dbpedia-fa:Finite-state transducer dbpedia-fr:Finite-state transducer dbpedia-hr:Finite-state transducer dbpedia-pt:Finite-state transducer dbpedia-ru:Finite-state transducer dbpedia-sr:Finite-state transducer https://global.dbpedia.org/id/23oiU |
| prov:wasDerivedFrom | wikipedia-en:Finite-state_transducer?oldid=1099044260&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Finite-state_transducer |
| is dbo:wikiPageDisambiguates of | dbr:FST |
| is dbo:wikiPageRedirects of | dbr:Operations_on_finite-state_transducers dbr:Finite_state_transducer dbr:Finite_state_transducers dbr:Finite_transducer dbr:Weighted_finite-state_transducer |
| is dbo:wikiPageWikiLink of | dbr:FST dbr:Moore_machine dbr:Nondeterministic_finite_automaton dbr:Morphological_dictionary dbr:Reversible_cellular_automaton dbr:Weighted_automaton dbr:Maurice_Nivat dbr:Operations_on_finite-state_transducers dbr:Constraint_grammar dbr:Tagged_Deterministic_Finite_Automaton dbr:Mealy_machine dbr:Tree_automaton dbr:Tree_transducer dbr:Graph_theory dbr:HFST dbr:Finite_state_transducer dbr:Arvi_Hurskainen dbr:Automata_theory dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Finite-state_machine dbr:Finite_state_transducers dbr:Finite_transducer dbr:Weighted_finite-state_transducer |
| is foaf:primaryTopic of | wikipedia-en:Finite-state_transducer |