Consider the regular expression (dd* U db)d and let L be the language over (b,d) expressed...

  

Transcribed Image Text:

Consider the regular expression (dd* U db)d and let L be the language over (b,d) expressed by this r.e. a) Using the construction regular expression to NFA, draw the NFA one obtains from dd*. I want you to separately draw the NFAs for d and for d". Then use those two drawing to construct the NFA for dd". (I'm not asking you construct the entire NFA for (dd* U db)d in this question. So please just do dd") b) Draw a state diagram for the simplest possible NFA you can think of that recognizes the language L (i.e. the language described by (dd* U db)d). Be sure to convince yourself that your NFA actually works, to avoid losing points for an incorrect answer. c) Starting with your NFA from Part b and using the construction NFA to DFA, draw the state diagram for a DFA that recognizes L. Make sure you label the states as sets of states from your NFA. And remember: It's not a DFA unless there is an applicable transition from every state on every symbol! Consider the regular expression (dd* U db)d and let L be the language over (b,d) expressed by this r.e. a) Using the construction regular expression to NFA, draw the NFA one obtains from dd*. I want you to separately draw the NFAs for d and for d". Then use those two drawing to construct the NFA for dd". (I'm not asking you construct the entire NFA for (dd* U db)d in this question. So please just do dd") b) Draw a state diagram for the simplest possible NFA you can think of that recognizes the language L (i.e. the language described by (dd* U db)d). Be sure to convince yourself that your NFA actually works, to avoid losing points for an incorrect answer. c) Starting with your NFA from Part b and using the construction NFA to DFA, draw the state diagram for a DFA that recognizes L. Make sure you label the states as sets of states from your NFA. And remember: It's not a DFA unless there is an applicable transition from every state on every symbol!