Saturday, October 5, 2013

Finite Automata

Few notes from my reading of Introduction to the Theory of Computation chapter 1.1:

Definition of Finite Automaton

A finite automaton is a 5-tuple (Q, Σ, δ, q0, F), where
  1. Q is a finite set called the states,
  2. Σ is a finite set called the alphabet,
  3. δ: Q × Σ → Q is the transition function,
  4. q0 ∈ Q is the start state, and
  5. F ⊆ Q is the set of accept states (final states).

Definition of Regular Language

A language is called a regular language if some finite automaton recognizes it.


Definition of Regular Operatioins

Let A and B be languages. We define the regular operations union, concatenation, and start as follows.
  • Union: A ∪ B = { x | x∈A or x∈B }
  • Concatenation: A ○ B = { xy | x∈A and y∈B }
  • Star: A* = {x1 x2 ... xk | k ≧ 0 and each xi ∈ A}
Note:
  • the concatenation operation attaches a string from A in front of a string from B in all possible ways to get the strings in the new language
  • the star operation is a unary operation instead of a binary operation
  • because "any number" includes 0 as a possibility, the empty string ε is always a member of A*, no matter what A is