Chomsky Hierarchy of Languages:

Type 0:  Regular Expressions, Regular Grammars, Finite Automata

Type 1:  Context-Free Languages, Context-Free Grammars, Pushdown Automata

Type 2:  Context-Sensitive Languages, Context-Sensitive Grammars, ?

Type 3:  Recursively Enumerable languages, Unrestricted Grammars, Turing Machines.


An alphabet is a non-empty set.  Its members are called the characters, symbols, or letters of a language.

A string is a finite sequence of characters.  abc is not the same as acb, although both are strings of length 3.  The empty string is a thing.  It's usually represented by a Greek epsilon.  (However, I have a Greek omega used as well.)

A language is a set of strings over a particular alphabet.  A set can be empty.  If a set is empty, we use the Greek letter phi to express this.

Notice that phi and epsilon do not mean the same thing.  At all.  Phi is an empty set.  Epsilon is an empty string.

So if our alphabet is {a,b,c,d,e}.  Some possible languages are:

{a,ab,abc}

{a,aa,aaa,aaaa,aaaaa,aaaaaa,...}

the set of all strings with an equal number of a's b's and c's.

the set of n a's followed by n b's for any n greater than or equal to zero:  epsilon, ab, aabb, aaabbb, etc.

{epsilon}

phi

Sometimes if a language contains only one string (e.g. {abc}, we might abuse notation and refer to the language as "abc" even though "abc" is technically a string, not a language.

We sometimes use epsilon to refer to the language containing only the empty string.  In this way, epsilon refers to a language containing one string:  the empty string.  Phi refers to the set containing no strings.