![]() This choice of names is convenient, and helps understanding, becauseīecause a state of $D$ is intended to mimic (in some precise sense) the behavior of This is usually simplified into saying thatĮach state of $D$ is a subset of the states of $N_4$. However, it is convenient to use sets of names When building the DFA $D$, you can use any name you want for the That are meaningful, and help understand the program. Good programming practice recommands the use of identifiers You have exactly the same situation in programming, when you have toĬhoose names/identifiers for variables, functions, classes or otherĮntities, though these names are usually restricted to alphanumeric This is probably why Sipser used $1$ for the start state. This namingįreedom should rather be used to make things easier to understand and You only want them as names in order to describeīut this should not encourage you to use strange naming. They do not even need to come from aĬonsistent source. That you can enumerate (give me some time to think about sets that are countable but not recursively enumerable. Set of states or symbols, you can take any set of mathematical objects In other words, in languages and automata theory, when you talk of a Touch the start arrow or any other part of the picture), or it could even be the names Huey, Dewey,Īnd Louie, or the names "foo", $2$ and "blue" (which is very useful if you describe the NFA with a poem). Now be $2$ (in the picture, you move $1$, $2$ and $3$, but you do not $3$ assigned differently to the states so that the start state would Initial NFA $N_4$, but you might describe the same NFA with the names If you take a DFA and change consistently the name of a state of the Whether they stand for the character or the integer does not actually So here $1$, $2$, and $3$ are the names of the states. Important (using quotes, for example), but you can often forget about That there are notational devices to make the distinction when it is Themselves or their names when the names is written down. Named too to talk about them, it is hard to know whether you are using ![]() Since other things, such as integers or sets of integers, need to be Names from any set, such as integers, or sets of integers for example. Utterances, or written character strings. Particular, there is no reasons that names should be only spoken You can play a lot with names, which is sometimes very convenient. (the "s" ending "bites" is intentional) while dogs may bite. The name of Mary is "Mary", and "dogs" never bites ![]() Though the quotes are needed only in the definition, since theīeginning of this definition is about the name, rather than what isīeing named, quotes are not to be used when the name stands for what Or more accurately Let "Joe" be a name for the third natural integer. Notational definition: Let Joe be a name for the third natural integer. Understand, or it can be the name "Joe" if you have first given the Though you can also call it "third natural interger" which people will It can be theĬharacter "3" or the string "III" if it is the third natural integer, ItĬan be "babou" right now if I am the something. It with a name, which should refer to it only in a given context. Start, how you can pass from one to another on some input, and whichĪs usual, when you talk about something, the best way is to identify To describe/define your automaton is to have 3 distinct states, and toīe able to distinguish them in some way so that you can tell where you Theįact is that it is irrelevant, that it does not matter. Natural integers, or only the three characters that represent them (or even, possibly, three strings of one character each). Now, you might wonder whether it is actually the first three In theĮxample, the names of the initial NFA $N_4$ are the integers $1$, $2$ and The major point in this is that state names do not matter. Presentation, other than with the page you give. Have Sipser's book, so that I cannot relate specifically to his I suspect it may be the former, so I will try to answer that. That it is a set of states, or the fact that it is this specific set Next, we determine the start and accept states of D. I have problem understanding this para :. I couldn't understand as to how he is taking his act on equivalence between NFA and DFA. I was reading Michael Sipser's Introduction to Theory of Computation and I came to a problem. Before asking this question,I had gone through Equivalence of NFA and DFA - proof by constructionīut my question is a bit different from that.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |