Theory of Computing

1. Desion a Mealv machine that encodes words as follows: NOTE: = \{digit, alphabet\} Write the formal description of the machine 2. For ={g,b},L is the set of those words that end with different alphabets. That is to say, it does not include any words that end with gg or bb. a. Design an NFA that recognizes the strings of L and mention its formal description. b. Does the string ggbbg belong to L? Justify your answer with a sequence of transitions and explain what the sequence indicates. c. Convert the NFA into a DFA and mention its formal description. d. Does the string bbgbg belong to L? Justify your answer with a sequence of transitions using the DFA you designed and explain the sequence indicates. 3. Let L be the language of the words that include a number of the alphabet " a " that is a multiple of 4 while there can be any number of " b " and " c". NOTE: ={a,b,c} Kindly consider that zero is not a multiple of 4. a. Design a DFA that recognizes the language L and write its formal description. 4. For ={a,b}L is the set of all strings starting with an even number of a 's followed by an odd number of b 's. a. Generate the regular expression for L. b. Convert this regular expression into an NFA with -moves using the approach discussed in lecture and write its formal description