The Complexity of Finite Automata: A Comparison of DFA and NFA

When it comes to automating processes, finite automata (FAs) are often used due to their ability to recognize patterns in input data. However, when it comes to determining the complexity of FAs, there are two main types: deterministic finite automata (DFA) and nondeterministic finite automaton (NFA). In this article, we will explore the differences between DFA and NFA, including their respective complexities.

One key difference between DFA and NFA is the way they handle transitions. In a DFA, each state has a unique next state for each input symbol, whereas in an NFA, there are multiple states that can be reached from a single state, with no clear indication of which one will be chosen. This makes it more difficult to determine the complexity of NFAs compared to DFAs.

The Complexity of Deterministic Finite Automata

Deterministic finite automata (DFA) have a relatively simple complexity profile, making them an attractive choice for many applications. In particular, DFA have a linear time complexity, which means that their computational time scales directly with the size of the input data. This is because each transition can be computed in constant time.

The Inner Method for DFA

The inner method for DFA involves traversing the automaton from a given state and checking if there is an accepting state reachable from that state. The complexity of this method is relatively low, making it easy to implement in practice. However, one important difference between DFA and NFA is that for DFAs, we don't need to specify both the next state and the set of states that can reach that next state.

Printing Function

The printing function for DFA is straightforward, as it simply returns a string representation of the automaton's states and transitions. This makes it easy to visualize and understand the behavior of the automaton.

Example Automaton: N0

To illustrate the complexity of NFAs, let's consider an example automaton called N0. In this example, we have three states (0, 1, and 2), two input symbols (0 and 1), and a specific transition relation that defines how to move from one state to another based on the input symbol. The initial state is 0, and the final state is 2.

Transition Relation

The transition relation for N0 is as follows:

* From state 0, if we see a 0, we can only be in state 1.

* If we see a 1 from state 0, we can only be in state 2.

* From state 1, if we see a 1, we can only be in state 2.

* From state 2, there is no transition that leads back to state 1.

The Set of Initial States

The set of initial states for N0 is simply {0}, as this is the starting point for our automaton.

The Set of Final States

The set of final states for N0 is {2}, as this is the accepting state.

Run Function: NFA

The Run function for NFAs is more complex than that of DFAs. It involves computing the set of possible next states at each step, which requires using a function called Delta to look up in the transition relation. If there is no transition defined for a particular input symbol and current state, the run function returns the empty set.

In contrast to DFA, where we simply have a linear sequence of next states, NFA involves computing a set of possible next states at each step. This makes it more difficult to determine whether an NFA accepts a given input string.

Translation from DFA to NFA

Converting a DFA to an NFA is relatively straightforward. We create a new Delta function that assigns a singleton set to any transition in the original DFA, and we also specify the initial states as singletons. This makes it easy to translate every DFA to an NFA by simply turning all these single states into singletons.

Power Automaton Construction

Constructing a power automaton from an NFA is a more complex task. It involves creating new states that represent multiple possible next states, and then defining how to transition between these states based on the input symbol. This process can be quite involved, but it allows us to create a DFA that can recognize the same patterns as the original NFA.

Example Automaton: B

To illustrate the concept of power automata construction, let's consider an example automaton called B. In this case, we have three states (A, B, and C), two input symbols (0 and 1), and a specific transition relation that defines how to move from one state to another based on the input symbol.

Transition Relation

The transition relation for B is as follows:

* From state A, if we see a 0, we can be in either state B or C.

* If we see a 1 from state A, we can only be in state B.

* From state B, if we see a 0, we can only be in state C.

* If we see a 1 from state B, we can only be in state B.

* From state C, there is no transition that leads back to state A.

The Set of Initial States

The set of initial states for B is simply {A}, as this is the starting point for our automaton.

The Set of Final States

The set of final states for B is {C}, as this is the accepting state.

In conclusion, while finite automata are a powerful tool for recognizing patterns in input data, their complexity profile can be quite different depending on whether we're dealing with DFAs or NFAs. By understanding these differences, we can choose the right type of FA for our specific application and optimize its performance accordingly.

"WEBVTTKind: captionsLanguage: enwe are talking about finite automata last time and we had a look at deterministic finite automata what are these good for I mean they are sort of fun to play this right but some people that really I mean they cannot do any sort of Theory without seeing the Practical applications so let's say a few words about this when you write a compiler or any sort of programming language there are some components like which are sort of lexical which we need lexical analysis for like what is what is a what is an identifier what's a number what's a comment and so on this is a low level structure and this is done via a regular Expressions finite automata and so on so that's one of the things they're good for yeah um another thing is actually a regular Expressions which are we will see related to automata We Will We haven't seen this yet they are useful to describe patterns in text if you want to write something like text processing well if you want to write an editor script yeah to do something using regular expressions and they are translated into into automata practical yeah so so another one is um protocols uh communication protocols they're often described by finite automata it's it's a it's a good thing and then finite automata sort of the entry The Rock So to say to to so form a description of of computation which which do playable in theory as well as in applications okay yes so today as the last time we talked about deterministic finite automata and um I I I I do a few and we played with them uh so I mean this is under so other video and you don't have to go through this again but I wanted to do it today is is another thing it's non-deterministic finite automata and what are they we'll see they look very similar to the DFAS but they're basically magic machines whereas for a DFA you always are in a state and then you send some input you go to a different state for the nfas you you there is maybe a choice you maybe could go there or maybe here or you may be going nowhere yeah and and the magic is that an NFA it will always make the right choice yeah if there is a way that they could accept the word it will make this Choice yeah so they're really magic machines right so we're going I mean if you get them right no no I mean yeah the magic okay yeah that but they're matching and always guessing right when they run right so so this is in general actually the case with non-deterministic automata I mean there are other kinds of non-deteristic automata like pushed on automata or Turing machines they can be all non-deterministic and they're always the idea is they always do the right the right choices it's a bit magic right and you may ask what what are they good for again yeah because the DFA is clearly we can implement we can run but the NFA is there seem to be a bit there was a non-ded Mystic automata seemed to be a bit sort of fancy in like you have to have enough magic to be able to to run them yeah the point is that they're actually first of all in the case of the nfas we will see we can translate them into DFA that's not always possible for other automatons not always possible but in this case we can actually translate them and the non-deterministic automaton there it sort of in between the most of abstract description of languages yeah into actually implementation so they're like a a thing in between so for example when we look at regular Expressions we can translate them first into non-domestic finite automata and then next step into DFAS but they're sort of in between so they're useful as in between us yeah so this example so we're looking at at a language of words over some alphabet so the alphabet is this time is zero one so if you're looking at sequences of zero one and the language I'm going to uh just describe as a language so that the penultimate symbol of of the verge of the string is one okay let's play the game that's that that save as a shown as a good alternative I've been practicing okay very good what about one zero is it in the language yes okay what about one zero zero no no okay very good um what about uh zero one zero yes very good and what about one oh no no it's not exactly okay very good you I think I can hire you as an automaton or something you know okay so let's build okay how do I do this fold the door okay so let's build the automaton so as we have seen already the automaton they have little squiggles which are states well it's not I I call the state zero and I say it's my starting state so I put an arrow in and now I say no no I see a zero or one I stay in the state okay but now if I see a run I get sort of excited because maybe I'm going to win and then I have another state whatever comes here I go into this state and this is my final state okay so that's um that's an NFA and um why is an NFA um okay so first of all we have when we Interstate 0 and we see a one we could go here or we could go here right so that's a bit weird all right and then when we see a one okay with zero one we go here but then what happens here what happens if we see anything we there's no no transition so it's not a DFA yeah for two reasons so one reason in this case we have got two options and in this case we have no options but let's see whether we can we can run this automaton and you need a bit of investment to play with nfas yeah so how does this work so I'm I'm simulating an NFA by putting coins on the states remember that the DFA said it was my finger but here it gets a bit more complicated so let's say we want to do one zero see what happens so one zero we are here so we put a coin on the initial state or actually an NFA can have several initial States so we have to put all the coins and all the initial States this one is only one okay and now you see we see a one so so this one goes here but it also goes here so we are like in two states now right we are in state zero and state one at the same time like a superposition yes Phantom right and now okay we have we have to add this and now we read the zero so what happens is uh zero and zero and we are finished and we have a coin in the final state so hence it's accepted okay let me do one one one okay which I didn't ask previously but I just accustomed to me that's a good example okay we start with this coin then we have a one so let me go here right and now we have another one so so yeah if this coin stays here this coin goes here and this coin goes here right so we are finished and we have a coin in the final state so it's accepted no surprises so do a negative one what about one zero zero one zero zero okay so you start the corner one so now we read the one so we go here now we read the zero zero zero and now we really noticeable this coin has nowhere to go so we lose it it's really a game of money you can lose money you can win money but you can lose stays where it is and we have no coin on the final state so it's not accepted so this is the final automaton and that's where we run them right with coins but the idea is that the current self-represent all the states we could be in now we can translate an NFA into a DFA okay so here's the idea is that we have a a DFA where the states are sets of States so for example what we start with is the state which has only the set zero so now if you have a coin in state zero what we do is we Define a DFA which tracks the configuration of coins basically yeah so if we hit in state zero and we we see a zero then we still have just one coin and zero so that's this one here or if you see a one then we obviously have two coins so we have coin in zero and one so we go zero one okay so now let's say we're in zero one what happens if we see a zero what happens if you see a zero we stay here and we go here so we are after zero we are in zero two but let's dig in if you're in zero one and we see a one zero and if you see a one then this go here but because we have a loop here we go into 0 1 2 so if n zero one and we see a one and 0 1 2. you're not finished we have to to get transitions for these as well so what that's again we're on zero two and we see a zero what happens if you see a zero this one is lost but this one stays where it is so we are back to the state where we only have a coin in zero and what happens if you see a one so let's get let's reset we have zero two we see a one then this coin disappears and here we have two coins right so that that means if you see one I hope I didn't make a mistake here okay so here we have zero one so we have to see if we have three coins 012 and we see a zero what's happening this this is here this is lost so we are zero two so if you see Zero you go to zero two okay now what happens if here zero one two and we have a one we lose this one and this all okay so we have to mark initial state so the state where we put the tokens and the coins or the initial States is this one and and then we have to mark the final States so final states are any state which contains a two where there's at least a token a token a coin on the two and this is in DFA right because we have one initial State and we have always exactly we know all what's happening because we know what happens to the coins and this is a famous construct it's called the power automaton and it shows I mean hopefully the idea is clear that we can translate any NFA into a DFA into DFAS are easy to run okay now why is this called Power automaton because the states here are sets of states so it's a power set and in this case it's quite harmless we start with three states we have four states but in in general it could be an exponential blow up because with three states we actually have eight possible States two to the three because there are eight possible subsets and there are lots of states which are not reachable which you don't have to don't have to draw so another four states which you don't have to draw because it can never be reached but in principle you can have automaton which grew up like this so it's doable but not always practical yeah exactly it's not feasible okay should we go to do some python hackery let's do it yeah okay so here we have the code from last time which was a code for DFAS so we had a an init function uh printing function and a run function if you have some examples okay I'm going to do the the NF is in the same file because there's going to be some interaction between the two right you want to translate NF is to DFA is actually also Divas to nfas which seems should be easy but still we have to do a bit of work okay so we define a class NFA is it that certain problems are only able to be done within NFA to start with and then you translate it or it's certainly much easier so if you for example you see I want to recognize a fixed string yeah then to do this to to constructed and DFA can be non-trivial because I mean if all the possible yeah yeah so it's much easier to to construct the NFA and principles you can translate it yeah especially as I say if you come from regular expressions uh then it's quite straightforward to construct for every regular expression in the NFA and then to the DFA but it's not so obvious how to construct directly a DFA and in terms of running this computationally not on a piece of paper with coins yes we're going to look at that yeah yeah so we look at it is it easier for the computer to do the DFI sure yeah much easier yeah okay exactly actually DFA has got a linear complexity whereas for an NFA it's first of all not clear I mean it turns out after translation it's it's also linear but okay the inner method for the DFA is very similar the difference is that for the initial State we don't have not one unless you state which we have a set of initial States and the transition function Delta now becomes the transition relation because we don't know we don't always have function given the state and given an input we don't have one next state but we have a set of next States and this represents the relation right okay let me just continue a bit the printing function is called easy so nothing exciting but let me first do my example automaton okay so I call it n0 so what we have to say we have to give the set of States zero one two set of symbols which is 0 and 1. and now we give this transitional relation and that's a bit more interesting than before so we assign to any combination every combination of uh of of a state and an input a set of states so here for example the set of State 0 if if you're in in zero and we see a one then we could be in zero and one then we can only be in two and if we have one and one we can only be in two so first of all we haven't really described what happens for every combination so this is implicitly for the combinations we haven't covered it's the empty set and okay then we have here a set of initial states which is just zero and the set of final state which is two okay so what we now have to do is to define the Run function for nfas and that's a bit more involved than for DFAS we have to define a run function this was very easy in the case for the for the finite automata with just a little while loop going through the symbols and just use the data function to compute the next state but here okay we have to compute the set of States at each step and there's also the problems that sometimes we haven't defined uh the the answer and then it should be the empty set okay so what I'm doing here is I I have a function called do Delta which constructs the the set of the the states looking up in this relation but if there is no set then it Returns the empty set okay and the Run function what it's doing it it starts with the set p as a current set of coins it's a set which is in the initial State and then we have this while loop as before but we have to compute the the set of new coins and what we do is we go through all the states which are in P in the moment apply this Delta function and gets a new state and we take the union of all these so we take the union of all these possibilities and in the end we set P to be this this new state and when we have processed the whole world we say the intersection of p and the final State shouldn't be empty okay so let's type to to run this we have here this Autumn 10 and 0. so n0 don't run what was our first example one zero which is yes and now we do one zero zero and it is no and what else all we want to do this string which is just a one which is also false okay test cases now we have these two classes NFA and DFA it's first of all every every DFA should be an NFA so how can we translate a DFA into an NFA so I'm going to write a conversion method for DFAS called nfas to construct an in an NFA I have to construct this new Delta function and basically it returns a Singleton set for for any transition in in the in the Delta function of the of cells the DFA and it also constructs the Singleton set here okay for the for the initial States because there's only one so this translation is pretty easy so this using this function we can translate every DFA to an NFA by just turning all these single States into into Singletons and that's just how it looks like in Python but I'm going to leave the the other translation the power automation translation I'm leaving this as an exercise but I can provide the answer so here the idea is if we have an NFA we want to construct a corresponding DFA and there we have to do this power automated construction which I've just described by example so as I say that's left as an exercise to the reader but I can provide the answer if you get stuck and now let's try this one a B a bad State it's like kind of engineering type things this one is getting creating removing providing criticizing so like for some reason these types of wordswe are talking about finite automata last time and we had a look at deterministic finite automata what are these good for I mean they are sort of fun to play this right but some people that really I mean they cannot do any sort of Theory without seeing the Practical applications so let's say a few words about this when you write a compiler or any sort of programming language there are some components like which are sort of lexical which we need lexical analysis for like what is what is a what is an identifier what's a number what's a comment and so on this is a low level structure and this is done via a regular Expressions finite automata and so on so that's one of the things they're good for yeah um another thing is actually a regular Expressions which are we will see related to automata We Will We haven't seen this yet they are useful to describe patterns in text if you want to write something like text processing well if you want to write an editor script yeah to do something using regular expressions and they are translated into into automata practical yeah so so another one is um protocols uh communication protocols they're often described by finite automata it's it's a it's a good thing and then finite automata sort of the entry The Rock So to say to to so form a description of of computation which which do playable in theory as well as in applications okay yes so today as the last time we talked about deterministic finite automata and um I I I I do a few and we played with them uh so I mean this is under so other video and you don't have to go through this again but I wanted to do it today is is another thing it's non-deterministic finite automata and what are they we'll see they look very similar to the DFAS but they're basically magic machines whereas for a DFA you always are in a state and then you send some input you go to a different state for the nfas you you there is maybe a choice you maybe could go there or maybe here or you may be going nowhere yeah and and the magic is that an NFA it will always make the right choice yeah if there is a way that they could accept the word it will make this Choice yeah so they're really magic machines right so we're going I mean if you get them right no no I mean yeah the magic okay yeah that but they're matching and always guessing right when they run right so so this is in general actually the case with non-deterministic automata I mean there are other kinds of non-deteristic automata like pushed on automata or Turing machines they can be all non-deterministic and they're always the idea is they always do the right the right choices it's a bit magic right and you may ask what what are they good for again yeah because the DFA is clearly we can implement we can run but the NFA is there seem to be a bit there was a non-ded Mystic automata seemed to be a bit sort of fancy in like you have to have enough magic to be able to to run them yeah the point is that they're actually first of all in the case of the nfas we will see we can translate them into DFA that's not always possible for other automatons not always possible but in this case we can actually translate them and the non-deterministic automaton there it sort of in between the most of abstract description of languages yeah into actually implementation so they're like a a thing in between so for example when we look at regular Expressions we can translate them first into non-domestic finite automata and then next step into DFAS but they're sort of in between so they're useful as in between us yeah so this example so we're looking at at a language of words over some alphabet so the alphabet is this time is zero one so if you're looking at sequences of zero one and the language I'm going to uh just describe as a language so that the penultimate symbol of of the verge of the string is one okay let's play the game that's that that save as a shown as a good alternative I've been practicing okay very good what about one zero is it in the language yes okay what about one zero zero no no okay very good um what about uh zero one zero yes very good and what about one oh no no it's not exactly okay very good you I think I can hire you as an automaton or something you know okay so let's build okay how do I do this fold the door okay so let's build the automaton so as we have seen already the automaton they have little squiggles which are states well it's not I I call the state zero and I say it's my starting state so I put an arrow in and now I say no no I see a zero or one I stay in the state okay but now if I see a run I get sort of excited because maybe I'm going to win and then I have another state whatever comes here I go into this state and this is my final state okay so that's um that's an NFA and um why is an NFA um okay so first of all we have when we Interstate 0 and we see a one we could go here or we could go here right so that's a bit weird all right and then when we see a one okay with zero one we go here but then what happens here what happens if we see anything we there's no no transition so it's not a DFA yeah for two reasons so one reason in this case we have got two options and in this case we have no options but let's see whether we can we can run this automaton and you need a bit of investment to play with nfas yeah so how does this work so I'm I'm simulating an NFA by putting coins on the states remember that the DFA said it was my finger but here it gets a bit more complicated so let's say we want to do one zero see what happens so one zero we are here so we put a coin on the initial state or actually an NFA can have several initial States so we have to put all the coins and all the initial States this one is only one okay and now you see we see a one so so this one goes here but it also goes here so we are like in two states now right we are in state zero and state one at the same time like a superposition yes Phantom right and now okay we have we have to add this and now we read the zero so what happens is uh zero and zero and we are finished and we have a coin in the final state so hence it's accepted okay let me do one one one okay which I didn't ask previously but I just accustomed to me that's a good example okay we start with this coin then we have a one so let me go here right and now we have another one so so yeah if this coin stays here this coin goes here and this coin goes here right so we are finished and we have a coin in the final state so it's accepted no surprises so do a negative one what about one zero zero one zero zero okay so you start the corner one so now we read the one so we go here now we read the zero zero zero and now we really noticeable this coin has nowhere to go so we lose it it's really a game of money you can lose money you can win money but you can lose stays where it is and we have no coin on the final state so it's not accepted so this is the final automaton and that's where we run them right with coins but the idea is that the current self-represent all the states we could be in now we can translate an NFA into a DFA okay so here's the idea is that we have a a DFA where the states are sets of States so for example what we start with is the state which has only the set zero so now if you have a coin in state zero what we do is we Define a DFA which tracks the configuration of coins basically yeah so if we hit in state zero and we we see a zero then we still have just one coin and zero so that's this one here or if you see a one then we obviously have two coins so we have coin in zero and one so we go zero one okay so now let's say we're in zero one what happens if we see a zero what happens if you see a zero we stay here and we go here so we are after zero we are in zero two but let's dig in if you're in zero one and we see a one zero and if you see a one then this go here but because we have a loop here we go into 0 1 2 so if n zero one and we see a one and 0 1 2. you're not finished we have to to get transitions for these as well so what that's again we're on zero two and we see a zero what happens if you see a zero this one is lost but this one stays where it is so we are back to the state where we only have a coin in zero and what happens if you see a one so let's get let's reset we have zero two we see a one then this coin disappears and here we have two coins right so that that means if you see one I hope I didn't make a mistake here okay so here we have zero one so we have to see if we have three coins 012 and we see a zero what's happening this this is here this is lost so we are zero two so if you see Zero you go to zero two okay now what happens if here zero one two and we have a one we lose this one and this all okay so we have to mark initial state so the state where we put the tokens and the coins or the initial States is this one and and then we have to mark the final States so final states are any state which contains a two where there's at least a token a token a coin on the two and this is in DFA right because we have one initial State and we have always exactly we know all what's happening because we know what happens to the coins and this is a famous construct it's called the power automaton and it shows I mean hopefully the idea is clear that we can translate any NFA into a DFA into DFAS are easy to run okay now why is this called Power automaton because the states here are sets of states so it's a power set and in this case it's quite harmless we start with three states we have four states but in in general it could be an exponential blow up because with three states we actually have eight possible States two to the three because there are eight possible subsets and there are lots of states which are not reachable which you don't have to don't have to draw so another four states which you don't have to draw because it can never be reached but in principle you can have automaton which grew up like this so it's doable but not always practical yeah exactly it's not feasible okay should we go to do some python hackery let's do it yeah okay so here we have the code from last time which was a code for DFAS so we had a an init function uh printing function and a run function if you have some examples okay I'm going to do the the NF is in the same file because there's going to be some interaction between the two right you want to translate NF is to DFA is actually also Divas to nfas which seems should be easy but still we have to do a bit of work okay so we define a class NFA is it that certain problems are only able to be done within NFA to start with and then you translate it or it's certainly much easier so if you for example you see I want to recognize a fixed string yeah then to do this to to constructed and DFA can be non-trivial because I mean if all the possible yeah yeah so it's much easier to to construct the NFA and principles you can translate it yeah especially as I say if you come from regular expressions uh then it's quite straightforward to construct for every regular expression in the NFA and then to the DFA but it's not so obvious how to construct directly a DFA and in terms of running this computationally not on a piece of paper with coins yes we're going to look at that yeah yeah so we look at it is it easier for the computer to do the DFI sure yeah much easier yeah okay exactly actually DFA has got a linear complexity whereas for an NFA it's first of all not clear I mean it turns out after translation it's it's also linear but okay the inner method for the DFA is very similar the difference is that for the initial State we don't have not one unless you state which we have a set of initial States and the transition function Delta now becomes the transition relation because we don't know we don't always have function given the state and given an input we don't have one next state but we have a set of next States and this represents the relation right okay let me just continue a bit the printing function is called easy so nothing exciting but let me first do my example automaton okay so I call it n0 so what we have to say we have to give the set of States zero one two set of symbols which is 0 and 1. and now we give this transitional relation and that's a bit more interesting than before so we assign to any combination every combination of uh of of a state and an input a set of states so here for example the set of State 0 if if you're in in zero and we see a one then we could be in zero and one then we can only be in two and if we have one and one we can only be in two so first of all we haven't really described what happens for every combination so this is implicitly for the combinations we haven't covered it's the empty set and okay then we have here a set of initial states which is just zero and the set of final state which is two okay so what we now have to do is to define the Run function for nfas and that's a bit more involved than for DFAS we have to define a run function this was very easy in the case for the for the finite automata with just a little while loop going through the symbols and just use the data function to compute the next state but here okay we have to compute the set of States at each step and there's also the problems that sometimes we haven't defined uh the the answer and then it should be the empty set okay so what I'm doing here is I I have a function called do Delta which constructs the the set of the the states looking up in this relation but if there is no set then it Returns the empty set okay and the Run function what it's doing it it starts with the set p as a current set of coins it's a set which is in the initial State and then we have this while loop as before but we have to compute the the set of new coins and what we do is we go through all the states which are in P in the moment apply this Delta function and gets a new state and we take the union of all these so we take the union of all these possibilities and in the end we set P to be this this new state and when we have processed the whole world we say the intersection of p and the final State shouldn't be empty okay so let's type to to run this we have here this Autumn 10 and 0. so n0 don't run what was our first example one zero which is yes and now we do one zero zero and it is no and what else all we want to do this string which is just a one which is also false okay test cases now we have these two classes NFA and DFA it's first of all every every DFA should be an NFA so how can we translate a DFA into an NFA so I'm going to write a conversion method for DFAS called nfas to construct an in an NFA I have to construct this new Delta function and basically it returns a Singleton set for for any transition in in the in the Delta function of the of cells the DFA and it also constructs the Singleton set here okay for the for the initial States because there's only one so this translation is pretty easy so this using this function we can translate every DFA to an NFA by just turning all these single States into into Singletons and that's just how it looks like in Python but I'm going to leave the the other translation the power automation translation I'm leaving this as an exercise but I can provide the answer so here the idea is if we have an NFA we want to construct a corresponding DFA and there we have to do this power automated construction which I've just described by example so as I say that's left as an exercise to the reader but I can provide the answer if you get stuck and now let's try this one a B a bad State it's like kind of engineering type things this one is getting creating removing providing criticizing so like for some reason these types of words\n"