On Context-free Bigram Languages

Abstract

The article considers languages in the alphabet {a1,…,an}, in the words of which the proportion of all consecutive pairs aiaj is recorded. This proportion is described by the generating matrix of the language Θ. The author called such languages bigram. Natural languages have a similar property. It turns out that the properties of such languages to be empty, finite, regular, context-free or context-sensitive are verifiable by the matrix Θ. This paper examines in detail the issue of infinite context-free languages.