Q $1.[10$ Points$]$ Let L be any language over an alphabet $\backslash$Sigma $.$ Prove or disprove L

$+$ is nite

only if L $=..$

Q $2.[15$ Points$]$ Draw a DFA for the language over input alphabets $\backslash$Sigma $=\{0,1\}$ that accepts

strings a$)$ starting with $`1\text{'},$ b$)$ ending with $10,$ c$)$ starting with $1$ and ending with $10.$

Q $3.[20$ Points$]$ Let $\backslash$Sigma $=\{0,1\}.$ For each of the following languages design a DFA with

minimal number of states that accept the language.

i$)$ Draw a DFA that accepts the string $10$ or $010.$

ii$)$ Draw a DFA that accepts all strings but $001.$

$1$

Q $4.[15$ Points$]$ Design a DFA that accepts all unsigned binary integers that are less than

$8.$

Examples: $11,00001,101,...$

Q $5.[15$ Points$]$ Design a DFA that accepts all positive decimal integers divisible by $3.$

Examples: $03,12,33,999,$

Q $6.[15$ Points$]$ Let G be a grammar with the start variable S and the following productions:

S $->$ aA $|\backslash$lambda

A $->$ bbS

i$)$ Give a simple description of the language L$($G$)$ generated by grammar G above.

ii$)$ Show a derivation of the string w $=$ abbabb from G$.$

iii$)$ Suppose L $=\{$w : w in L$($G$)$ and $|$w$|<=10\}.$ What is L

R$,$ the reverse of L$?$

Q $7.[10$ Points$]$ Design a DFA that accepts every string w over the alphabet $\{$a$,$ b$,$ c$\}$ in

which no two consecutive symbols are the same.