Regular grammar

From Wikipedia, the free encyclopedia

In computer science a right regular grammar (also called right linear grammar) is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms:

  1. A → a - where A is a non-terminal in N and a is a terminal in Σ
  2. A → aB - where A and B are in N and a is in Σ
  3. A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0.

In a left regular grammar (also called left linear grammar), all rules obey the forms

  1. A → a - where A is a non-terminal in N and a is a terminal in Σ
  2. A → Ba - where A and B are in N and a is in Σ
  3. A → ε - where A is in N and ε is the empty string.

An example of a right regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists of the following rules

S → aS
S → bA
A → ε
A → cA

and S is the start symbol. This grammar describes the same language as the regular expression a*bc*.

A regular grammar is a left regular or right regular grammar.

[edit] Introduction

The regular grammars describe exactly all regular languages and are in that sense equivalent to finite state automata and regular expressions. Moreover, the right regular grammars by themselves are also equivalent to the regular languages, as are the left regular grammars.

Every regular grammar is a context-free grammar. However, not every context-free grammar is a regular grammar. Moreover, there are nonregular (but still context-free) languages which use only right and left regular productions; for example, the paradigmatic context-free language with strings of the form aibi is generated by the grammar G with N = {S, A}, Σ = {a, b}, P with the rules

S → aA
A → Sb
S → ε

and S being the start symbol. Note that this grammar has both left-regular and right-regular rules and is therefore not regular any more.

Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.

[edit] See also

Automata theory: formal languages and formal grammars
Chomsky
hierarchy		 Grammars Languages Minimal
automaton
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
n/a Indexed Indexed Nested stack
n/a Tree-adjoining etc. (Mildly context-sensitive) Embedded pushdown
Type-2 Context-free Context-free Nondeterministic pushdown
n/a Deterministic context-free Deterministic context-free Deterministic pushdown
Type-3 Regular Regular Finite
n/a Star-free Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it,
and any automaton in each category has an equivalent automaton in the category directly above it.