A grammar is regular if and only if its rules are of the form X -> a or X -> aY, where X and Y are nonterminals and a is a terminal. Regular languages can be accepted by finite state automata. Regular languages may also be defined using regular expressions, which consist of sets of string over a finite alphabet under the operations of union, concatenation and Kleene closure.
Related categories 1
Grammars for Regular Languages
A series of pages showing that a regular grammar is either a right-linear or left-linear grammar.
The formal definition of regular expressions, also used to define regular languages.
A Wikipedia article on regular expressions with an informal discussion, a formal definition and examples.
Basic definitions of regular languages, how they are generated, closure properties, and comparison with context free languages.
This site gives a recursive definition of the class of regular languages, discusses its closure properties and gives examples.
This short chapter proves that regular languages are those accepted by finite state automata. [PDF]
Last update:December 19, 2014 at 12:54:10 UTC