Theory of Computation
Please read the concept and answer the first question
Background on GNFAs: A GNFA (generalized NFA) is an NFA that has the following properties (you can read more about these in Section 1.4 of the Sipser book) (a) Each transition is labeled with a regular expression, not just a single symbol (b) The initial state qinitial has no transitions leading to it (c) There is only one final state laccept, (d) laccept has no transitions leaving it (e) Let q be a state other than qaccept, and let qf be a state other than ginitial- Then there is a transition from q to q GNFAs are an important part of proving that for every regular language, some regular expression describes it Converting a DFA to a GNFA Given a DFA, it is always possible to create a GNFA that recognizes the same language by adding a new initial state with an e transition to the DFA's start state, a new accept state with e transitions from all of the original machine's accept states to the new accept state, and then adding transitions (including self-loops) from every non-accepting state to every other state. For example, below is a DFA (on the left) and its equivalent GNFA (on the right) Assignment # 3 Febr ruary 20, 2019 0 0,1 OU1 91 accept Ripping an internal state out of a GNFA Our goal is to reduce the GNFA to one that has just two states with one transition between them; that transition will be labeled with a regular expression that describes the same lang original DFA In the above machine, consider the subset of states that are ginitial, 91, 92. Looking at these states in isolation, the transitions between them are: uage as the OU1 0 nitial 92 Consider the ways we may transition from ginitial to q2. There are 2 paths: 1. To state qi, loop around q 0 or more times, and then to q2 2. Or, transition directly to q2 That is, a string that transitions from finitial to 92 either matches the regular expression 0*1 or the regular expression. Put together, a string that transitions from ginitial to 2 matches the regular expression (0* 1 ) U 0-0* 1 Removing qi from the GNFA requires doing this process for all transitions in the machine (for more information, see Figure 1.63 and surrounding discussion in Sipser). After qi is removed from the machine, we have the machine: initial accept Determining the equivalent regular expression Proceed as above, ripping each successive state out of the machine. For reference, the next step above (ripping out q2) results in the following regular expression for the transition from qinitial to accept: (0*1(0U 1)"e)U). This RE is equivalent to 0*10U1)*, so we have the 2-state GNFA linitial accept The regular expression labeling the single transition in this machine must describe the language of the original DFA Assignment 1. Use the above procedure to find a regular expression that describes the language of M2 from the previous homework, depicted below 1 91 42 93 0 0 0 (a) Construct a GNFA (call it No) for this machine following rules (a)-(e) above. That is, add a new initial state, a new accept state, and connect all intermediate states to one another with transitions labeled with regular expressions. Your GNFA should have 5 states, and each state (other than the accept state) should have 4 outgoing transitions (any transition labeled with the means it's a transition that didn't exist in the original machine) (b) What is the GNFA that results from ripping state q out of No? Call this machine Ni (c) What is the GNFA that results from ripping state q2 out of NM? Call this machine N2 (d) What is the GNFA that results from ripping state qs out of N2? Call this machine N3 (e) Using N3, determine a regular expression that describes the language of the original DFA Background on GNFAs: A GNFA (generalized NFA) is an NFA that has the following properties (you can read more about these in Section 1.4 of the Sipser book) (a) Each transition is labeled with a regular expression, not just a single symbol (b) The initial state qinitial has no transitions leading to it (c) There is only one final state laccept, (d) laccept has no transitions leaving it (e) Let q be a state other than qaccept, and let qf be a state other than ginitial- Then there is a transition from q to q GNFAs are an important part of proving that for every regular language, some regular expression describes it Converting a DFA to a GNFA Given a DFA, it is always possible to create a GNFA that recognizes the same language by adding a new initial state with an e transition to the DFA's start state, a new accept state with e transitions from all of the original machine's accept states to the new accept state, and then adding transitions (including self-loops) from every non-accepting state to every other state. For example, below is a DFA (on the left) and its equivalent GNFA (on the right) Assignment # 3 Febr ruary 20, 2019 0 0,1 OU1 91 accept Ripping an internal state out of a GNFA Our goal is to reduce the GNFA to one that has just two states with one transition between them; that transition will be labeled with a regular expression that describes the same lang original DFA In the above machine, consider the subset of states that are ginitial, 91, 92. Looking at these states in isolation, the transitions between them are: uage as the OU1 0 nitial 92 Consider the ways we may transition from ginitial to q2. There are 2 paths: 1. To state qi, loop around q 0 or more times, and then to q2 2. Or, transition directly to q2 That is, a string that transitions from finitial to 92 either matches the regular expression 0*1 or the regular expression. Put together, a string that transitions from ginitial to 2 matches the regular expression (0* 1 ) U 0-0* 1 Removing qi from the GNFA requires doing this process for all transitions in the machine (for more information, see Figure 1.63 and surrounding discussion in Sipser). After qi is removed from the machine, we have the machine: initial accept Determining the equivalent regular expression Proceed as above, ripping each successive state out of the machine. For reference, the next step above (ripping out q2) results in the following regular expression for the transition from qinitial to accept: (0*1(0U 1)"e)U). This RE is equivalent to 0*10U1)*, so we have the 2-state GNFA linitial accept The regular expression labeling the single transition in this machine must describe the language of the original DFA Assignment 1. Use the above procedure to find a regular expression that describes the language of M2 from the previous homework, depicted below 1 91 42 93 0 0 0 (a) Construct a GNFA (call it No) for this machine following rules (a)-(e) above. That is, add a new initial state, a new accept state, and connect all intermediate states to one another with transitions labeled with regular expressions. Your GNFA should have 5 states, and each state (other than the accept state) should have 4 outgoing transitions (any transition labeled with the means it's a transition that didn't exist in the original machine) (b) What is the GNFA that results from ripping state q out of No? Call this machine Ni (c) What is the GNFA that results from ripping state q2 out of NM? Call this machine N2 (d) What is the GNFA that results from ripping state qs out of N2? Call this machine N3 (e) Using N3, determine a regular expression that describes the language of the original DFA
