Local languages

Abstract

A language which has only a finite number of primitive roots is like a finite-dimensional vector space having a finite basis. Such a language is called a local language. The purpose of this paper is to study some of the algebraic properties of local languages. We show that every local context-free language is regular which generalizes the well-known fact that every context-free language over one letter alphabet is regular. We also derive that a skinny context-free language is local or not is decidable.

Keywords:

• Formal language
• context-free language
• regular language
• combinatorics of words

C.R. Categories:

• F.4.3