# How can Chomsky hierarchy be applied to languages with alternated letters?

I have the following grammar, which I know it is regular because it can be represented by a finite state automata:

$$\begin{array}{l} \mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\ \mathrm{X} \rightarrow \mathrm{a} \mathrm{Y} \mathrm{b} \mid \mathrm{ab} \\ \mathrm{Y} \rightarrow \mathrm{b} \mathrm{X} \mathrm{a} \mid \mathrm{ba} \end{array}$$

According to Chomsky hierarchy:

Type-3 grammars generate the regular languages. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal (right regular). Alternatively, the right-hand side of the grammar can consist of a single terminal, possibly preceded by a single nonterminal (left regular).

However, I do not find the hierarchy applied to the grammar. Am I missing something?

Every regular grammar produces a regular language.

But:

Not every grammar for a regular language is regular.

In other words, a regular language can be described by any of an infinitude of grammars, some of which are regular and some not.

In this case, you can easily create either a left- or a right-regular grammar for your language. For example:

$$\begin{array}{l} \mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\ \mathrm{X} \rightarrow \mathrm{X} \mathrm{a}\mathrm{b} \mid \mathrm{ab} \\ \mathrm{Y} \rightarrow \mathrm{Y} \mathrm{b} \mathrm{a} \mid \mathrm{ba} \end{array}$$

Of course, that transformation only preserves the language parsed, not the induced parse trees.

• Thank you very much! :) Dec 4, 2020 at 17:51