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