next up previous
Next: Problem 2 - Cache Up: Information Science I Previous: Information Science I

Problem 1 - Finite Automaton

For a string $ x=x_{n-1}\cdots x_1 x_0 \in \{0,1\}^*$ $ (x_i\in\{0,1\},i=0,\dots,n-1)$, we define an integer $ [x]$ by $ [x] = x_{n-1}2^{n-1} + \cdots + x_12^1 + x_02^0$, where $ [\epsilon] = 0$. Show that the language

$\displaystyle L=\{x\in\{0,1\}^*\;\vert\;[x]=3n\;\hbox{for some integer}\;n\geq 0\}$

is accepted by a finite automaton.




Reynald AFFELDT
2000-06-08