Archive for the ‘Computer Science’ Category

Sipser on P versus NP

December 22, 2012

On October 3, 2006 Michael Sipser was at Harvard to give the following lecture on the P versus NP problem:

This talk is arguably the very best introduction to computational complexity I have ever come across. I highly recommend it.

October 2, 2012

Consider the deterministic finite automaton [1] illustrated below

[ state diagram courtesy of Michael Sipser [1] ]

Henceforth, we will call this automaton $M_1$. Note that $M_1$ has three states, labeled $q_1$, $q_2$, and $q_3$. The start state is $q_1$ (note the arrow coming from nowhere) and the accept state is $q_2$ (note the double circle). There are two possible inputs, labeled $0$ and $1$, and, depending on the input, the automaton will jump from one state to another. In the diagram above these state transitions are depicted using arrows connecting two states.

Suppose that the automaton $M_1$ receives an input string such as $1101$ (which the automaton reads from left to right). Since the start state is $q_1$ and the first input symbol is $1$, the automaton will jump to state $q_2$. The second input symbol is $1$, so the automaton will remain at $q_2$. The automaton reads the third input symbol, which is $0$, and then jumps from state $q_2$ to state $q_3$. The last input symbol is $1$ and thus the automaton jumps from state $q_3$ to state $q_2$. Hence, the state sequence corresponding to the input string $1101$ is the following

$q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_2$

After reading the last symbol in the input string, $M_1$ produces an output. Since the final state $q_2$ is the accept state, we have that the automaton produces the output “accept”. Were the final state not $q_2$, the automaton would produce the output “reject”. We conclude that this automaton accepts the input string $1101$. What other input strings does $M_1$ accept? Michael Sipser answers this question in [1]:

Experimenting with this machine on a variety of input strings reveals that it accepts the strings $1$, $01$, $11$, and $0101010101$. In fact, $M_1$ accepts any string that ends with a $1$, as it goes to its accept state $q_2$ whenever it reads the symbol $1$. In addition, it accepts strings $100$, $0100$, $110000$, and $0101000000$, and any string that ends with an even number of $0$s following the last $1$. It rejects other strings, such as $0$, $10$, $101000$.

A set of strings is called a language [1]. The set of all input strings accepted by the deterministic finite automaton $M_1$ is a language which we denote by $L (M_1)$.

__________

Formal definition

A deterministic finite automaton (DFA) consists of a finite set of states $Q$, a finite input alphabet $\Sigma$ that tells us what the allowed input symbols are, a transition function $\delta : Q \times \Sigma \to Q$ that tells us how to jump from one state to another, a start state $q_0 \in Q$, and a set of accept states $A \subseteq Q$. A deterministic finite automaton (DFA) is thus a $5$-tuple of the form

$(Q, \Sigma, \delta, q_0, A)$

The deterministic finite automaton $M_1$ which we discussed earlier in this post is defined formally as follows

$M_1 := (\{q_1, q_2, q_3\}, \{0,1\}, \delta, q_1, \{q_2\})$

where the transition function $\delta: \{q_1, q_2, q_3\} \times \{0,1\} \to \{q_1, q_2, q_3\}$ is defined enumeratively as

$\delta (q_1, 0) = q_1$,        $\delta (q_2, 0) = q_3$,        $\delta (q_3, 0) = q_2$

$\delta (q_1, 1) = q_2$,        $\delta (q_2, 1) = q_2$,        $\delta (q_3, 1) = q_2$

Alternatively, we could view each state transition $q_i \xrightarrow{\sigma} q_j$ as an ordered triple $(q_i, \sigma, q_j)$, which might be easier to implement in some programming languages.

__________

Computing state sequences

Given an input string $\sigma = \sigma_1 \sigma_2 \dots \sigma_n$ over a given alphabet $\Sigma$, how do we obtain the corresponding state sequence? I solved that problem last January. I will not repeat myself here, but the crux of the matter is that the final state can be obtained using a left-fold

$\text{foldl} \, \delta \, q_0\, [\sigma_1, \sigma_2, \dots, \sigma_{n}]$

whereas the entire state sequence can be computed using a left-scan

$\text{scanl} \, \delta \, q_0\, [\sigma_1, \sigma_2, \dots, \sigma_{n}]$

Lacking a better name, I called this procedure the “scanl trick“, as I used the Haskell function scanl to implement it. Please let me know if you find a more sophisticated name for this “trick”.

__________

data State = Q1 | Q2 | Q3 deriving (Read, Show, Eq)

type Input = Integer

-- define state-transition function
delta :: State -> Input -> State
delta Q1 0 = Q1
delta Q1 1 = Q2
delta Q2 0 = Q3
delta Q2 1 = Q2
delta Q3 0 = Q2
delta Q3 1 = Q2
delta  _ _ = error "Invalid input!"

-- define initial state
initialstate :: State
initialstate = Q1

-- create list of accept states
acceptstates :: [State]
acceptstates = [Q2]

-- create infinite list of input sequences
inputss :: [[Input]]
inputss = concat $iterate g [[]] where g = concat . map (\xs -> [ xs ++ [s] | s <- [0,1]]) -- create accept predicate isAccepted :: [Input] -> Bool isAccepted inputs = finalstate elem acceptstates where finalstate = foldl delta initialstate inputs -- compute language recognized by the DFA language :: [[Input]] language = filter isAccepted inputss Some remarks about this script are in order. Please note that: • Sets are represented by lists. Strings are represented by lists, too. The latter is more natural than the former. Sets of strings become lists of lists. • A new data type is created to represent the states, which we denote by Q1, Q2, and Q3. The input symbols are integers. • Note that Input is a type synonym, inputs is a list of inputs symbols (i.e., an input string), and inputss is a list of lists of inputs (i.e., a list of input strings). Yes, it is a bit confusing. • The final state is computed using the higher-order function foldl (left-fold). We check if the final state is an accept state using the list membership predicate elem. If you have any objections to this script, please do let me know. Let us now test it! We load it into GHCi and voilà: *Main> -- check list of input strings *Main> take 31$ inputss
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]
*Main> -- compute the language of the automaton
*Main> -- (let us extract some 40 input strings only)
*Main> take 40 language
[[1],[0,1],[1,1],
[0,0,1],[0,1,1],[1,0,0],[1,0,1],[1,1,1],
[0,0,0,1],[0,0,1,1],[0,1,0,0],[0,1,0,1],
[0,1,1,1],[1,0,0,1],[1,0,1,1],[1,1,0,0],
[1,1,0,1],[1,1,1,1],[0,0,0,0,1],[0,0,0,1,1],
[0,0,1,0,0],[0,0,1,0,1],[0,0,1,1,1],[0,1,0,0,1],
[0,1,0,1,1],[0,1,1,0,0],[0,1,1,0,1],[0,1,1,1,1],
[1,0,0,0,0],[1,0,0,0,1],[1,0,0,1,1],[1,0,1,0,0],
[1,0,1,0,1],[1,0,1,1,1],[1,1,0,0,1],[1,1,0,1,1],
[1,1,1,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,0,0,0,1]]

The list of input strings is exactly the same I posted yesterday. The input strings in the language $L (M_1)$, or, to put it more precisely, the input strings in $L (M_1)$ that are displayed above either end with a $1$, or end “with an even number of $0$s following the last $1$“, as mentioned by Sipser in [1]. Why is that? The last $1$ in the input string puts $M_1$ in state $q_2$, and an even number of $0$s after that $1$ lead to transitions from $q_2$ to $q_3$ and back to $q_2$, e.g.,

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

or

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

or

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

It would also be interesting to take a look at the state sequences corresponding to the input strings in $L(M_1)$. We compute these state sequences using the infamous “scanl trick“:

*Main> -- create list of sequences of states
*Main> let statess = map (\xs -> scanl delta initialstate xs) language
*Main> -- take the "first" 20 state sequences
*Main> take 20 statess
[[Q1,Q2],[Q1,Q1,Q2],[Q1,Q2,Q2],
[Q1,Q1,Q1,Q2],[Q1,Q1,Q2,Q2],[Q1,Q2,Q3,Q2],
[Q1,Q2,Q3,Q2],[Q1,Q2,Q2,Q2],[Q1,Q1,Q1,Q1,Q2],
[Q1,Q1,Q1,Q2,Q2],[Q1,Q1,Q2,Q3,Q2],[Q1,Q1,Q2,Q3,Q2],
[Q1,Q1,Q2,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],
[Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q2,Q2],
[Q1,Q1,Q1,Q1,Q1,Q2],[Q1,Q1,Q1,Q1,Q2,Q2]]

Note that all state trajectories end in state Q2, as we expected.

__________

References

[1] Michael Sipser, Introduction to the Theory of Computation (2nd edition), Thomson Course Technology, 2006.

Generating all words over an alphabet

October 1, 2012

An alphabet $\Sigma$ is a finite set of symbols. A word $w$ of length $n$ over an alphabet $\Sigma$ is a sequence of symbols from $\Sigma$, i.e.,

$w : \{0,1,\dots,n-1\} \to \Sigma$

Alternatively, we can view a word $w$ of length $n$ over the alphabet $\Sigma$ as an $n$-tuple (i.e., an ordered list with $n$ elements) over $\Sigma$, i.e., $w \in \Sigma^n$. The set of all finite words over $\Sigma$, including the empty word $\varepsilon$, is denoted by $\Sigma^*$, where $*$ is the Kleene star.

We thus encounter the following problem:

Problem: Given an alphabet $\Sigma$, how do we generate all the words over $\Sigma$? In other words, given $\Sigma$, how do we generate the Kleene closure $\Sigma^*$?

The following Haskell script solves this problem:

g :: [a] -> [[a]] -> [[a]]
g alphabet = concat . map (\xs -> [ xs ++ [s] | s <- alphabet])

allwords :: [a] -> [[a]]
allwords alphabet = concat $iterate (g alphabet) [[]] where alphabet must be a finite list, otherwise the execution of the script won’t ever terminate. The script above, although short, uses a lot of machinery: list comprehension, higher-order functions map and iterate, concatenation of lists of lists, and partial function application. Let us test this script. First, we load it into GHCi. Then we can run a GHCi session: *Main> -- define alphabet *Main> let alphabet = [0,1] *Main> -- define function f *Main> let f = g alphabet *Main> -- check type *Main> :t f f :: [[Integer]] -> [[Integer]] *Main> -- apply f to several lists of lists *Main> f [[]] [[0],[1]] *Main> (f . f) [[]] [[0,0],[0,1],[1,0],[1,1]] *Main> (f . f . f) [[]] [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] So far, so good. Suppose that we would like to find all words over alphabet $\Sigma_2 := \{0,1\}$ whose length is less than or equal to $4$. How many such words are there? There are $|\Sigma_2|^k = 2^k$ words of length $k$. Hence, there are $\displaystyle\sum_{k=0}^n 2^k = \frac{2^{n+1} -1}{2-1} = 2^{n+1} - 1$ binary words of length less than or equal to $n$. Hence, if we make $n = 4$, then we obtain $2^{n+1}-1 = 31$. Continuing our GHCi session: *Main> take 31$ allwords alphabet
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

Very nice! We could use this in Coding Theory! For example, suppose that we would like to find all binary words of length $8$ whose Hamming weight is equal to $5$. There are

$\displaystyle\binom{8}{5} = \frac{8!}{3! 5!} = 56$

such words. We can find them as follows:

*Main> -- take all words of length less than or equal to 8
*Main>  let words = take 511 \$ allwords alphabet
*Main> -- filter out binary words of length 8
*Main> let wordsL8 = filter (\xs -> length xs == 8) words
*Main> length wordsL8
256
*Main> -- filter out binary words of length 8
*Main> -- and also of Hamming weight equal to 5
*Main> let wordsL8H5 = filter (\xs -> sum xs == 5) wordsL8
*Main> length wordsL8H5
56
*Main> wordsL8H5
[[0,0,0,1,1,1,1,1],[0,0,1,0,1,1,1,1],[0,0,1,1,0,1,1,1],
[0,0,1,1,1,0,1,1],[0,0,1,1,1,1,0,1],[0,0,1,1,1,1,1,0],
[0,1,0,0,1,1,1,1],[0,1,0,1,0,1,1,1],[0,1,0,1,1,0,1,1],
[0,1,0,1,1,1,0,1],[0,1,0,1,1,1,1,0],[0,1,1,0,0,1,1,1],
[0,1,1,0,1,0,1,1],[0,1,1,0,1,1,0,1],[0,1,1,0,1,1,1,0],
[0,1,1,1,0,0,1,1],[0,1,1,1,0,1,0,1],[0,1,1,1,0,1,1,0],
[0,1,1,1,1,0,0,1],[0,1,1,1,1,0,1,0],[0,1,1,1,1,1,0,0],
[1,0,0,0,1,1,1,1],[1,0,0,1,0,1,1,1],[1,0,0,1,1,0,1,1],
[1,0,0,1,1,1,0,1],[1,0,0,1,1,1,1,0],[1,0,1,0,0,1,1,1],
[1,0,1,0,1,0,1,1],[1,0,1,0,1,1,0,1],[1,0,1,0,1,1,1,0],
[1,0,1,1,0,0,1,1],[1,0,1,1,0,1,0,1],[1,0,1,1,0,1,1,0],
[1,0,1,1,1,0,0,1],[1,0,1,1,1,0,1,0],[1,0,1,1,1,1,0,0],
[1,1,0,0,0,1,1,1],[1,1,0,0,1,0,1,1],[1,1,0,0,1,1,0,1],
[1,1,0,0,1,1,1,0],[1,1,0,1,0,0,1,1],[1,1,0,1,0,1,0,1],
[1,1,0,1,0,1,1,0],[1,1,0,1,1,0,0,1],[1,1,0,1,1,0,1,0],
[1,1,0,1,1,1,0,0],[1,1,1,0,0,0,1,1],[1,1,1,0,0,1,0,1],
[1,1,1,0,0,1,1,0],[1,1,1,0,1,0,0,1],[1,1,1,0,1,0,1,0],
[1,1,1,0,1,1,0,0],[1,1,1,1,0,0,0,1],[1,1,1,1,0,0,1,0],
[1,1,1,1,0,1,0,0],[1,1,1,1,1,0,0,0]]

where we used function take (again) and higher-order function filter. The two predicates were built using anonymous functions.

I am happy with this script. Please let me know in case you are not.

__________

Related:

Combinatorial Explosion

September 16, 2012

An amusing Japanese cartoon on combinatorial explosion:

Tastefully done, I would say. The target audience consists not of this blog’s readers, but rather of their children.

Hat tip: Michael Lugo

Distance between two words

January 31, 2009

Consider a finite set $\Sigma$ with $|\Sigma|$ distinct elements which we will call symbols. We will call set $\Sigma$ an alphabet. A word (also known as string) of length $n$ over set $\Sigma$ is formed by constructing an $n$-tuple of symbols from alphabet $\Sigma$

$w = (w_1, w_2, w_3, \ldots, w_n)$

where $w_i \in \Sigma$ for all $i \in \{1, 2, \ldots, n\}$. A string of length $n$ will be called an $n$-string. The set of all $n$-strings is given by the cartesian product

$\Sigma^n = \Sigma \times \Sigma \times \ldots \times \Sigma = \displaystyle\prod_{i=1}^n \Sigma$.

For example, in coding theory one usually works with binary words, i.e., words over alphabet $\mathbb{F}_2 = \{0,1\}$. The set of all binary words of length $n$ is $\mathbb{F}_2^n = \{0,1\}^n$, whose cardinality is $| \mathbb{F}_2^n | = 2^n$.

In this post we will work only with words over the alphabet

$\Sigma = \{\text{a} ,\text{b} ,\text{c} ,\text{d} ,\text{e} ,\text{f} ,\text{g} ,\text{h} ,\text{i} ,\text{j} ,\text{k} ,\text{l} ,\text{m} ,\text{n} ,\text{o} ,\text{p} ,\text{q} ,\text{r} ,\text{s} ,\text{t} ,\text{u} ,\text{v} ,\text{w} ,\text{x} ,\text{y} ,\text{z}\}$

which is known as the Latin alphabet, and whose 26 symbols are known as letters. For example,  $\textbf{cat}$ and $\textbf{car}$ are represented by the 3-strings $s_1 = (\text{c}, \text{a}, \text{t})$ and $s_2 = (\text{c}, \text{a}, \text{r})$, respectively, where $s_1, s_2 \in \Sigma^3$.

__________

Hamming distance

Given two strings of equal length, the Hamming distance between them is the number of positions for which the corresponding symbols are different. In other words, the Hamming distance between two strings of equal length is the minimum number of symbol substitutions required to change one string into the other.

Let function $d_{H} : \Sigma^n \times \Sigma^n \rightarrow \mathbb{Z}_0^{+}$ be defined by

$d_{H} (v, w) = \displaystyle \sum_{i=1}^n \mu \left( v_i, w_i \right)$

where function $\mu : \Sigma \times \Sigma \rightarrow \{0,1\}$ is defined by

$\mu (a, b) = \displaystyle\left\{\begin{array}{rl} 0 & \text{if} \quad{} a = b\\ 1 & \text{if} \quad{} a \neq b\\ \end{array}\right.$

then $d_H (s_1, s_2)$ is the Hamming distance between $n$-strings $s_1$ and $s_2$. For example, if $s_1 = (\text{c}, \text{a}, \text{t})$ and $s_2 = (\text{c}, \text{a}, \text{r})$, then we have $d_H (s_1, s_2) = 1$ because $s_1$ and $s_2$ only differ in one symbol (the last one).

Suppose we are given an $n$-string over the Latin alphabet $\Sigma$. If we replace the letter at position $i$ with another letter in $\Sigma$, where $i \in \{1, 2, \ldots, n\}$, we can obtain a total of $|\Sigma| - 1$ new $n$-strings, each within Hamming distance $1$ of the original $n$-string. Let us call these $n$-strings neighbors of the original $n$-string. Thus, an $n$-string has a total of $(|\Sigma| - 1) n$ neighbors.

__________

Word graphs

If two $n$-strings are neighbors of one another when their Hamming distance is equal to $1$, then a graphical approach would be the natural way to go. Let $G = (N,E)$ be an undirected graph whose set of nodes is $N = \Sigma^n$ (set of all $n$-strings over alphabet $\Sigma$), and whose set of edges is $E \subset \Sigma^n \times \Sigma^n$. Two nodes are connected by an edge if their Hamming distance is equal to $1$. Hence the total number of nodes in $G$ is $|N| = |\Sigma^n| = 26^n$, and the total number of edges in $G$ is

$|E| = \displaystyle\frac{n | \Sigma^n|}{2} \left(| \Sigma| - 1\right) = \displaystyle\frac{n}{2} | \Sigma|^n\left(| \Sigma| - 1\right)$,

because each node has $(|\Sigma| - 1) n$ neighbors, there are $|\Sigma^n|$ nodes, and each edge is counted twice so we need to divide the total by $2$. Note that $G$ is a regular graph (of degree $|\Sigma| - 1$) because all nodes have the same number of neighbors.

For example, let $n=3$ and let us consider the $3$-string $(\text{c}, \text{a}, \text{r})$, which has $(|\Sigma| - 1) n = 75$ neighbors. Out of these $75$ words, I could count $21$ words which actually mean something in the English language:

bar, ear, far, gar, jar, mar, oar, par, tar, war, yar, cor, cur, cab, cad, cam, can, cap, cat, caw, cay.

Please let me know if I forgot to include any word in this list. These words form a sub-graph of the graph of all $3$-strings. Note that the words

bar, car, ear, far, gar, jar, mar, oar, par, tar, war, yar

are all neighbors of one another, and hence, they form a clique of size $12$. The words

car, cor, cur

form a clique of size $3$. The words

cab, cad, cam, can, cap, car, cat, caw, cay

are all neighbors of one another as well, and thus they form a clique of size $9$. The subgraph formed by the word “car” and its neighbors which make sense in the English language is illustrated below, where the three cliques are easy to identify

[ graph generated with Graphviz ]

It is not practical to depict the whole graph of $3$-strings over alphabet $\Sigma$ since it contains $|\Sigma^3| = |\Sigma|^3 = 26^3 = 17576$ nodes and $|E| = 659100$ edges!

__________

Python code

In case you are wondering: no, I did not type the 26 symbols of the Latin alphabet in $\LaTeX$. That would have been way too cumbersome. All it took was one single line of Python code:


", ".join([("\text{" + chr(i) + "}") for i in range(ord('a'),ord('z')+1)])



Suppose we would like to find all strings within Hamming distance of $1$ of string $(\text{c}, \text{a}, \text{t})$. The following Python script automates the process:

def MutateString(s, alphabet, index):
li = []
for ch in alphabet:
if ch != s[index]:
li.append(s[:index] + ch + s[index+1:])
return li

# build Latin alphabet (lowercase symbols only)
Sigma = [chr(i) for i in range(ord('a'),ord('z')+1)]

# obtain list of mutated strings
print "Mutate 1st symbol:\n" + ", ".join(MutateString('cat', Sigma, 0)) + '\n'
print "Mutate 2nd symbol:\n" + ", ".join(MutateString('cat', Sigma, 1)) + '\n'
print "Mutate 3rd symbol:\n" + ", ".join(MutateString('cat', Sigma, 2)) + '\n'


The graph of the word “car” and its neighbors was generated also by a Python script using the GvGen library.

def HammingDistance(s1, s2):
"""Computes the Hamming distance between strings s1 and s2"""
assert len(s1) == len(s2)
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

import gvgen

# list of words
words = ['car', 'bar', 'ear', 'far', 'gar', 'jar', 'mar', 'oar', 'par', 'tar', 'war', 'yar', 'cor', 'cur', 'cab', 'cad', 'cam', 'can', 'cap', 'cat', 'caw', 'cay']

# creates the new graph instance
graph = gvgen.GvGen()
graph.smart_mode = 1

# creates graph nodes
nodes = []
for elem in words:
nodes.append(graph.newItem(elem))

# creates graph edges
for i in nodes:
for j in nodes:

# extracts the labels of each node
node1 = i['properties']['label']
node2 = j['properties']['label']

# links nodes i and j if the Hamming
# distance between their labels is 1
if HammingDistance(node1,node2) == 1: