Regular grammars

Definitions of regular grammars vary but usually it’s fairly easy to convert a grammar satisfying one definition to one satisfying another which generates the same language. I’ll use the following definitions.

A left regular grammar is a phrase structure grammar where

• each alternate in the rule for the start symbol is a single non-terminal symbol,
• the start symbol never appears on the right hand side of a rule, and
• each alternate in the rule for any other non-terminal symbol is either empty or is a single non-terminal symbol followed by a single terminal symbol.

A right regular grammar is a phrase structure grammar where

• each alternate in the rule for the start symbol is a single non-terminal symbol,
• the start symbol never appears on the right hand side of a rule, and
• each alternate in the rule for any other non-terminal symbol is either empty or is a single terminal symbol followed by a single non-terminal symbol.

A simple, but not terribly useful, language is the language of any number of x’s followed by any number of y’s. Here “any number” includes zero, so the empty string, for example, belongs to this language. A left regular grammar for this language is

%start weird

%%

weird : xxyy
      ;

xxyy  : | xxyy y | xx x 
      ;

xx    : | xx x | error y
      ;

error : error x | error y
      ;

The symbols xxyy and xx have the empty string as a possible expansion. The symbols start and error do not. The symbol error is not actually capable of generating any strings. Whenever we expand it we get another error symbol. The symbol xx can generate a string with any number of x’s, including zero. The symbol xxyy can generate any string with x’s followed by y’s.

A right regular grammar for the same language is

%start weird

%%

weird : xxyy
      ;

xxyy  : | x xxyy | y yy
      ;

yy    : | y yy | x error
      ;

error : x error | y error
      ;

A more complicated, but more interesting, example is the language of decimal representations of integers, normalised in the usual way, i.e. there are no leading zeroes except for the integer \({ 0 }\), there is at most one leading \({ - }\) sign, no \({ + }\) sign, and there is no \({ - 0 }\). We can write a right regular grammar for this language as follows:

%start integer

%%

integer : zero | pos_int | neg_int
        ;

zero    : 0 empty
        ;

empty   :
        ;

neg_int : - pos_int
        ;

pos_int : 1 digits | 2 digits | 3 digits
        | 4 digits | 5 digits | 6 digits
        | 7 digits | 8 digits | 9 digits
        ;

digits  : | 0 digits
        | 1 digits | 2 digits | 3 digits
        | 4 digits | 5 digits | 6 digits
        | 7 digits | 8 digits | 9 digits
        ;

and a left regular grammar for the same language is

integer : zero | nonzero
        ;

zero    : empty 0
        ;

nonzero : nonzero 0 | nonzero 1 | nonzero 2 | nonzero 3 | nonzero 4
        | nonzero 5 | nonzero 6 | nonzero 7 | nonzero 8 | nonzero 9
        | head 1 | head 2 | head 3 | head 4 | head 5
        | head 6 | head 7 | head 8 | head 9
        ;

head    : | empty -
        ;

empty   :
        ;

Both of these languages have both a left regular grammar and a right regular grammar. In fact every language which has a left regular grammar also has a right regular grammar and vice versa, but we’re not yet in a position to prove this.