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.

Simulating finite automata in programs

Suppose we wanted to take a machine like \[ M1 = \left( \{q_0,q_1,q_2\}, \{a,b\}, {\small \begin{array}{c|cc} & a & b\\ \hline q_0 & q_2 & q_1\\ q_1 & q_2 & q_1\\ q_2 & q_1 & q_2 \end{array}}, q_0, \{q_0,q_2\} \right) \] ... and implement it as a function we could call in a computer program? Below are two different approaches to doing this in C++: ex0.cpp and ex1.cpp.

Important! ex1.cpp is a much better way to do this! 

$ g++ ex1.cpp -o ex1
$ ./ex1
usage: ./ex1 in1 in2 ...
$ ./ex1 a b aa ab bb abaab ababb
accept a
reject b
reject aa
accept ab
reject bb
accept abaab
reject ababb

Comment 1: Performance-wise, ex0.cpp is a disaster. A single transition might take as many as |Σ||Q| steps --- i.e. we check each character/state combination. If we give each alphabet symbol an index, we can represent the transition function δ as a table (i.e. a 2D array), just like we do when writing out 5-tuples for machines. That way, each transition is done in a single table lookup which, as you've learned in data structures, is a constant time operation. ex1.cpp does this. Similarly, in ex0.cpp, determining whether we're in an accepting state can take as many as |W| steps. Once again, clever use of arrays can make that constant time, and that's what ex1.cpp does.

Comment 2:

In the last "extra" session, you might have written a function like this: That's OK, but if we follow our data-driven programming approach, we might do something like this: BTW: real Python programmers have ways to write this version much more concisely. We'll get into that later.
The approach taken by ex1.cpp is vastly better than that of ex0.cpp in another, possibly more important, way. In ex0.cpp the transitions and accepting states are embedded in code, i.e. in if/else-if/else statement and || and && expressions. In ex1.cpp, the transitions and accepting states are embedded in data, i.e. in the 2D array delta and 1D array W. [This is an example of data-driven programming which is something we will see Python makes easy for us programmers to do.] Why is this so much better? Imagine you want to change the machine by changing which states are accepting states? Or by changing some of the transitions, which program is easier to modify? What if I gave you a totally different machine with four states and alphabet $\{a,b,c\}$, which program would be easier to adapt?

Important! The big takeaway here is that it is trivial to convert a finite automaton into extremely efficient code to accept or reject strings by executing the machine. In fact, we can automate the conversion. So, while it is true that Finite Automata are very simple, limited models of computation, we love it when we can design FAs to solve our problems, because we can automatically convert them to extremely efficient code. With more powerful models of computing, converting to code becomes more and more difficult, and efficiency becomes harder and harder (to the point of being impossible) to achieve.

Set review: Set Operations

We covered several basic operations on sets in our Extra lesson on sets. Here's a summary:

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)" ... but then again, maybe not. You don't know. So give them a smack upside the head to provide helpful corrective feedback.

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,\Sigma,\delta,s,W)$
Output: DFA $M'$ such that $L(M') = \overline{L(M)}$
$M' = (Q,\Sigma,\delta,s,Q-W)$
From our informal discussions on this algorithm, it should be clear that it does what it's supposed to, i.e. that it produces a machine 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.

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 Σ*.

ACTIVITY:

Set review: Function definitions

Specifying function prototypes/signatures is straightforward. Specifying definitions is a bit less so, because you have so much flexibility in how you do it. So it's wroth reviewing. For the most part, you just need to 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 that Z stands for the set of all integers.)
s:Z → Z
s(x) = x+1
The prototype you should already know. The definition says that for any 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} \]
As I said before, you get a fair amount of flexibility in how you define these things. Here's an example defining a function 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 $M_1 = (Q_1,\Sigma,\delta_1,s_1,W_1)$ and $M_2 = (Q_2,\Sigma,\delta_2,s_2,W_2)$ and produces new machine $M$ such that $L(M) = L(M_1) \cap L(M_2)$, i.e. the language accepted by $M$ is the intersection of the languages accepted by $M_1$ and $M_2$. (Notice that the alphabets of the two machines must be the same!)
Algorithm: Intersection
Input: DFA $M_1 = (Q_1,\Sigma,\delta_1,s_1,W_1)$ and DFA $M_2 = (Q_2,\Sigma,\delta_2,s_2,W_2)$
Output: DFA $M$ such that $L(M) = L(M_1) \cap L(M_2)$
$M = (Q,\Sigma,\delta,s,W)$, where
Once again, a formal proof that this algorithm really constructs a machine accepting 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:

  1. Clearly specify what the input is.
  2. Clearly specify what the output is, i.e. what kind of object does the algorithm return, what task does the algorithm accomplish.
  3. 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 body of the algorithm 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".