Theory of Computation

Section A

Automata

The term "Automata" is derived from the Greek word "αὐτόματα" which means "selfacting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

Formal definition of a Finite Automaton

An automaton can be represented by a 5-tuple (Q, Σ, δ, q0, F), where:

·         Q is a finite set of states.

·         Σ is a finite set of symbols, called the alphabet of the automaton.

·         δ is the transition function.

·         q0 is the initial state from where any input is processed (q0 ∈ Q).

·         F is a set of final state/states of Q (F ⊆ Q).

Related Terminologies

Alphabet

·         Definition: An alphabet is any finite set of symbols.

·         Example: Σ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.

String

·         Definition: A string is a finite sequence of symbols taken from Σ.

·         Example: ‘cabcad’ is a valid string on the alphabet set Σ = {a, b, c, d}

Length of a String

·         Definition : It is the number of symbols present in a string. (Denoted by |S|).

·         Examples: o If S=‘cabcad’, |S|= 6 o If |S|= 0, it is called an empty string (Denoted by λ or ε)

Kleene Star

·         Definition: The Kleene star, Σ * , is a unary operator on a set of symbols or strings, Σ, that gives the infinite set of all possible strings of all possible lengths over Σ including λ.

·         Representation: Σ * = Σ0 U Σ1 U Σ2 U……. where Σp is the set of all possible strings of length p.

·         Example: If Σ = {a, b}, Σ *= {λ, a, b, aa, ab, ba, bb,………..}

Kleene Closure / Plus

·         Definition: The set Σ + is the infinite set of all possible strings of all possible lengths over Σ excluding λ.

·         Representation: Σ + = Σ1 U Σ2 U Σ3 U……. Σ + = Σ* − { λ }

·         Example: If Σ = { a, b } , Σ+ ={ a, b, aa, ab, ba, bb,………..}

Language

·         Definition : A language is a subset of Σ* for some alphabet Σ. It can be finite or infinite

·         Example : If the language takes all possible strings of length 2 over Σ = {a, b}, then L = { ab, bb, ba, bb}