1. Derive the Regular Expressions a) Language having all words that do not end at a double letter over ? = { a b} b) Even- Even language over ? = { a b} c) Language having all words that start and end with double letter over ? = { a b} d) Language having words containing only one substring ab over ? = { a b} e) Language having words with odd number of as and bs over ? = { a b} f) Language of all those string that all possible strings of as and bs of any length whatsoever over S = {a b}, excluding the null string g) Language having words with even number of as and odd no of bs over ? = { a b} 2. Build Transition Table and Finite State Automata a) Build a machine that accepts the language of all words starting and ending with different letter over the alphabet S = {a b} b) Language having all words that at least one double letter over ? = { a b} c) Build a machine that accepts the language of all words containing odd number of as and odd number of bs d) Build a machine that accepts the language of all words containing a triple letter, either aaa or bbb, and only those words e) Build a machine that accepts all words or a*b* 3. Build Nondeterministic Finite State Automata a) An NFA that accepts the language of all words over the alphabet S = {a b} having word ending with aba b) An NFA that accepts the language of all words with an odd number of as or an even number of bs over the alphabet S = {a b} c) An NFA that accepts the language of all words with an even number of as or an odd number of b;s over the alphabet S = {a b} d) What is Differences between NFA and TG e) What is Differences between DFA and NFA f) Define the Pigeonhole Principle? g) Length of string and Null string? h) Kleene stare closure and Plus closure operator? 4. Build Moore machine Good Luck a) That knowing exactly how many times the substring aab occurs in a long input string. b) That knowing exactly how many times the substring bab occurs in a long input string. 5. Build TG a) for the language that all words containing at least one double letter over ? = { a b} b) for the language that all words containing an even number of as and an even number of bs, including the null string ?. 6. Build Context free Grammar a) for the language that all words with a double a in them somewhere. Or (a + b)* aa (a + b)* b) for the language L= {a nb ma n where n>0, m>0} c) for the language L= {a nb mc md 2n where n>0, m>0} 7. Build Push Down Automata a) L = {a n b 2n+1 for n = 1; 2; 3; } b) L = {a n b n c 2n for n = 1; 2; 3; } c) L = {a nb n for n = 1; 2; 3; } d) L = {a m b n c m+n for n and m = 1; 2; 3; } e) L = {a n c b 2n for n = 1; 2; 3; where c is an arbitrary letter}

Attachments:

Assignment-02....pdf