MENU

Class 1: Course intro, alphabet/language intro


Reading
Sections 1.1, 1.2, 1.3 of Theory of Computing, A Gentle Introduction.

Homework
This homework will define and, hopefully help you understand, some of the basic notation involved with manipulating strings.
  1. Given the alphabet Σ = {a,b,c}, what is the language of all strings that start and end in c, with length at most three. [Remember: a language is by defintion a set!]
  2. Concatenation of strings, i.e. gluing strings together, is indicated by placing strings next to one another. so if w = abb and x = ba, then wx = abbba.
    1. Let x = bba, y = aab, and z = bcb. What is yxz?
    2. For strings u and v, is it always true that (uv)R = vu? Convince me of your answer! ["R" means reverse a string. So (abb)R = bba.]
  3. We denote the length of a string w as |w| ... like magnitude for a vector. For strings u and v, what can you say about |uv|?
  4. Consider the mystery string λ. Suppose that for any string w, we have |wλ| = |w|. What can you tell me about λ?
  5. We often represent the characters in a string like this: w = a1a2...ak. Suppose I define the "George" of a string w = a1a2...ak to be a2a1 a4a3 ... akak-1. What is the "George" of abcccb?

Course admin
Choose section leader, pass out course policy and departmental honor policy. 1/C remember: You must pass this course to graduate with a CS degree, and it isn't offered again in the spring!

What is "theory of computing"?

Languages, alphabets, strings

Further importance of languages
Most fundamental computing problems can be phrased as the following kind of problem: Given a description of a language L, decide whether a given string w is in the language L. These problems are decision problems, which means they have yes or no answers. Often the decision problem version of a question is a bit easier than the original, but they're related.

For example, suppose your original problem is "Compute (3 + (2*x)) + x*4 given x". As a decision problem this , might become "Given a string x:y, where x and y are strings of digits, decide if x:y is in the language of strings for which the numbers encoded by x and y satisfy y = (3 + (2*x)) + x*4".

By restricting our attention to decision problems like this, our computational models can become much simpler, so at some points we'll just talk about decision problems. True, the decision problem is often easier that the original problem, but this is OK. What we'll show at the end of the semester, is that there's a straightforward decision problem of the type described above that can't be solved by any computer or computer program. No matter how clever you are writing your program or building your machine, there will always be some input strings that foil your program. Either it will give wrong answers, or it will run forever, never giving any answer at all!


Christopher W Brown
Last modified: Thu Aug 23 10:17:18 EDT 2007