Alphabets

An alphabet is a finite, non-empty set of symbols. As a convention we use the Epsilon greek letter to represent an alphabet and the first lower letters of the latin alphabet (a, b, ...) to represent symbols.

An example of the definition of an alphabet follows:

It is the alphabet composed by the symbols a, b and c.

Note that the symbols composing an alphabet doesnt have an inner structure: they are managed as atoms with independence of what they actually represents. For example we could define the following symbols:

• A letter such as t.
• A digit such as 2.
• A fruit from a relation of fruits such as apple.
• A day such as Tuesday.

Strings

A string (sometimes also called a word) is a sequence of symbols from some alphabet.

For example, given the alphabet

we can build several strings using the symbols a, b and c:

The empty string

It is possible to build a string composed by zero symbols. It is called the empty string and it is usual to represent it using the epsilon greek letter:

Note that the empty string can be defined in any alphabet.

The size of a string

The size of a string is the number of symbol positions existing in a given string.

For example, the size of the string abc is 3 (it has three positions for symbols).

We denote the size of strings using the following notation:

Concatenation of strings

Strings can be concatenated together.

Given the following strings:

we can apply concatenation to obtain:

Note that if we concatenate a string with the empty string we obtain the same string again:

In other words: the empty string is the identity operator for string concatenation.

Languages

A language is a possibly infinite set of strings from a given alphabet.

For example, consider the following language

that defines the set of all strings composed by a sequence of a and a sequence of b given that the lenght of both sequences are the same and there is at least one a and one b.

Power of an alphabet

The power of order n of a given alphabet is the language composed by all the strings of size n using the symbols from that alphabet.

For example, given the alphabet

we can define the following powers:

Note that, despite we used an identical notation, the alphabet it not the same than its first order power: in the former a and b represent symbols while in the later a and b are strings of size 1.

Closure of an alphabet

We define the transitive closure of an alphabet as:

In other words: the transitive closure of a given alphabet is the infinite language composed by the strings of any size of that alphabet (including the empty string):

We define the transitive-reflexive closure of an alphabet as:

In other words: the transitive-reflexive closure of a given alphabet is the infinite language composed by the strings of any size of that alphabet not including the empty string.

Note that any language defined on a given alphabet is a subset of the reflexive-transitive closure of that alphabet:

The empty language

The empty language is defined as

Note that the language containing only the empty string

is not the empty language: it is composed by one string.

Deterministic Finite Automata (DFA)

A deterministic finite automata (abbreviated DFA) is defined by the following quintuple:

where

• is a set of states.
• is an alphabet.
• is the initial state of the automata.
• is the transition function for the automata.
• is the subset of the accepting states for the automata.

The transition function

The transition function of a DFA is a function that accepts a symbol as its argument and return a state .

For example, consider a DFA that will process the following language:

We can define the DFA as:

where

• 
• 
• 
• is defined by:
  • 
  • 
  • 
  • 

Transition diagrams

There is a graphical (and quite intuitive) way to describe a transition function: transition diagrams.

Here is the transition diagram corresponding to the transition function described in the previous section:

Note how the final state is represented using a double circle.

Transition tables

A transition function can also be described using the following tabular representation:

Note how the initial state is represented using a and the final state is represented using a .

The extended transition function

The extended transition function of a DFA is defined by induction as:

• 
  • Basis:
  • Induction:

Lets give an example of the application of the extended transition functions, using the DFA we defined in the previous sections:

Language accepted by an automaton

Given an automata:

The language accepted by the automaton A is defined as: