Assignment 1

1. ConstructaDFAforsetofstringsover{a,b}thatstartswith0andendwith10.Givetheregularexpression forthesetof strings. 2. Constructa DFAforsetofstrings over{0,1}thataccepts thelanguageL=01*0. 3. Constructa DFAforsetofstrings over{a,b}thatends withbb. 4. ConstructaDFAforsetofstringsover{a,b}thathasabaassubstring.Giveitsregularexpression 5. ConstructNFA forsetofstringsover {0,1} a. Thathasexactlyone‘0’ b. Thathasatleastone ‘0’ c. Thathasat mostone‘0’ 6. Constructan TuringMachineAutomataforL=0n1nwhichusestape 7. Constructan PushDownAutomataforL=0n1nwhichusesstack 8. Constructthe minimizedDFAfortheautomata givenbelow 9. Constructthe NFAforthegiventransition tableandFindthe equivalentDFAforit. States/Inputs 0 1 A A B B B A,B 10. Find the type of grammar for the following a. Aab b. AAAabB c. aAbaabbcc d. abcab