2. DFAs

Jan 13, 2022

Deterministic Finite Automata

Input tape (str)   =>  [ DFA ]  =>   Output: accept/reject

• for every state there is a transition for every symbol, in the alphabet
• machine cannot change memory, only read from it
• to accept: all input is scanned and last state is accepting
• to reject: all input is scanned and the last state is non-accepting

Formal definition

• $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ where
  • $Q$ is set of states
  • $\mathrm{\Sigma }$ is input alphabet and $ϵ\notin \mathrm{\Sigma }$ (never contains empty string)
  • $\delta$ is transition function
  • $q_0$ is initial state
  • $F$ is set of accepting states (0 or more)

Transition function

• $\delta :Q\times \mathrm{\Sigma }\to Q$
• describes the result of a transition from state $q$ with symbol $x$: $\delta (q,x)=q^{\prime }$

• can be represented as a transition table, for example:

  $\delta$	a	b
  $q_0$	$q_1$	$q_2$
  $q_1$	$q_0$	$q_2$
  $q_2$	$q_2$	$q_0$

Extended transition function

• ${\delta }^{\ast }:Q\times {\mathrm{\Sigma }}^{\ast }\to Q$
• ${\delta }^{\ast }(q,x)=q^{\prime }$
• describes the resulting state after scanning string $w$ from state $q$
• example: ${\delta }^{\ast }(q_0,abbba)=q_2$
• special case, for any state q: ${\delta }^{\ast }(q,ϵ)=q$
• in general: implies there is a walk of transitions $w={\sigma }_1{\sigma }_2...{\sigma }_k$ from q to q'

Language accepted by DFA

• $L(M)$ denotes and contains all strings accepted by M, i.e. M recognizes $L(M)$
• for a DFA, $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$   =>   $L(M)=\{w\in {\mathrm{\Sigma }}^{\ast }:{\delta }^{\ast }(q_0,w)\in F\}$
• language rejected by M: $\overline{L(M)}=\{w\in {\mathrm{\Sigma }}^{\ast }:{\delta }^{\ast }(q_0,w)\notin F\}$
• language L is regular is there is a DFA M that accepts it $L(M)=L$
• the languages accepted by DFAs form the family of regular languages