{"id":789,"date":"2015-12-14T17:17:23","date_gmt":"2015-12-14T16:17:23","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=789"},"modified":"2015-12-15T12:03:27","modified_gmt":"2015-12-15T11:03:27","slug":"6-transducers","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/6-transducers","title":{"rendered":"6. Transducers"},"content":{"rendered":"

In this part of the lecture, we talk about automata which define functions<\/p>\n

  <\/span>   <\/span>\"\[f : \Sigma^* \to \Gamma^*\]\"<\/p>\n

Such automata are called transducers. Examples of functions that we wish to model include:<\/p>\n

    \n
  1. \u00a0replace every \"a\" by \"b\"<\/li>\n
  2. duplicate every \"a\"<\/li>\n
  3. duplicate every letter at an even-numbered position<\/li>\n
  4. swap the first and last letter<\/li>\n
  5. identity if the last letter is \"a\", otherwise erase the entire word<\/li>\n
  6. duplicate the entire word<\/li>\n
  7. reverse the entire word<\/li>\n<\/ol>\n

    The simplest possible model, which has already been discussed in previous lectures, is a deterministic finite automaton over the input alphabet, where every transition is labelled by letter of the output alphabet (this is enough to cover example 1), or a possibly empty word over the output alphabet (this is enough to cover examples 2 and 3).<\/p>\n

    The remaining examples require additional features. We describe two groups of transducers in the rest of the lecture.<\/p>\n

    In this lecture<\/a>, we describe nondeterministic finite automata with output, as well as two other models that have the same expressive power. These models are sufficient to cover examples 4 and 5.<\/p>\n

    To cover functions like duplication or reverse, much more power is needed. One solution is to use\u00a0two-way transducers<\/a>. Another solution is to uses one-way automata with registers<\/a>. Finally, we show that these solutions are equivalent.<\/p>\n

     <\/p>\n","protected":false},"excerpt":{"rendered":"

    In this part of the lecture, we talk about automata which define functions     Such automata are called transducers. Examples of functions that we wish to model include: \u00a0replace every by duplicate every duplicate every letter at an even-numbered position swap the first and last letter identity if the last letter is , otherwise […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":535,"menu_order":6,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-789","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/789"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=789"}],"version-history":[{"count":21,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/789\/revisions"}],"predecessor-version":[{"id":859,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/789\/revisions\/859"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/535"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=789"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}