CPSC 229, Fall 2000 Information for the Third Test -------------------------------------------------------------------------- The third test for this course takes place on Wednesday, November 15. This test covers Sections 3.3 and 3.4 on mathematical induction. It covers sections 4.1 through 4.5 from Chapter 4. Although Section 4.6 on non-regular languages is not included, you are still responsible for basic facts about non-regular languages that we cover in class. Here are some of the terms, ideas, and techniques that you should be familiar with for this test: mathematical induction proof by induction base case and inductive case of a proof by induction why does induction work? summation notation (with the "big sigma" operator) other "big operators", such as for union and intersection of sets inductive proofs about summations the second form of the principle of induction recursion base case and inductive case of a recursive subroutine relationship between induction and recursion alphabet symbol string length of a string concatenation of stings reverse of a string empty string language the set of strings over an alphabet ("Sigma-star") "Sigma-star" is countably infinite the number of different languages over a given alphabet is uncountable concatenation of languages Kleene star operator, applied to languages set operations applied to languages (union, intersection, complement) reverse of a language regular expressions regular expressions and pattern matching operators +, *, and concatenation in regular expressions the language generated by a regular expression regular language FSA (Finite State Automaton) start state and accepting (or final) states DFA (Deterministic Finite Automaton) formal definition of a DFA as a 5-tuple (giving the set of states, the alphabet, the start state, the transition function, and the set of accepting states) the language accepted by a DFA transition diagram for an FSA relating the formal definition of a DFA to its transition diagram NFA (Non-deterministic Finite Automaton) the language accepted by an NFA the complement of a regular language is regular the intersection of two regular languages is regular the equivalence of regular expressions, DFA's, and NFA's given a regular expression, how to produce an equivalent NFA given an NFA, how to produce an equivalent DFA counting argument that there are languages that are not regular specific examples of languages that are not regular