This string is in the language, and so we can add the empty string to it. To recap, we have identified two states: an accepting start/initial state, and what we call a "dead" state - a state that is not accepting and which does not ever lead to an accepting state.
The set of strings we can add to this to get a string in the language is the empty set, and therefore, we will need a state distinct from the one we've already identified to remember this string and strings like it - strings to which we cannot add anything to get a string in the language.
This is an example of a string not in the language, and there's nothing we can add to the end of this string to cause it to be in the language we've already violated the condition that all a's in the string are preceded by b's. We will need at least one state to remember the empty string (and strings like it - strings to which we can append the empty string or any other string in the language and still have a string in the language) this will be the start/initial state, and since the empty string is in the language (we check this easily), we know the start/initial state will be accepting. Additionally, we can append any string in the language we are going for to the empty string, and we will get a string in the language (trivially). What can you append to this to get a string in the language? Well, the empty string is in the language, so we can append the empty string (i.e., nothing) and also have a string in the language. Let's start with a few small strings and see what I mean. A good way to think about FAs is by trying to think about how many different situations you can be in, in terms of how you are going to get to a string in the language.
0 kommentar(er)
