Q$1$: $(15$ points$)(25$ minutes$)$ DFA, NFA, and $-$NFA

Consider the alphabet ${\displaystyle \underset{?}{\overset{?}{}}}=\{0,1\},$ and the regular expression $RE=0^{*}+(10{)}^{*}+101.$

Design a DFA that accepts this language.

Design an NFA that accepts this language.

Design an $-$NFA that accepts this language using the rules we covered in our

lectures. Q$2$: $(10$ points$)(20$ minutes$)$ Context$-$Free Grammars

Design a CFG that accepts the language $\{0^m{1}^n|m>n\}.$ Examples

$,...)$

Find the leftmost derivation of these two strings $0000$ and $000011$

Draw the parse tree of these two strings $00011$ and $00000$

Is this language regular or not? Prove your answer. Q$3$: $(10$ points$)(20$ minutes$)$ Properties of CFG

Given the following CFG:

$SAB$

$ABC|0$

$BAC|1$

$C0|1$

Prove that the language of this CFG is not empty.

Test the membership of the following two strings using CYK Algorithm $($show all of

your steps$)$:$-$

$11111$

$01100$ Q$4$: $(10$ points$)(15$ minutes$)$ Turing Machines

Giving the following TM

Use TM ID's to show the movements of the following two strings and explain why it

accepts or rejects.

$10$#$10$: q$101$#$01+....$

$11$#$000$: q$100$#$01...-$

What does this TM do$?$ explain how?