Deterministic finite automata

A deterministic finite Automata $M$ sets limits on its properties and makes sure everything is finite.

formal construction

in particular, $M$ must have a finite set $Q$ of states, a finite Alphabet $\Sigma$, an initial state $q_0\in Q$, a subset of accepting states $F\subseteq Q$, and a transition function $\delta$.

the transition function $\delta$ is defined as $\delta :Q\times \Sigma \to Q$. this means if $M$ reads symbol $\sigma$ in state $q_n$, the resulting state can be determined by calculating $\delta (q_n,\sigma )$.

language

the set of strings $w$ over $\Sigma$ such that $M$ accepts $w$ is denoted as $L(M)$. if there exists a Language $A$ such that $L(M)=A$, that language is said to be regular.

syntax versus semantics

when we want to talk about the syntax of $M$, this involves a listing of its states $Q$, alphabet symbols, transitions, initial state, and accepting states. we can then ask syntactic questions like how many states does $M$ have, or if the set of final states is empty.

the semantics of $M$ is talking about the language $L(M)$. here, $L(M)$ is mathematical set that captures what $M$ can compute/solve. we can then ask semantic questions like if a particular string $w$ is in $L(M)$, of if the set $L(M)$ is empty.

this distinction holds in all of computer science. the syntax of a program is the text corresponding to its code. the semantics of a program is the mathematical function it computes.

Proving its correctness

given a Language $A$ described by a mathematical constraint, and a DFA $M$, to prove that $L(M)=A$:

1. find precise descriptions of mutually disjoint sets $A_0,A_1,A_2,\dots ,A_n$ of strings that take the machine from initial state to each corresponding state in $Q$. this is in your IH.
2. language $A$ should be union of sets corresponding to final states. for every state, we want to create a mathematical definition that allows us to get there. obviously, they should be mutually exclusive from other states.
3. prove by induction on string $w$: for all $w$, ${\delta }^{\ast }(q_0,w)=q_i$ if $w$ is in set $A_i$, for $0\le i\le n$
   1. base case is proving claim for $w=ϵ$
   2. IH is assuming that ${\delta }^{\ast }(q_0,x)=q_i$ if $x$ is in set $A_i$
   3. finally, inductive step is proving that for each $\sigma$ in $\Sigma$, it holds true that ${\delta }^{\ast }(q_0,x.\sigma )=q_i$ if $x.\sigma$ is in set $A_i$. we do a case-by-case analysis from here.