**Reading**-
Sections 1.4 of
*Theory of Computing, A Gentle Introduction*... again. You really need to know this stuff! **Homework**- Printout the homework and answer the questions on that paper.

**Set Operations**-
There are several basic operations on sets that you need to
know, all of which were covered in detail in discrete! Here's
a summary:
**union**: the union of two sets*A*and*B*(which we denote by*A∪B*) is the set of elements of either*A*or*B*or both.**intersection**: the intersection of two sets*A*and*B*(which we denote by*A∩B*) is the set of elements of common to both*A*and*B*.**difference**: the difference of sets*A*and*B*(which we denote by*A - B*) is the set of elements in*A*that are not in*B*.**complement**: complement of set*A*(denoted*A*) is the set of everything not in*A*. This is a little tricky, in that it requires that we know ahead of time what the*universe of discourse*is --- i.e. we need to know what all could have gone into*A*in the first place. For example, if we're talking about languages over the alphabet*{a,b}*and*A = {abb,bba}*, then*A*doesn't include, for example, the string*ccab*, because our universe of discourse was strings over*{a,b}*.

Rembember: a

*language*is a*set*. Therefore, if*L1*and*L2*are languages, the expression*L1∩L2*is well-defined — it makes sense. Same with ∪, – and . In contrast, if*M1*and*M2*are finite automata,*M1∩M2*is nonsense — it is*not*well-defined — because*M1*and*M2*are*tuples*, not*sets*! If someone writes "*M1∩M2*", they probably mean "*L(M1)∩L(M2)*". **Complement machine algorithm: the formal version**-
Now we can give a precise algorithm that takes as input a machine
*M = (Q,Σ,δ,s,W)*and returns as output a machine*M'*such that*L(M') = L(M)*, i.e. the language accepted by*M'*is the complement of the language accepted by*M*. Here it is:**Algorithm:**Complement

**Input:**DFA*M = (Q,Σ,δ,s,W)*

**Output:**DFA*M'*such that*L(M') = L(M)*

*M' = (Q,Σ,δ,s,Q - W)**M'*accepting the complement of the language accepted by*M*. A strictly formal proof of the algorithm's correctness relies on the concept of*configuration*, which we'll need to even give a formal definition of what it means for a machine to accept a string! On the other hand, hopefully this algorithm is so obviously correct that no further proof is needed. **Set construction notation**-
When we want to describe fancy sets, often union, intersection
Cartesian product, etc just aren't enough. There is a special
notation for constructing sets that we often employ in these
situations. We'll start with an example. Suppose we wanted
to construct the set of all ordered pairs of natural numbers
(recall, the natural numbers
) whose sum is 1000. Here's how we'd do it:**N**= {0,1,2,3,4,...}*{(a,b) ∈*. This expression reads:**N**x**N**| a + b = 1000}The set of all

Essentially, the form of these expressions is*(a,b)*, which are pairs of natural numbers, such that*a + b = 1000*.*{A | B}*where*A*defines the set from which you're choosing objects, the**|**means "such that", and the*B*gives a criterion for selecting which objects will actually end up in your set. People are usually pretty free-wheeling about what goes in the*A*and*B*, as long as it's clear what set's getting constructed. The big thing to remember, is that in*A*you're also giving a name or pattern representing a random object which you'll refer to in*B*--- like I did with*(a,b)*in the above example. If I'd chosen a different "pattern", like*x ∈*, it would've been difficult to express the selection criterion. I would've ended up with something like:**N**x**N***{x ∈*| first component of**N**x**N***x*+ second component of*x = 1000}*← ugly way to get the job done! **Languages (more formally)**-
Languages are just sets of strings, so we often use set
constructor notation to describe languages. This often leaves
us in the situation of wanting to refer to the language/set of
all strings over a given alphabet Σ. The notation for
this is Σ*.
Problems:

- Define the set of all strings over the alphabet
*{I,J,K}*whose length is 10.*{w ∈ {I,J,K}* | |w| = 10}**w*over*{I,J,K}*such that the length of*w*is 10". - Define the set of all palindromes over the alphabet
*{0,1}*.*{w ∈ {0,1}* | w = w*^{R}}*w*over*{0,1}*such that*w*equals*w*reversed. -
What about the following language?
*{xw ∈ {a,b,c}* | x = a and w = w*^{R}}*a*in this language? Why? How about λ?

- Define the set of all strings over the alphabet
**Function definitions**-
We know how to specify function prototypes in the mathematical
language of sets, but we haven't dealt with function
definitions yet. They're straightforward, actually. under
the prototype, you just give a rule for getting the function's
value from its input. For example, suppose we wanted to
define the "successor function"
*s*, which simply takes an integer and returns the next integers. (Recall thatstands for the set of all integers.)**Z***s:Z → Z*

s(x) = x+1*x*from the function's domain, the function produces*x+1*.Often we end up breaking things up into cases when we define functions. For example, we might give the following definition for the "signed successor function"

*ss*.\[ \begin{array}{l} ss:Z \longrightarrow Z\\ ss(x) = \left\{ \begin{array}{cl} x + 1 & \text{if } x \gt 0\\ x - 1 & \text{if } x \lt 0\\ x & \text{if } x = 0 \end{array} \right. \end{array} \]*f*that takes a string and concatenates it with its reverse, with the hitch that if the string has odd length, the last character isn't doubled up in the result string. For example:*f(ab) = abba*, but*f(abb) = abbba*. Let*Σ = {a,b}*. We'll define*f*in a few different ways:

\[ \begin{array}{l} f: \Sigma^* \longrightarrow \Sigma^*\\ f(\lambda) = \lambda\\ \underset{ w \in \Sigma^*, a \in \Sigma }{f(wa)} = \left\{ \begin{array}{cl} waaw^R & \text{if $|wa|$ even}\\ waw^R & \text{if $|wa|$ odd}\\ \end{array} \right. \end{array} \]\[ \begin{array}{l} f: \Sigma^* \longrightarrow \Sigma^*\\ f(a_1 a_2 \cdots a_k) = \left\{ \begin{array}{cl} a_1 a_2 \cdots a_{k-1} a_k a_k a_{k-1} \cdots a_2 a_1 & \text{if $k$ even}\\ a_1 a_2 \cdots a_{k-1} a_k a_{k-1} a_{k-2} \cdots a_2 a_1 & \text{if $k$ odd}\\ \end{array} \right. \end{array} \] **Intersection machine algorithm: more formally**-
This algorithm takes as input machines
*M1 = (Q1,Σ,δ1,s1,W1)*and*M2 = (Q2,Σ,δ2,s2,W2)*and returns as output a machine*M*such that*L(M) = L(M1) ∩ L(M2)*, i.e. the language accepted by*M*is the intersection of the languages accepted by*M1*and*M2*. (Notice that the alphabets of the two machines must be the same!)**Algorithm:**Intersection

**Input:**DFA*M1 = (Q1,Σ,δ1,s1,W1)*and DFA*M2 = (Q2,Σ,δ2,s2,W2)*

**Output:**DFA*M*such that*L(M) = L(M1) ∩ L(M2)*

*M = (Q,Σ,δ,s,W)*, where*Q = Q1 x Q2**δ:Q x Σ → Q*

δ((q,p),a) = (δ1(q,a),δ2(p,a))*s = (s1,s2)**W = W1 x W2*

*L(M1) ∩ L(M2)*will have to wait. We're familiar enough with the idea of this algorithm that we probably don't need any more convincing. **Notes on writing down algorithms**-
When you write down an algorithm you must:
- Clearly specify what the input is.
- Clearly specify what the output is, i.e. what kind of object does the algorithm return, what task does the algorithm accomplish.
- Write down the body of the algorithm clearly and unambiguously enough that another person could follow it, apply it to example inputs and get the answer you intend ... maybe even implement it as a program.

All the variables describing the input are like parameters to a function, i.e. they are values you can use to construct your output result --- you do not have to give them values in your algorithm. All variables appearing in your output description that are not part of the input are variables

**you must give values to**. For example, in the intersection algorithm the variable*Σ*appears in the output expression, but nowhere in the "output" section do I give Σ a value. No problem, because Σ is given to us as input to the algorithm. The variable*W*, on the other hand, is not given to us as input and it appears in the output expression. Therefore, we must define*W*, i.e. give it a value, which we do on the last line with "*W = W1 x W2*".