automata – what is it?

the term "automata" is derived from the greek word "αὐτόματα" which means "self-acting". 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, ∑, δ, q₀, 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.

• q₀ is the initial state from where any input is processed (q₀ ∈ 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 −

  • if s = ‘cabcad’, |s|= 6

  • 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 − ∑* = ∑₀ ∪ ∑₁ ∪ ∑₂ ∪……. 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 − ∑⁺ = ∑₁ ∪ ∑₂ ∪ ∑₃ ∪…….

  ∑⁺ = ∑* − { λ }

• 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, aa, ba, bb }