CS250 at CCUT Week 3: Theory of Computation Introduction

Click here to see this week's lecture notes

Prove that the following languages are regular by constructing a DFA that recognizes them.

$L_1$ = $\{s | s$ is a binary representation of a multiple of 5 $\}$ , $\Sigma = \{0, 1\}$
$L_2$ = $\{s | s$ contains an odd number of 1s and an odd number of 0s $\}$ , $\Sigma = \{0, 1\}$
$L_3$ = $\{s | s$ contains three conscutive 1s $\}$ , $\Sigma = \{0, 1\}$
$L_4$ = $\{s | s$ 's tenth symbol from the left end is a $1\}$ , $\Sigma = \{0, 1\}$
$L_5$ = $\{s | s$ is an even number represented in base 3 $\}$ , $\Sigma = \{0, 1, 2\}$
$L_6$ = $\{s | s$ contains an even number of $0$ s or exactly three $1$ s $\}$ , $\Sigma = \{0, 1\}$