Week 13 Lecture notes

State Diagrams and Regular Expressions

Simple patterns

Suppose that our set of input characters contains 0 and 1. Let's build DFAs to recognize two simple patterns: even length strings and strings that have exactly the form $1(00)^+1$

When describing sets of strings, the notation $x^+$ means any non-zero number of x's. So $1(00)^+1$ describes all strings that start and end with a single 1 and have an even (non-zero) number of 0's between them.

1(00)+1 DFA — Recognizer for strings of the form $1(00)^+1$.

In this second example, notice that there are certain places where seeing one of the two characters immediately means the input string isn't acceptable, e.g. seeing a 0 as the first character or a 1 as the second character. To keep the diagram simple, we simply omit the transitions for these inputs and have the convention that missing transitions lead to a "dump" (aka fail) state.

Similarly, there are no transitions from the final state E. Our string isn't supposed to contain any characters after that second 1. So there are implied transitions from E to the dump state on both 0 and 1.

Two parallel constraints

Suppose that our set of input characters contains C, E, and M. Let's build a DFA that recognizes strings of even length that have the form $C^*MME^*$. (Remember that $x^*$ means zero or more x's.)

We can use the following state diagram to recognize $C^*MME^*$, where missing transitions go to an invisible dump state.

DFA letter pattern — Recognizer for strings of the form $C^*MME^*$.

Let's modify that state diagram so that it also keeps track of whether the overall length is even or odd. To do this, we make two copies of each state.

DFA two constraints — DFA for even length strings of the form $C^*MME^*$.

WYSWYG

We want to build a DFA that will recognize if the string WYSWYG appears anywhere in a sequence of characters. For simplicity, let's assume that no other characters will appear except these four.

To extend this to handle inputs that might containadditional characters besides these four, put the other possible characters on the transitions headed back to the start state.

NP = P ?

The problem of $NP = P$ is one of the most important open problems in computer science. The simple way to think about it is that it asks the question is it harder to find an answer or check the answer. The thing that makes it intersting is that for something that seems so simple and obvious people have been unable to prove or disprove it. To understand this problem more compleatly we have to start with what P and NP are. The are the names of complexity classes. They are groups of problems that can be solved in a particular time or less. The ones we have talked about is EXP, P, and NP.

EXP is the set of decision problems solvable in exponential time
NP (nondeterministic polynomial time) is the set of decision problems where the yes answer can be checked in polynomial time.
P is the set of decision problems that can be solved in polynomial time.

venn diagram — The relationship between P, NP, and EXP. The open question is whether the circle labelled NP is the same as the circle labelled P, or larger.