Study Notes on Deterministic Finite Automata

Deterministic Finite Automata

Overview of Deterministic Finite Automata (DFA)

• Definition: Finite automata are theoretical machines used to recognize regular languages. Conversely, any language that can be recognized by a finite automaton is categorized as a regular language.

Definition of a Deterministic Finite Automaton

• A deterministic finite automaton (DFA) can be formally defined as a 5-tuple:
  • Q: A finite set of states
  • Σ: A finite set of symbols (input alphabet)
  • δ: A transition function, mapping from Q × Σ to Q
  • q₀: An initial state belonging to the set Q
  • A: A subset of Q representing accepting states

Notes on the Definition of DFA

• Set Q: This represents a finite collection of elements, which can symbolize various states of the system (e.g., a vending machine). Examples include:

  • "Waiting for a customer to put a coin in"
  • "Have received 5 cents"

• Initial State: The example illustrates that the initial state can be defined as the state indicating readiness to receive an input, such as a coin.

• Accepting State: The accepting state is defined as the state in which the machine successfully dispenses a product (like a soda).

Transition Function

• The transition function (δ) is also known as the next state function. It determines the state the automaton will move to when it receives a specific input while in a given state (q).

  • Example: For the initial state q and input symbol a (like a nickel), the transition can indicate the state change to "have received 5 cents".

• Specification Requirement: As δ is a function, it mandates that for every state q in Q and every input symbol a in the alphabet Σ, the outputs must be clearly defined for transitions.

• Accepting Sequences: A sequence of inputs is considered accepted if the DFA ends in an accepting state when no further input is received. Otherwise, it is rejected.

Terminology and Symbols

• A DFA is often referred to simply as "finite automaton". The abbreviations FA and DFA are commonly used.

Representation of DFAs

• Transition Diagrams: DFAs are represented visually by directed graphs called transition diagrams.
  • Vertices: Represent states, illustrated as circles.
  • Arcs: Labeled transitions with input symbols.
  • An arc from vertex p to vertex q labeled with input symbol a represents the transition δ(p, a) = q.
  • Accepting States: Indicated by double circles within these diagrams.
• Transition Tables: These can be used alongside diagrams to represent transition functions in tabular form.

Examples of DFAs

Example 1

• Given:
  • Q = {0, 1, 2}
  • Σ = {a}
  • A = {1}
  • Initial State: 0
  • Transition Table:
    | State (q) | Input (a) | Next State (δ(q, a)) |
    |-----------|-----------|----------------------|
    | 0 | a | 1 |
    | 1 | a | 2 |
    | 2 | a | 2 |

Example 2

• Given:
  • Q = {0, 1, 2}
  • Σ = {a, b}
  • A = {1}
  • Initial State: 0
  • Transition Table:
    | State (q) | Input (a) | Next State (δ(q, a)) |
    |-----------|-----------|----------------------|
    | 0 | a | 1 |
    | 0 | b | 2 |
    | 1 | a | 2 |
    | 1 | b | 2 |
    | 2 | a | 2 |
    | 2 | b | 2 |

Example 3

• Given:
  • Q = {0, 1}
  • Σ = {a, b}
  • A = {0}
  • Initial State: 0
  • Transition Table:
    | State (q) | Input (a) | Next State (δ(q, a)) |
    |-----------|-----------|----------------------|
    | 0 | a | 0 |
    | 0 | b | 1 |
    | 1 | a | 1 |
    | 1 | b | 1 |

Example 4: Vending Machine

• Given:
  • Q = {0, 5, 10, 15, 20}
  • Σ = {D, N}
  • A = {15, 20}
  • Initial State: q₀ = 0
  • Transition Table:
    | State (q) | Input (a) | Next State (δ(q, a)) |
    |-----------|-----------|----------------------|
    | 0 | N | 5 |
    | 0 | D | 10 |
    | 5 | N | 10 |
    | 5 | D | 15 |
    | 10 | N | 15 |
    | 10 | D | 20 |
    | 15 | N | 5 |
    | 15 | D | 10 |
    | 20 | N | 5 |
    | 20 | D | 10 |

Constructing DFA from Regular Expressions (RE)

• DFAs can be directly constructed from given regular expressions without the need for an intermediate transition table.

Regular Expression Examples

• Example 5: R.E. = a(a + b)*
• Example 6: R.E. = (a + b)+
• Example 7: R.E. = ((a+b)(a+b))*
• Example 8: R.E. = b(a + b)*
• Example 9: R.E. = (a + b)*a
• Example 10: R.E. = a(a + b)* + b(a + b)*b
• Example 11: R.E. = a(a + b)b + b(a + b)a
• Example 12: R.E. = (a + b)*

Notes on Finite Automata

• Equivalence of Finite Automata: Two finite automata are equivalent if they recognize the same language.

  • FA1:
  • FA2:
  • FA3:

  Examples showcase how different automata can lead to the same language acceptance tooling with proper state management and transition understanding.

Conclusion: Understanding deterministic finite automata involves recognizing their structural definitions, transition dynamics, and the ways in which they map to various inputs and states, exemplified through practical scenarios like vending machines and theoretical constructs like regular expressions.