計算機科學(xué)分類自動機理論automata

1、1Discussion of Common Problems 1TypesLanguage an Automaton AcceptsSound of No Hands Clapping2TypesTypes or classes are not just important in programming; they are vital in mathematics and automata theory.Weve seen distinctions among types:Characters vs. strings.Sets vs. elements.3Strings Vs. Charact

2、ersA common and important distinction in programming languages.”a” is of type String; a is of type char.Especially important: is of type String.Oddity: in the -NFA, we see arcs labeled by strings ( in particular) and by characters (ordinary inputs like 0).4Strings Vs. Characters (2)Its not a problem

3、; characters can be coerced to strings.Example: in Java ” + 0 = ”0”.Similarly, in an -NFA, you can mentally coerce the character labels to strings of length 1.And for any kind of finite automaton, labels of paths are strings.5Example: Label of a Path010Concatenation of the labels, each treatedas a s

4、tring is 010.6Sets Vs. ElementsThese are always different types.Especially, strings are elements, while sets of strings (e.g., languages) are sets. is a string.The empty set is a set.Sets can have “members”; elements never do.7Sets Vs. Elements (2)The empty set is the only set in the world that does

5、 not have any members.Notice that strings like or 001 do not have members, but for a different reason:Elements cannot have members.8States of an NFAStates are always elements.The subset construction seems to construct DFA states that are sets of NFA states.Really, the DFA states correspond to sets o

6、f NFA states, but are elements with names like “Sally” or “q”.Convenient to use something like p, q for the name of a DFA state.9Language of an AutomatonAutomata accept strings.Labels of paths from the state state to an accepting state.They also accept languages.EXACTLY the set of strings that the a

7、utomaton accepts.Thus, many strings, but ONE language.10FallacyWe had a number of forum discussions where people took “automaton A accepts language L” to mean that all the strings of L are accepted by A.If that were the case, all languages would be “accepted” by:AStart0, 111Sound of No Hands Clappin

8、gPeople sometimes have trouble with the edge cases of general statements.Example: We know what the sum of integers is; but what if there are 0 integers?Example: we know what it means for a string to have an even number of 0s; but what if that string is empty?12Sum of Zero IntegersWe know what the su

9、m of several integers is, e.g., 4 + 7 + 3.What is the sum of no integers?The only sensible choice is the identity for the operation +; i.e., 0.13Programming ViewIf we wanted to sum integers ai for i = 0, 1, n-1, we would write, e.g.:sum = 0;for (i=0; in; i+) sum += ai;What is the result if n=0? (Ans

10、.: sum = 0).14Other Operatorsp OR q OR r? OR of zero propositions = false (the identity for OR).p AND q AND r? AND of zero propositions = true (the identity for AND).p*q*r? product of zero numbers = 1 (the identity for multiplication).”w” ”x” ”y”? concatenation of zero strings = (the identity for co

11、ncatenation).15Example: Concatenation of Zero StringsSuppose the start state is also accepting.The path from state A to A has, as label, the concatenation of zero strings.Implies that is accepted by this DFA. AStart16Is 0 Odd or Even?Even, because the remainder of 0 divided by 2 is 0.I.e., 0 = 2*0 + 0.The empty string has zero of every symbol.So has an even number of 0s an even number of 1s, and so on.17Automata Not a Lady AutomatonAnd let me add one more point not of mathematics but of diction.“Automa