Deterministic Finite State Automata (DFA)

Overview

• Deterministic Finite State Automata (DFA) is the first type of machine introduced in the module.
• A DFA has a finite set of states, and its behavior is deterministic.
• At each point, the next state is determined by the current state, the symbol being read, and the transition function.
• There is no guessing; the computation follows a defined path.

Formal Definition of DFA

A DFA is defined as a 5-tuple consisting of:

1. Q: A finite set called the states.
2. Σ: A finite set called the alphabet.
3. δ: The transition function.
4. q₀: The start state.
5. F: The set of accepting states.

Components

• States (Q): Elements from the set are states of the automaton. One is the start state, and a subset are accepting states.
• Alphabet (Σ): The strings processed contain symbols from this finite set.
• Transition Function (δ): Determines the next state given a current state and a symbol.
  • Domain: Cartesian product of states (Q) and the alphabet (Σ).
  • Codomain: The set of states (Q).

Formal Description of Computation

• Computation requires a formal definition aligning with the intuition of DFA.
• Acceptance Criteria:
  • A sequence of states (r₀, r₁,..., rn) must exist such that:
    1. r₀ is the start state.
    2. For each symbol in the string, the sequence follows δ.
    3. rn is an accepting state.
• An automaton recognizes a language L if it accepts input strings belonging to L.
• If a DFA does not accept a string, it rejects it, excluding it from the recognized language.

Pictorial Representations

• DFA can be represented diagrammatically.
• States: Represented as circles.
• Transitions: Directed arrows between states, annotated with symbols.
• Start State: Arrow without a tail and without a symbol annotation.
• Accepting States: Indicated by concentric circles.

Example

• Given a DFA with a defined configuration of states and transitions:
  • Accepts strings with an odd number of 'a's and 'b's.

Exercise 1

• Determine which strings are accepted by the DFA.
• Example computations include:
  1. String "abba" is rejected.
  2. String "aabb" is rejected.
  3. String "abab" is accepted.
  4. String "baba" is accepted.