Type-3 vs. regular grammars
The past few days I've been studying some early publications of Chomsky and more precisely those dealing with the structure of language. To my surprise, I noticed that there's a prevalent misconception among the members of the wider CS community, a misconception regarding the term regular grammar. The vast majority of articles, papers and books dealing with the calculus/theory of computation keep referring to type-3 Chomsky grammars as regular grammars. Unfortunately, this is not 100% correct and may complicate things for someone willing to gain a deeper understanding of the subject. I would like to stress the fact that my purpose is not to criticize anyone, I'd just like to point out a problem regarding the use of the term regular.
It is known (and can be easily proved) that some language described by a type-3 grammar can be generated by a simple Markovian Finite State Machine (a finite automaton). The relation of regular expressions to finite automata may have probably influenced the CS community to refer to type-3 grammars as regular grammars, nevertheless this is kind of incompatible with Chomsky's writings. Formally, the definition of a regular grammar given by Chomsky is by no means related to FSMs and in fact, it is used in [1] to prove the limited generative power of the latter. To get this straight, I will start by giving the definitions of type-3 and regular grammars as given by Chomsky in [1].
G is categorized as a type-3 grammar when the following restrictions hold for all of its rules (1):
A grammar is said to be regular when (2):
Condition (2) imposes a simple restriction in the grammar. More precisely, for each nonterminal A, nonterminal B may appear only once in the left hand side of A's rules.
The difference between the two definitions lies in the following (3):
Obviously there's a fundamental difference between the two. Regular grammars cannot in general be handled by FSMs while it's trivial to construct a finite automaton that produces languages that obey the rules in (1). Definition (2) is what makes regular grammars more powerful than type-3; regular (context-free, type-2) grammars may be self-embedding (a.k.a recursive), thus allowing for more flexibility. It's very easy to prove the statement made in this paragraph using a counter example (read on).
Section 5 in [1], deals with regular grammars. According to Chomsky (theorem 5 in [1]), every type-2 grammar can be rewritten in a form consisting only of rules like those in (2). This new form, is called a regular grammar and its main characteristic is that the phrase structures (a.k.a parse trees) resulting from it have at most two children in each non-leaf node. The actual algorithm for converting a type-2 grammar to its regular equivalent consists of four steps each of which should be applied recursively until no more possible.
To sum up, according to Chomsky, regular is a special form of a type-2 grammar rewritten in form (2). On the contrary, most people refer to type-3 grammars when talking about regular grammars. Keep this in mind while studying this particular topic of mathematical logic ;)
Reading Chomsky's publications one can immediately notice that the author disregards the usage of epsilon rules in grammars. The definitions that result in the, so called, Chomsky hierarchy assume that a nonterminal A cannot be replaced by the identity element (a.k.a epsilon, null). On the contrary, the wikipedia page at [2], gives two example grammars that, in fact, cannot be categorized in accordance to the Chomsky hierarchy due to the presence of epsilon rules. Both grammars given in [2], describe the language a^nb^n; The first is context-sensitive but not type-1, the second is context-free but not type-2.
Some readers may assume that, due to their structural similarities, regular and type-3 grammars are equivalent; maybe that's why everyone keeps using these terms interchangeably. I'll show you why this is not true. Consider the type-2 grammar for the language a^nb^n, a language requiring infinite memory and thus not producible by a finite automaton, which is shown below. Recall that, strictly speaking, the grammar presented in wikipedia for this language is not type-2:
This is a type-2 grammar which can easily be converted to a regular form as shown below (4):
The dashes in the start symbol's production are the sentence markers; a notation used by Chomsky in several of his articles so I've preserved it here. Now think for a moment. We know there's no type-3 grammar that can produce the language a^nb^n but we just presented a regular grammar that is able to do so. The reader can easily verify that grammar (4) is indeed regular since it obeys the rules given in (2). Consequently, regular grammars and type-3 grammars are not equivalent. If they were, then context-free grammars and regular expressions would have the same generative power, but they don't.
-- hk
[1] "On certain formal properties of grammars", N. Chomsky, Handbook of Mathematical Psychology, Vol. 2, New York, NY, USA: Wiley (1963), p. 323-418
[2] Chomsky hierarchy on wikipedia
