Lecture: Overview $-$ Introduction

$1.$ a$,$ b in N $($positive integers$),$ prove that: a mod b $=$ b mod a iff a $=$ b $(20$ points$)$

Lecture: Overview $-$ Introduction

$2.$ Prove or disapprove that: If a$,$ b in Z $($integers$),$ then a$24$b $!=2(20$ points$)$

Lecture: DFA $$ NFA

$3.(20$ points$)$ Please give the state diagram of a DFA for the language given. In all parts, $\backslash$Sigma $=\{$a$,$ b$\}.$

$(1)\{$w$|$ w has an even number of a$$s$\}$

$(2)\{$w$|$ w has one or two b$$s$\}$

$(3)\{$w$|$ w has even length$\}$

$(4)\{$w$|$ w has an odd number of a$$s$\}$

Your solution should be a DFA solution.

Lecture: RL$-$RE

$4.$ Give regular expressions that describe the languages. In all parts, the alphabet is $\{0,1\}.(20$ points$)$

For the correct format, please check our examples in slides and use the following symbols: $0,1,,*,(),$ U$.$

Other formats like this $^1(0+1)*$$ will not be graded.

a$.\{$w$|$ w starts with $0$ and has an odd length$\}$

b$.\{$w$|$ w starts with $1$ and has an even length$\}$

c$.\{$w$|$ w contains at least two $0$s$\}$

d$.\{$w$|$ w contains at most one $1\}$

Lecture: NRL

$5.(20$ points$)$ Let B $=\{1$ky$|$ y in $\{0,1\}$ and y contains at least k $1$s$,$ for k $>=1\}.$ Show that B is a regular language.

Let C $=\{1$ky$|$ y in $\{0,1\}$ and y contains at most k $1$s$,$for k$>=1\}.$ Show that C isn$$t a regular language.