Quick Overview of Formal Grammars

Grammars are rule-based descriptions of formal languages. A grammar (at least for JFLAP) specifies substitution rules by which any string in a given language can be generated from a certain input string of terminal and/or nonterminal characters. Each class of grammars corresponds to a particular class of langauges and a particular class of automata that accept it. Here is a listing of grammars and their corresponding languages.

Grammar Language Automata
Regular Grammars Regular Languages Finite Automata
Context-free Grammar Context-free Language Push-Down Automata
Unrestricted Grammar Recursively Enumerable Languages Turing Machine
These grammars are listed in order from least powerful to most powerful, where we define a more powerful grammar as one which can accomplish all the tasks that a less powerful grammar can accomplish, as well as tasks that a less powerful grammar cannot.

Regular Grammars

Regular grammars are either left-linear or right-linear.
A right-linear grammar is a grammar in which all substitution rules are of the forms: 

    {A}\rightarrow{xB}
    
    {A}\rightarrow{x}
where \inline {A}, {B} are nonterminal symbols, and \inline {x} is zero or more terminal symbols.
A left-linear grammar is a grammar in which all subsitution rules look like: 
    {A}\rightarrow{Bx}
    
    {A}\rightarrow{x}
with \inline {A}, {B}, {x} defined as above.
Put another way, regular grammars are grammers with two constraints. The left side must be a single nonterminal symbol, and the right side must have a specific form (a single nonterminal on the left or right of an arbitrary number of terminal symbols).
Regular grammars are accepted by finite automata.

Context-free Grammar

These more powerful grammars are similar to regular grammars except the right-hand side is entirely unconstrained. All substitution rules have the form: 

    {A}\rightarrow{x}
where \inline {A} is a nonterminal symbol, and \inline {x} is zero or more terminal or nonterminal symbols.
The term context-free refers to the fact that the left hand side is a single nonterminal symbol, so it can be substituted with the right-hand side without any regard to where in the sentence it is. Context-free grammars are accepted by push-down automata. A special subclass, called deterministic context-free grammars, can have an efficient parser written for them.

Unrestricted Grammar

Unrestricted grammars are those accepted by Turing machines, and they are unrestricted in the sense that substitution rules can take any form. The only exception is that the left-hand side of the rule cannot be the empty string.