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

DFA & NFA

In the course "Formal Language", we learned about "DFA and NFA", and here's my study notes.

Reference

1. http://stackoverflow.com/questions/3978438/dfa-vs-nfa-engines-what-is-the-difference-in-their-capabilities-and-limitations
2. DFA http://en.wikipedia.org/wiki/Deterministic_finite_automaton
3. NFA http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

Definitions

Finite Automaton

A finite automaton is a processor that has states and reads input, each input character potentially setting it into another state.

 In my opinion, we can see this as a finite state machine.

Deterministic Finite Automaton (1943)

A finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation.

In one state at a time.

Nondeterministic Finite Automaton (1959)

A finite state machine that (1)does not require input symbols for state transitions and (2)is capable of transitioning to zero or two or more states for a given start state and input symbol.

In more than one state at a time.

Difference between DFA and NFA

• all transitions are uniquely determined
• an input symbol is required for all state transitions
• DFAs are easier to understand, but NFAs are generally smaller.