Grammar (parsing)

A grammar is a set of rules that describe a language. The rules consist of

A finite set of non-terminal symbols («variables»), typically denoated by N. The elements of this set are typically written as uppercase letters.
A finite set of terminals, disjoint from N, typically denoted by Σ. The elements of this set are typically written as lowercase letters.
A finite set of production rules, typically denoted by P
A starting symbol that is an element of N, typically denoted by S.

Types of grammars (Chomsky hierarchy)

	Grammar accepted	Language accepted	Automaton / Machine
Type 0	Unrestricted grammar	Recursively enumarable language	Touring machine (Deterministic (DTM) vs Non-deterministic (NTM), the default being DTM
Type 1	Context sensitive grammar	Context sensitive language	Linear bounded automata (LBA) (also deterministic vs. non-deterministic)
Type 2	Context free grammar	Context free lanuage	Push down automata (PDA), also D vs N, the default being NPDA
Type 3	Regular grammar	Regular language	Finite automata (FA), also DFA vs NFA, the default being DFA

Type 0 grammars have the most expressive power, Type 3 the least expressive power.

The expressive power of of DFAs is equal to the expressive power of NFAs. Therefore, every NFA can be converted into a DFA.

The expressive power of NPDAs is greated than the expressive power of DPDAs. Therefore, some NPDAs can't be converted into a DPDA.

The expressive power of DTMs is equal to the expressive power of NTMs.

FA: no memory needed

PDA: FA + 1 stack

TM = FA + 2 stacks

The Chomsky hierarchy is sometimes also referred to as Chomsky-Schützenberger hierarchy, after the French mathematician Marcel-Paul Schützenberger.