# Why every rational langage is the image of a local automaton

I have seen this result but I don’t understand why it’s true :

Every rational language is the image of a local language by a morphism : $$\phi : \Sigma^{*’} \to \Sigma^*$$

I know what a local automaton is. It’s just an automaton that recognizes a local language. A local language is basically a language where all factors of size two are not in a certain set $$S$$. Now if I take a morphism from this language then it will still give me a local language right ? (i.e. the image of local language by a morphism is a local language). So I didn’t understand this result, I mean every rational language is not local...

Thank you !

This is seen as follows. A finite state automaton can be "encoded" by a 2-testable language by using the transitions as letters. So we consider symbols $$(p,a,q)$$. The corresponding language is 2-testable: basically test whether the transitions are consecutive which is clear from letter pairs: $$(p,a,\underline q)(\underline q,b,r)$$. We find the original language by applying a coding: $$(p,a,q)$$ maps to $$a$$.
(2) No. Local languages are not closed under codings. $$(ab)^*$$ is a local language. Initial letter $$a$$, final letter $$b$$, two letter substrings $$ab, ba$$. The image $$(aa)^*$$ is not local. There is no way to distinguish odd length strings from even length strings by just looking at substrings.
• There is no local automaton, but a local language. It is the language of he original finite state automaton, but every symbol $a$ (on edge from $p$ to $q$) replaced by the symbol $(p,a,q)$. That language is local because by looking at pairs of consecutive symbols we can check whether it is OK (i.e., whether the edges are consecutive). The morphism is mentioned in the answer, but I use the word "coding". This is sometimes done when considering a letter-to-letter morphism. – Hendrik Jan Mar 5 '19 at 13:26