Basic Notions

An alphabet is any finite set of symbols

e.g: {0,1}, {a, b, c, ..., g}

An string is any finite sequence of symbols from a given alphabet

e.g. 0111000 (from the binary alphabet {0,1}), empty string $\epsilon$

A language is a set of strings over a given alphabet

e.g. the empty language $\empty$ and

A computational device is a mechanism that inputs a string and accepts or rejects it

Deterministic Finite Automata

• Choose an alphabet
• Draw states
• Choose start state
• Choose the accept state
• Draw the transitions (out of every state on every symbol)

The language for a DFA is the set of all strings it accepts

Designing DFAs

First example, $\empty$