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 !


(1) Indeed. Every regular [=rational] language is the morphic image of a local [=2-testable] language.

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you but I am sorry I didn’t understand at all your explanation, where is the local automata here ? What is the morphism you are considering... $\endgroup$ – Strange_questionnn Mar 5 '19 at 8:57
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Mar 5 '19 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.