### Some Formal Definitions

#### A Deterministic Finite Automata (DFA) is

- A set called “states”
- A set called “symbols”
- A function
- A designated state called the start point
- A subset called the “accepting states”.

The DFA is then often referred to as the ordered quintuple .

#### Defining how strings act on DFAs.

Given a DFA, , a state , and a string , we can define like so:

- If only has one symbol, we can consider to be the symbol and define to be the same as if we considered as the symbol.
- If , where and , then .

And in this way, we have defined how DFAs can interpret strings of symbols rather than just single symbols.

#### The language of a DFA

Given a DFA, , we can define “the language of “, denoted , as .

### Some Examples, Maybe?

#### Example 1:

Let’s construct a DFA that accepts only strings beginning with a 1 that, when interpreted as binary numbers, are multiples of 5. So some examples of strings that would be in are 101, 1010, 1111

### Some More Formal Definitions

#### A Nondeterministic Finite Automata (NFA) is

- A set called “states”
- A set called “symbols”
- A function
- A designated state called the start point
- A subset called the “accepting states”.

The NFA is then often referred to as the ordered quintuple .

#### Defining how strings act on NFAs.

Given an NFA, , a collection of states , and a string , we can define like so:

- If only has one symbol, then we can consider to be the symbol and define .
- If , where and , then .

And in this way, we have defined how NFAs can interpret strings of symbols rather than just single symbols.

### Maybe in another post, we’ll get past the definitions!

Advertisements