Languages and their generative grammars can be be classified into different cate- gories depending on the complexity of the structures of their production rules. The first category, which correspond to the simplest kind of production rules, is called regular. |