UNIT I ASSIGNMENT

1. Construct a DFA for set of strings over {a,b} that starts with 0 and end with 10. Give the regular expression for the set of strings. 2. Construct a DFA for set of strings over {0,1} that accepts the language L=01*0. 3. Construct a DFA for set of strings over {a,b} that ends with bb. 4. Construct a DFA for set of strings over {a,b} that has aba as substring. Give its regular expression 5. Construct NFA for set of strings over {0,1} a. That has exactly one ‘0’ b. That has at least one ‘0’ c. That has at most one ‘0’ 6. Construct an Turing Machine Automata for L=0n1n which uses tape 7. Construct an Push Down Automata for L=0n1n which uses stack 8. Construct the minimized DFA for the automata given below 9. Construct the NFA for the given transition table and Find the equivalent DFA for it. 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

ASSIGNMENT 2

Word Document gave in classroom