0.1 Automata, Computatbility, and Complexity Main question the course aims to answer: What are the fundamental capabilities and limitations of computers? Complexity Theory: What makes some problems computationally hard and others easy? Computability Theory: What problems are solvable by computers and what are not? Automata Theory: We create models and then investigate the power of these models. The two key models are DFAs and PDAs, and the two groups of languages we will focus on are regular languages and context-free languages. Sets ---- You should remember these from COT 3100. In this class, we will deal with languages. A language is simply a subset taken from an universe of strings. A string is the concatenation of 0 or more symbols taken from an alphabet. Notice that there are always an infinite number of possible strings as long as the alphabet we are using has at least one symbol in it. In fact, the vast majority of the languages we will deal with are infinite languages, namely languages that contain an infinite number of strings. To see this is possible, consider the set of all strings formed with the characters 0 and 1. Here is a language that is a subset of this set of strings that is infinite: {01, 0101, 010101, ...} In English, this language would be the set of strings that contain 1 or more concatenated repetitions of the string 01. Certainly, you are familiar with the concepts of set union, intersection and complement. We will use these extensively in the course. Keep in mind that the intersection between two infinite sets could be infinite as well. Sequences and Tuples -------------------- A sequence is an ordered list of elements. A k-tuple is a sequence with k elements. We will use the term "tuple" frequently in this course. Also, note that a set itself can be an element in another set. The idea of a power set exemplifies this. A power set of a set is the set of possible subsets of the original set. A cross product of two sets produces a new set whose elements are pairs or 2-tuples. For example if A={1,2,3} and B={a,b}, then AxB = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)} Functions and Relations ----------------------- This was covered in detail in COT 3100. Please refer to notes you have from that course for this section, or the text. Graphs ------ These are abstract entities created of nodes/vertices and edges. Edges connect vertices.Types of modifiers for graphs are: 1) undirected/directed 2) unweighted/weighted An undirected graph means that there's no designated direction between the vertices that define an edge. In a directed graph, one of the two vertices is the "from" vertex and the other is the "to" vertex. A weighted graph has a real number associated with each edge while an unweighted graph does not. Here are some terms to look up in the text: subgraph, simple path, connected, simple cycle, tree, leaves, root, outdegree, indegree, directed path, strongly connected Strings and Languages --------------------- This is the bread and butter of this course. As described before, an alphabet is a set of characters. A string is the concatenation of zero or more characters from a given alphabet. A language is simply a set of strings taken from the universe of all possible strings from a given alphabet. The length of a string w is designated as |w|. It is the number of characters in the string. A string of length 0 is the empty string and we will write it with a Greek epsilon. A substring is a subsequence of characters in a string, thus they appear contiguously in a string. I've already used the term concatenate. It just means to "stick next to" When we concatenate "go" to "lf" we get "golf", for example. A lexicographical ordering of strings is the same as a dictionary ordering, with the added rule that all shorter strings precede longer ones. So, a lexicographical ordering of all strings from the alphabet {0,1} is epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, etc. Boolean Logic ------------- This was covered well in COT 3100. Definitions, Theorems and Proof ------------------------------- Please read the definitions of proof, theorem, lemma and corollary. In this class, just as in this text, we will attempt to prove theorems at a high level. We will try not to get bogged down with intricate details. Use the examples in the text as a guide for the type of detail I am looking for in your proofs. I'll expect you to be thorough, but once you've explained why one idea works, there's no need to repeat that explanation. Please read the proofs on page 20 of the text. Types of Proof -------------- Proof by Construction: You show that something is true by creating a specific example that shows it is true. Example: Prove that all positive integer greater than 2 can be written as the sum of two distinct positive integers. Given an integer k, where k>2, we can express it as 1 + (k-1). Since k>2, it follows that k-1 > 1. Thus, the integers 1 and k-1 are distinct and also add up to k, proving the given statement. Proof by Contradiction: We went over this in COT 3100 several times. Look over the proof given in the text. Proof by Induction: You have certainly seen this in COT 3100. In this class you will see that it can be used to prove statements that aren't summations and that don't even contain summations!