Formal Languages and Logic/Finite state automata

Definition (deterministic finite state automaton):

A deterministic finite state automaton (DFA for short) is a quintuple $A=(Q,\Sigma ,\delta ,q_{0},F)$, where $Q=\{q_{1},\ldots ,q_{n}\}$ is a finite set, $\Sigma$ is a finite alphabet, $\delta :Q\times \Sigma \to Q$ is a function, $q_{0}\in Q$, and $F\subseteq Q$.

Definition (state):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then a state of $A$ is an element of $Q$.

Definition (initial state):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then the initial state of $A$ is $q_{0}$.

Definition (transition function):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then $\delta$ is the transition function.

Definition (accepting state):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then an accepting state is an element of $F$.

Proposition (every accepting state is a state):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then every accepting state of $A$ is a state.

Proof: This is because $F\subseteq Q$. $\Box$

Definition (generalized transition function):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a deterministic finite state automaton. Then the generalized transition function $\delta ^{*}:Q\times \Sigma ^{*}\to Q$ is the function defined on $\Sigma *$ by induction on word length as thus:

1. for a singleton word $a\in \Sigma$, $\delta ^{*}(q,a):=\delta ((q,a))$
2. whenever $w=a_{1}a_{2}\cdots a_{n}\in \Sigma ^{*}$, then $\delta ^{*}(q,w):=\delta (\delta ^{*}(q,a_{1}a_{2}\cdots a_{n-1}),a_{n})$

Definition (language accepted by a deterministic finite state automaton):

Let $A=(Q,\Sigma ,\delta ,q_{0},F)$ be a finite state automaton. The language accepted by the deterministic finite state automaton by $A$ is defined to be

$L(A):=\{w\in \Sigma ^{*}|\delta ^{*}(q_{0},w)\in F\}$.

Theorem (finite state automata accept precisely regular languages):

Whenever $A=(Q,\Sigma ,\delta ,q_{0},F)$ is a finite state automaton, the language accepted by $A$ is regular. Whenever $L$ is a regular language, there exists a finite state automaton that accepts it.

Proof: Let first $A=(\Sigma ,Q,\delta ,q_{0},F)$ be a finite state automaton. Define a Chomsky grammar $G=(\Sigma ,N,P,S)$ as follows: $N=Q$, $S=q_{0}$ and the productions shall be given by

${\displaystyle }$ $\Box$