Exercises — Finite automata — DFA - formal definition (5-tuple), state diagrams

This is pure reading of the 5-tuple — no computation. (a) $|Q|=3$ states. (b) The start state is always $q_0$ (the third-listed component after $Q$ and $\Sigma$). Here $q_0$. (c) $F=\{q_2\}$, so the only accepting state is $q_2$. (d) Look up the row for $(q_1,b)$: $\delta (q_1,b)=q_2$.

(a) The start state is $S_0$ — it is the one with an arrow coming from nowhere (the free arrow on the left pointing into it). (b) The accepting state is $S_1$ — it is drawn as a double circle, which means $S_1\in F$. (c) Follow the labelled arrows: the arrow leaving $S_0$ labelled 1 lands on $S_1$, so $\delta (S_0,1)=S_1$. The arrow leaving $S_1$ labelled 0 lands on $S_0$, so $\delta (S_1,0)=S_0$.

We apply $\delta$ one symbol at a time — this is the recursion $\hat{\delta }(q,xa)=\delta (\hat{\delta }(q,x),a)$ unrolled left to right.

So $\hat{\delta }(q_0,abba)=q_1$. Since $q_1\notin F$ (only $q_2$ accepts), $M$ rejects $abba$.

(a) Trace $aab$: $q_0\stackrel{a}{\to }{q}_1\stackrel{a}{\to }{q}_1\stackrel{b}{\to }{q}_2$. End $q_2\in F$ ⇒ accepted. (b) For $\epsilon$ there is nothing to read: by the base case $\hat{\delta }(q_0,\epsilon )=q_0$. Is $q_0\in F$? No — $F=\{q_2\}$. So $\epsilon$ is rejected. (A DFA accepts $\epsilon$ iff its start state is accepting.)

Notice what each symbol does. A 1 is always a self-loop: $\delta (p_i,1)=p_i$ for every $i$. So 1s never change the state — they are ignored. A 0 steps you forward one place around the cycle $p_0\to p_1\to p_2\to p_0$.

So the state you end in equals (number of 0s read) mod 3: $p_0$ means "count of 0s is $\equiv 0$", $p_1$ means "$\equiv 1$", $p_2$ means "$\equiv 2$".

Accept iff you end in $p_0=F$. Therefore $L(M)=\{w\in \{0,1{\}}^{\ast }:\#0(w)\equiv 0(\mathrm{mod}3)\},$ in words: strings whose number of 0s is a multiple of 3 (0, 3, 6, ... zeros). Check $\epsilon$: it has zero 0s, and $0$ is a multiple of 3, and indeed $q_0=p_0\in F$ — consistent. ✓

From $q_0$, reading $b$ gives $\delta (q_0,b)=q_0$ — a self-loop. So reading any number of $b$s from $q_0$ leaves you at $q_0$: $\hat{\delta }(q_0,bbbb)=q_0$. Since $q_0\notin F$, $M$ rejects $bbbb$. (In fact $M$ rejects any string of $b$s only, because a b never moves you off $q_0$ once you're there.)

What must I remember? Only how close I am to completing an ab. Three situations:

• $s_0$ = "I have not just seen an a that could start ab, and I've not yet seen ab."
• $s_1$ = "the last symbol was an a — one b away from success."
• $s_2$ = "I have already seen ab somewhere — success is locked in forever."

Transitions (reason each one):

• $\delta (s_0,a)=s_1$ (an a arms us), $\delta (s_0,b)=s_0$ (a lone b does nothing).
• $\delta (s_1,a)=s_1$ (another a — still armed, last symbol is a), $\delta (s_1,b)=s_2$ (a then b = success!).
• $\delta (s_2,a)=s_2$, $\delta (s_2,b)=s_2$ (once found, ab can't un-happen — $s_2$ is a trap of the good kind).

Tuple: $Q=\{s_0,s_1,s_2\}$, $\Sigma =\{a,b\}$, start $s_0$, $F=\{s_2\}$.

Sanity trace $w=aab$: $s_0\stackrel{a}{\to }{s}_1\stackrel{a}{\to }{s}_1\stackrel{b}{\to }{s}_2$. End $s_2\in F$ ⇒ accepted. ✓ ($aab$ contains ab.) Sanity trace $w=ba$: $s_0\stackrel{b}{\to }{s}_0\stackrel{a}{\to }{s}_1$. End $s_1\notin F$ ⇒ rejected. ✓ (ba has no ab.)

Two independent facts to track:

• parity of length — even (needed) vs odd. Every symbol flips it.
• last symbol — was it 1? Only a final 1 should be accepted.

Because the last symbol fact is only checked at the end, we fold it into the states. Track a pair (length-parity, last-symbol). Use states $E_{\text{start}},E_1,E_0,O_1,O_0$ where the letter is length parity ($E$=even, $O$=odd) and the subscript is the last symbol; $E_{\text{start}}$ is the fresh state before any symbol.

Transitions (each symbol flips parity and records itself as last symbol):

• From $E_{\text{start}}$: 0$\to O_0$, 1$\to O_1$.
• From $E_0$/$E_1$: 0$\to O_0$, 1$\to O_1$.
• From $O_0$/$O_1$: 0$\to E_0$, 1$\to E_1$.

Accept states: we need even length and last symbol 1, i.e. $F=\{E_1\}$.

• $\epsilon$: stays in $E_{\text{start}}$, which is not in $F$ ⇒ rejected. Correct, since $\epsilon$ has no last symbol 1.
• Trace $11$: $E_{\text{start}}\stackrel{1}{\to }{O}_1\stackrel{1}{\to }{E}_1\in F$ ⇒ accepted (length 2 even, ends in 1). ✓
• Trace $10$: $E_{\text{start}}\stackrel{1}{\to }{O}_1\stackrel{0}{\to }{E}_0\notin F$ ⇒ rejected (ends in 0). ✓

Tuple: $Q=\{E_{\text{start}},E_1,E_0,O_1,O_0\}$, $\Sigma =\{0,1\}$, start $E_{\text{start}}$, $F=\{E_1\}$.

We induct on the length of $y$, because $\hat{\delta }$ is defined by recursion peeling one symbol off the right.

Base case $|y|=0$, i.e. $y=\epsilon$. Then $xy=x\epsilon =x$, so the left side is $\hat{\delta }(q,x)$. The right side is $\hat{\delta }(\hat{\delta }(q,x),\epsilon )$, which by the base rule $\hat{\delta }(p,\epsilon )=p$ equals $\hat{\delta }(q,x)$. Both sides equal — base holds.

Inductive step. Assume the claim for all strings of length $n$; let $y=za$ with $|z|=n$ and $a$ a single symbol. $\hat{\delta }(q,x(za))=\hat{\delta }(q,(xz)a)(\text{concatenation is associative})$ $=\delta (\hat{\delta }(q,xz),a)(\text{recursive rule of }\hat{\delta })$ $=\delta (\hat{\delta }(\hat{\delta }(q,x),z),a)(\text{induction hypothesis on }z)$ $=\hat{\delta }(\hat{\delta }(q,x),za)(\text{recursive rule, read backwards})$ $=\hat{\delta }(\hat{\delta }(q,x),y).$ This closes the induction, so the identity holds for all $x,y$. $■$

Why we care: this is the formal justification for "feed $x$, land in some state, then continue with $y$ as if starting fresh from there" — the reasoning you already used informally in every trace.

Let $w=a_1{a}_2\cdots a_m$ with $m\ge n$ be accepted, and list the states visited: $r_0=q_0,r_1=\hat{\delta }(q_0,a_1),\dots ,r_m=\hat{\delta }(q_0,w)\in F.$ That is $m+1\ge n+1$ states in the sequence $r_0,\dots ,r_m$. But there are only $n$ distinct states in $Q$. By the pigeonhole principle (more items than boxes ⇒ two items share a box), two of these visited states are the same: say $r_i=r_j$ with $i<j$.

The substring $a_{i+1}\cdots a_j$ takes the machine from $r_i$ back to the same state $r_j=r_i$ — a loop. Call this loop-piece $y$ (with $|y|=j-i\ge 1$). Write $w=xyz$ where $x=a_1\cdots a_i$ and $z=a_{j+1}\cdots a_m$.

Now use Exercise 5.1: from $q_0$, reading $x$ lands at $r_i$; reading $y$ returns to $r_i$; so reading $y$ any number of times $y^k$ still returns to $r_i$; then $z$ finishes at $r_m\in F$. Hence $\hat{\delta }(q_0,x{y}^{k}z)\in F\text{for every }k=0,1,2,\dots$ Since $|y|\ge 1$, the strings $x{y}^{k}z$ have strictly increasing length — infinitely many distinct accepted strings. $■$

L1 you learned to read a machine (find start via the free arrow, accept via double circles). L2 you learned to run it (trace every symbol, judge only the final state). L3 you learned to reverse-engineer the language a machine recognizes. L4 you learned to build a machine from a spec, always testing $\epsilon$. L5 you learned to prove things about all DFAs — composition of $\hat{\delta }$ and the pigeonhole loop that seeds the Pumping Lemma. Related roads from here: NFAs, subset construction, Regular expressions, and Lexical analysis / tokenizers.