Deterministic Finite Automaton

A deterministic finite automaton, short DFA, is a finite-state machine that can be in one of a finite number of states at any given time. It can only move from one state to another by following a set of rules called transitions. The deterministic property means that the DFA will always make the same transition to the same state, given the same input, there is no stochastic element to the machine, i.e. there is only one path to follow.

DFAs are used to solve decision problems, such as deciding whether a given string is a member of a language or not.

Importantly DFAs work in real time and without any memory or variables. They read the input string character by character and make decisions based on the current state and the read character. Once the last character of the input string has been read, the DFA will either accept or reject the input string based on the current state.

Notation

States, transitions, and final states also called configurations and impulses? accepted or rejected states.

Difference of configuration and state?

As a graph

Formal Definition

Formal definition of a DFA

as a table

Configurations

Current state of the DFA and the remaining input

Start and end configurations.

Transition Functions

transition notation looks funny, can also somehow denote that there is a transition from one state to another without a direct connection.

Language of a DFA

Language of a DFA

Can define regular languages with DFAs

Classes

States can be grouped somehow? this can then also be used in the design.

Using this and its properties can also define accepting regular language?

Designing a DFA

in the book he uses the classes?

Garbage State

Modular Design

From the slides?