# Question
Title: Decomposing the search problem into several small problems
I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either:

1. Searching through the original graph. or
2. By decomposing it into several subset of problems $P\_1,P\_2, \dots,P\_n$.

Ideally $sol(P )=sol(P\_1)\cup sol(P\_2)\cup \ldots \cup(P\_n)$ with no preprocessing (i.e the union of the subproblems correspond directly to the solution of the problem).

I have no constraint; though prefer the underlying graph to be a DAG and the problem to be a reachability problem. Google seems to fail on finding such papers.

# Answer
Consider the $k$-path problem: given a graph $G$ and an integer $k$, is there a simple path of length $k$ in $G$? To solve $k$-path, it suffices to find two paths of length $k/2$ and a vertex $v$ s.t. the paths only intersect in $v$. In general, such algorithms are known as "meet in the middle", or "split and list". Basically, split the problem into two or more parts, enumerate all possible solutions for the smaller parts, and finally combine them to a solution.

Horowitz and Sahni give the classical example for subset-sum (given a list of $n$ integers, is there a sublist whose elements sum up to $0$?). First, split the list into two parts of length $n/2$. For both parts, enumerate all possible $2^{n/2}$ sums. Using sorting and binary search, check if there are two sublists that sum up to zero. In general, such an algorithm gives you a halved exponential dependence on the input size. There are some more examples of this too, for starters you could check out \[1\].

Also, to add to D.W.'s answer, divide-and-conquer also seems to satisfy your requirements. More specifically, look into graph decompositions. A classical one is the Lipton-Tarjan planar separator theorem, which leads to efficient divide-and-conquer algorithms on planar graphs. There are plenty of other separator theorems and decompositions out there too. One that you see often for *directed* graphs is a modular decomposition.

---

\[1\] Fomin, Fedor V., and Dieter Kratsch. Exact exponential algorithms. Springer, 2010.
> 3 votes

# Answer
The term you are looking for is "divide-and-conquer". There are gazillions of divide-and-conquer algorithms; any algorithm textbook should show you quite a few examples. Divide-and-conquer is more general, because it also allows you to do some merger operation to combine the solutions to each piece -- but many divide-and-conquer algorithms do follow the form you are looking for, so I think "divide-and-conquer" should be a helpful search term.

In graphs, one common use of divide-and-conquer is to decompose the graph into connected components or strongly connected components, and then work on each component separately. In many cases, no pre-processing or post-processing to glue together the solutions is needed: you just take a union of the solution for each component.
> 3 votes

---
Tags: graphs, reference-request, search-algorithms, search-problem
---


# Question
Title: Physical layer services & hardware protocols
I am searching the content of this topic but I am not sure what should be the content for this topic. This is relate to Computer Network. My topic is `Physical layer services & hardware protocols.`

What should be content for this topic.

# Answer
Just a quick answer:

Hardware protocols are at the lowest level of the Open System Interconnection (OSI) model and are usually a mix of

* hardware specifications (cables, connectors, signals, ...)
* how data is exchanged between the hardware devices (start of communication, end of communication, data exchange, flow of control, timings, error handling, ...)

Typical examples of hardware protocols are: serial port RS-232, Parallel port IEEE 1284, USB , Ethernet, bus protocols, ...

Physical layer services are those functions used to correctly implement and manage the communication between devices at the physical layer: e.g. open a port, convert bits to timed signals, change the bit-rate, close a port, send data, multiplexing, flush data, ...
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$
Is $L=\\{a^nb^m|m\geq2^n\\}$ a context-free language?

# Answer
Let $p$ be the integer in Ogden's lemma, and consider the word $a^q b^{2^q} \in L$ for $q$ satisfying $2^q \> p$, marking its $b$ part. According to the lemma, we can write $a^q b^{2^q} = uxyzv$ where $xz$ contains between one and $p$ letters $b$. Since $uyv \in L$ and $xz$ contains at least one $b$, it follows that it also contains at least one $a$. For $ux^2yz^2v$ to be in $L$, we need $xz$ to contain at least $2^{q+1}-2^q = 2^q$ letters $b$, contradicting our choice of $2^q \> p$.

More generally, this works for any language of the form $\\{a^nb^m : m \geq f(n)\\}$ for any $f(n) = \omega(n)$, or even whenever $\limsup f(n)/n = \infty$.
> 1 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: In cache addressing, what value is placed in the offset field?
There is a 64 KB 1-word cache, and a word is 32 bits. From that I can derive that the length of the tag field is 16 bits, the length of index field is 14 bits, and, as my professor taught me, there is always 2 bits left behind for a byte offset.

Why the offset field is 2 bits, other than it fills in the remaining 2 bits of the word, and what its contents is was never covered in the course.

But when I looked around on Google, I read, and correct me if I am wrong, that the length of the offset field can vary. Although I have found answers on how to determine the length, I could not find anything about determining its contents when a read hit/miss is performed. My professor merely said "the byte offset is not used to select the word in the cache".

Just looking for clarification.

# Answer
Paul A. Clayton gives the answer in a comment.

You say a word has 32 bits. An implicit assumption is that we want to be able access every of the four bytes, so we need two bits to make this distinction.
> 1 votes

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: Decidable languages kleene star closure - question on a proof
I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the original decider of the language to approve the partition of each branch.

My question is, I can't understand how we can do this non-deterministic split on a word whose length we do not yet know. if the word is very big then there exist more partitions, thus more branches are needed.

So, i don't understand how this "non-deterministic split" can be materialized.

Also, if someone has another proof of this closure via turing machines it will be more than welcome!

# Answer
> 8 votes
It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be decided or not, regardless of how much time it will take to figure out. Therefore, an NTM will sometimes be more convenient to reason about, as we can abstract the "try all possible ways to do this", into "guess the right way to do this". However, the abstraction is only valid if we have a finite number of possibilities to try, of course.

**So, for the Kleene star closure:**

Assume that we have a decidable language $A$. Given that $A$ is decidable, there exists a decider for $A$, let us call it $M\_A$. From this $M\_A$, we can now construct a decider of $A^\ast$, let us call that decider $M\_{A^\ast}$.

This is a description of how $M\_{A^\ast}$ works:

**On input $w$:**

**If $w = \varepsilon$ (the empty string), accept**

**For all possible splits of $w$ into $w\_1,w\_2,...,w\_k$: if $M\_A$ accepts all the strings $w\_1, w\_2, ..., w\_k$, then accept**

**If all splits have been tried without success, reject.**

Lets look at an example where $A = \\{w \in \\{a,b,c\\}^\ast \\; | \\; w \\; \text{starts with} \\; ab \\; \text{or ends with} \\; c\\}$

For instance, we have that $\\{c, ab, ac, bc, cc, aac\\} \subset A$, but $\\{a, b, aa, ba, bb, ca\\} \cap A = \emptyset$.

Now, let us look at how $M\_{A^\ast}$ will determine whether or not the string $ccab$ is in $A^\ast$:

First, $M\_{A^\ast}$ checks the trivial case. Since $w \neq \varepsilon$, it cannot accept right away. It now has to try all the 8 possible splits of $ccab$ listed here:

$S\_1 = \\{ccab\\}$

$S\_2 = \\{cca, b\\}$

$S\_3 = \\{cc, ab\\}$

$S\_4 = \\{c, cab\\}$

$S\_5 = \\{cc, a, b\\}$

$S\_6 = \\{c, c, ab\\}$

$S\_7 = \\{c, ca, b\\}$

$S\_8 = \\{c, c, a, b\\}$

> **NOTE:** $S\_8$ contains three `,` to allow us to split the string $w$ into each of its letters. Since we can either contain or remove each one of the commas, there are $2^3 = 8$ total splits.

You could argue that split $1$ is not a real split, but since it complies with our definition of a split, $M\_A'$ has to check whether $A$ accepts all $w' \in S\_1$, which is only $ccab$. $M\_A$ rejects $ccab$ because it does not start with $ab$ or end with $c$. In $S\_2$, $cca$ is rejected by $M\_A$, and hence $M\_A'$ does not have to check $b$ and proceeds to split $S\_3$. In $S\_3$, both strings are accepted by $M\_A$. $cc$ is accepted because it ends with $c$, and $ab$ is accepted because it starts with $ab$. The machine $M\_A'$ now accepts, and hence $ccab \in A^\ast$, simply because $cc \in A$ and $ab \in A$.

# Answer
> 4 votes
With a Turing machine, you can always compute the length of the input as the first stage of the algorithm.

But, in this case, you don't need to. Suppose the language $L$ is decided by the Turing machine $M$. We can decide $L^\*$ nondeterministically as follows. Start advancing the head through the input $w\_1w\_2\dots w\_n$. At each step nondeterministically either just keep going or simulate $M$ to see if the word $w\_1\dots w\_k$ that you've seen so far is in $L$. If it's not in $L$, reject immediately. If it is in $L$, continue walking through the input, building up a new word $w\_{k+1}w\_{k+2}\dots w\_{k'}$ and nondeterministically guessing when to check whether that's in $L$.

You don't need to partition the input before you start: you can do it "on the fly".

# Answer
> 2 votes
> So, I don't understand how this "non-deterministic split" can be materialized.

I take it that your problem is understanding non-determinism.

In essence, the machine can make guesses: whenever the transition table offers more than one choice, it will just pick one of the alternatives. Intuitively, we then assume the machine always picks right; formally, we require it to do good in *one* of all possible computations¹.

So, given an input $w$ for we should check whether it is in $L^\*$ for some recursive $L$, the machine can *guess* a split

$\qquad\displaystyle w = w\_1 w\_2 \dots w\_k$

and then run decide $M\_L$ of $L$ and combine the results; we output

$\qquad M\_L(w\_1) \cdot \dots \cdot M\_L(w\_k)$.

We can actually do that because we look at Turing machines and so we can, in particular, simulate $M\_L$ as often as we want². Now, since we "always guess right" our machine finds a valid split *if there is one*.

Of course, we can get rid of the nondeterminism and just try all possible splits -- there's your alternative proof.

---

1. Please check out the formal definitions again. It's important to get them right when doing theory.
2. To convince yourself, come up with a C program (or similar) that does this.

---
Tags: computability, turing-machines, closure-properties, nondeterminism
---


# Question
Title: Prove that A* is the smallest reflexive and transitive set containing A
I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question:

We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$

> Show that A\* is a reflexive and transitive set containing A and if B is any other reflexive and transitive set containing A, then $A^\*\subseteq B$.

I've shown that Kleene star satisfies these two conditions. I've tried partitioning B into two sets with $A = B \cup C $ and trying a constructive proof but this hasn't led any where. I also am considering a proof by contradition but don't know where to start.

Can you help me with a hint on how to approach this problem?

# Answer
Hint: Try the usual approach to show set inclusion! That is, pick $w \in A^\*$ and show that $w \in B$.

Next hint:

> Apply transitivity of $B$ repeatedly.

More elaborately:

> If $w \in A^\*$ then either $w = \varepsilon \in B$ or there are $w\_1, \dots, w\_k \in A \subseteq B$ with $w = w\_1 \cdot \dots \cdot w\_k$. Now, because $BB \subseteq B$ we have $w\_2' = w\_1 w\_2 \in B$. For the same reason, $w\_2' w\_3 \in B$. And so on. Perform induction for the general proof.
> 1 votes

---
Tags: formal-languages, closure-properties
---


# Question
Title: Why don't people use Fermat's little theorem to check if number is prime?
There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula

$\qquad a^{p-1} \equiv 1 \pmod p$,

to check if a number is prime?

# Answer
> 4 votes
Expanding on Karolis's answer, the probabilistic primality tests used in practices, the Miller-Rabin test and the Solovay-Strassen test, are both based on modifications of the test you suggest, also known as the Fermat primality test. (Same for the less common Baillie-PSW test.) The problem with the Fermat test is that it is fooled by some composites known as Carmichael numbers.

The Solovay-Strassen test replaces the test $a^{n-1} \equiv 1 \pmod{n}$ with the similar formula $a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}$. Here $\left(\frac{a}{n}\right)$ is a Jacobi symbol, which for prime $n$ and $a \nmid n$ is equal to $1$ if $a$ is a quadratic residue modulo $n$ (i.e. has a square root modulo $n$) and to $-1$ if $a$ is a quadratic non-residue modulo $n$. There is a GCD-like algorithm for computing the Jacobi symbol, which makes the test feasible. It can be shown that if $n$ is an odd composite, then at least half the $a$s fail this test.

The Miller-Rabin test relies on the (similar) property that $1$ has two square roots modulo a prime, but more modulo composites. The idea is to check that $a^{n-1} \equiv 1 \pmod{n}$ and $a^{(n-1)/2} \equiv \pm 1 \pmod{n}$. If $a^{(n-1)/2} \equiv 1 \pmod{n}$, then we check that $a^{(n-1)/4} \equiv \pm 1 \pmod{n}$. And so on. The test *fails* if for some $k$, $a^{(n-1)/2^k} \equiv 1 \pmod{n}$ but $a^{(n-1)/2^{k+1}} \not\equiv \pm 1 \pmod{n}$. It can be shown that if $n$ is an odd composite, then at least three quarters of the $a$s fail this test (and so less iterations are needed compared to the Solovay-Strassen test).

---
Tags: discrete-mathematics, number-theory, primes
---


# Question
Title: find the minimum number of vertices in a directed graph from which the other vertices are reachable
In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met.

(in other words all of the other vertices are reachable from these chosen vertices.)

I want to find the minimum number of such vertices.

Actually this problem arises in social networks when we want to find the minimum number of people to which if we send a message then all of the network members will get that.(suppose that we know when someone gets the message he/she will send that to all of his/her followers.)

Can anyone help?

# Answer
> 2 votes
The problem can be reduced to finding "sources" (opposite of "sinks", nodes with in-degree zero) in the graph. Suppose there is an optimal solution in which $B$ is one of the chosen nodes and there is an edge $A\rightarrow B$. Then we can put $A$ instead of $B$ in the solution and still cover the whole graph ($A$ can reach $B$, so it can reach all the nodes reachable from $B$). On the other hand, "sources" have to be chosen because they are not reachable from any other node. Then we should repeatedly find "source" nodes, chose them and mark all the vertices reachable from them as covered.

If there are no "source" nodes, then the graph must have cycles. All the nodes in a cycle are equivalent in terms of the nodes they can reach. Thus, they can be simplified into a "supernode". If eventually the supernode becomes a "source" and hence chosen by the algorithm, that means an arbitrary node of the cycle can be chosen.

So the algorithm repeatedly performs iterations of "finding source nodes" and "simplification" until the whole graph is covered.

---
Tags: algorithms, graphs, social-networks
---


# Question
Title: How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.

What is the easiest method to do this in practice? Constructing a random d-regular graph, which is proven to be a.a.s. an expander?

I also read about Margulis constructions and Ramanujan graphs that are expanders and a construction using a zig-zag product. Wikipedia gives a nice but very short overview: http://en.wikipedia.org/wiki/Expander\_graph#cite\_note-10 But which method do I choose in practice?

For me, these methods seem all very complicated to implement and in particular to understand and maybe quite specific. Aren't there easier methods, maybe based on permutations or so, to practically generate a sequence of d-regular expander graphs?

Is it maybe easier to construct d-regular bipartite expander graphs?

I also have another question: What about families of bad d-regular expanders? Does such a notion make sense? Can one construct a family of d-regular graphs (that are of course connected) that is as bad as possible in the sense of an expander?

Thanks in advance.

# Answer
> 11 votes
If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular.

Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$. For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$. Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$.

As an example, the 7-vertex graph in the family is a 7-cycle with vertices numbered sequentially around the cycle; there are self-loops on $6$, $0$, and $1$; finally, there are chords joining $3$ and $5$, and $2$ and $4$.

See https://mathoverflow.net/questions/124708/an-expander-graph for further discussion and references. There are lots of more detailed pointers by searching on "expander" at CSTheory, Math.SE, and MO.

As Yuval Filmus points out, the random construction is likely to give better results in general, but of course may not yield an expander (especially for small graphs).

# Answer
> 0 votes
Given a random regular graph is an expander w.h.p. (follow the reference given in the documentation of the MATLAB code linked below), I once used the following:

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m

---
Tags: graphs, combinatorics, cryptography, discrete-mathematics, expanders
---


# Question
Title: If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?
I've seen in previous exams that professors marked the theory as correct:

> If $L$ is CFL and $\overline{L}$ is CFL, then L is regular.

I just don't see how this would work. How would we prove such a thing? I also can't come up with contradicting languages.

# Answer
> 10 votes
As Shaull noted in the comments, $\\{a^n b^n\\}$ works. The language is trivially context-free but not regular, so I'll show the complement is context-free. A word which is not of the form $a^n b^n$ is either $a^n b^m$ where $n\neq m$, or not of the form $a^n b^m$ at all. So

$(a+b)^{\ast}-{a^n b^n}=\\{a^i b^j: i \neq j\\} \cup ((a+b)^{\ast}-a^{\ast} b^{\ast})$

which is a sum of context-free language $\\{a^i b^j: i \neq j\\}$ and the complement of $a^{\ast} b^{\ast}$ which is a regular language.

Another way to see it is that $\\{a^n b^n\\}$ is a deterministic context-free language, which is a class closed under complement. In other words any nonregular DCFL is a counterexample to the question.

I'll leave the following question to the reader:

> Suppose $L$ and $\overline L$ are CFLs, is $L$ a DCFL?

---
Tags: formal-languages, context-free, closure-properties
---


title: Wiring Length Minimization

text:
# Question
Title: Wiring Length Minimization
My Problem is like this:

1. I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where wire can go.
2. There are some special Nodes, called splitters, from where a single wire can be splitted to 2 or more up to k. The k can be taken constant for now but it varies from node to node. Not all nodes are splitters.
3. There is one source of power from where a wire will emerge. It is the source. The wire has to be taken to n sinks.
4. An edge can take any number of wires traversing through it in either direction.
5. The the total wire length has to be minimized.
6. The nature of graph, planar or euclidean is not known.

**Example**: Below is a sample network. Nodes are named as numbers and edges are provided with equal weights of 1. Source is Node1 and Sinks are Node5, Node9 and Node13. In case 1 Node6 is Splitter node. In case 2 Node6 and Node4 are splitter nodes. The splitter node's k=3, i.e., it can take in one wire and split it out to 3 wires.

**Case 1**. Only one splitter Node. It makes sense to split at Node6.

**Case 2**. Two splitter Node. It makes sense to split at Node4 instead of Node6.

I am looking for different strategies to find out a generic solution for this problem. The graph presented here is of a smaller scale as compared to the problem in hand. The graph is static and can not be changed (i mean the solution should not suggest any new edge or propose new splitter location ). Any reference to research paper published on this kind of problem is also welcomed.

**Case 3**. Two splitter Node. It makes sense to split at Node4 and Node14. Note that this case has edge weights changed for Edge 8-12, 6-10 and 10-11. The important thing in this case is retracing of a wire after getting splitted from Node14.

# Answer
> 8 votes
This problem is NP-hard.

Assume every vertex is a splitter that can split to any number of degrees, then your problem is precisely the Steiner tree problem on a graph, where the set of source and sink vertices are the required vertices.

# Answer
> 3 votes
I don't have a solution to your problem, but I've got an intermediate simplification. Constraint 2 (each splitter node $i$ is allowed to split one wire into no more than $k\_i$ wires) is what has me stumped.

The simplification is that you can eliminate all the intermediate (square) nodes. Create a graph with just the source node, the sink nodes, and the splitter nodes.

1. In your original graph find the shortest path from the source node to each splitter node and add an edge in the new graph from the source node to the splitter node with that length.
2. Given two splitter nodes, $i$ and $j$ find the shortest path from $i$ to $j$ in the original graph and add an edge in the new graph from $i$ to $j$ with that length.
3. For every splitter $i$ and every sink $j$ find the shortest path from $i$ to $j$ in the original graph and add an edge in the new graph from $i$ to $j$ with that length.

Now you have a fully connected graph of $N$ splitters, (plus the source and the sinks). The edges have costs and you are trying to find a minimum cost tree that satisfies the constraint that each splitter node $i$ has no more than $k\_i$ children.

This (reduced) problem seems harder than the degree-constrained minimum spanning tree problem, which is NP-hard, because there is a different degree $k\_i$ on each node rather than a single degree constraint. But it is also different because you aren't actually looking for a spanning tree. Rather the desired minimum tree can leave out some of the splitter nodes. I don't know whether this second difference makes the problem easier or harder.

# Answer
> 1 votes
@Chao Xu, I also found Steiner to be nearest approximation to my problem. I am exploring Ant based systems to solve this problem.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: How to apply the substitution method to n/2?
I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.

In standard induction proofs you prove a base case, assume it holds for n then show it holds for n+1 and therefore show it applies to integers larger than the base case.

For when you solve recurrences like T(n) = T(n/2) the proof has a base, assumes T(n/2) then proves it holds for T(n). Does this proof not only hold for the numbers that are multiples of two of the base cases? Would this not require an infinitely large number of base cases to show what it holds for?

Could someone please explain this to me?

# Answer
> 1 votes
You're entirely correct - if all you prove is $T(1)$ and $T(n/2) \Rightarrow T(n)$, then you prove that $T(n)$ holds for all powers of $2$. One way to fix that is to prove $T(n)$ for all odd $n$, but that defeats the idea of induction. Instead, usually one actually proves the stronger $T(\lfloor n/2 \rfloor) \Rightarrow T(n)$ or $T(\lceil n/2 \rceil) \Rightarrow T(n)$, and both are enough to deduce $T(n)$ for all $n$.

In many cases, if you can prove $T(n/2) \Rightarrow T(n)$ then you can also prove the stronger claims, but it's technically more awkward. So instead of dealing with this mess, you are only shown the weaker claim. The "interesting" ideas are found already there, and to prove the stronger claim requires just working harder but no new ideas (other than routine tricks used for handling floors and ceilings).

# Answer
> 1 votes
I suppose what you mean by "substitution method" is guess & proof (by induction).

Be aware that you *do* perform an induction proof. By strengthening the induction hypothesis to *all* $n' \< n$, the proof can go through -- *if* your parameters are naturals. That where you trip since $\frac{n}{2}$ is not always natural.

There are two ways for approaching this.

* In the context of divide & conquer recurrences we usually solve the recurrence only for $n=2^k$ (that's how we get the form at hand); that should occur somewhere in the presentation/textbook. We do that because things become less messy to deal with, technically, and because we know that (under certain conditions¹) the result carries over.
* Solve the original recurrence which probably has the form

$\qquad T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + f(n)$.

Many methods for solving recurrences become messy because of the rounding, but guess & proof should be fine.

---

1. It's not trivial to see when and why we get the correct result by this method, but that's probably beyond your concern right now.

---
Tags: proof-techniques, recurrence-relation, induction
---


# Question
Title: Number of different output labels in Local Binary Pattern
I'm studying about Local Binary Pattern and I'm having trouble understanding the following part about the number of output labels for binary patterns from *Computer Vision using Local Binary Patterns*, by Pietikäinen et al. (2011):

> Another extension to the original operator uses so called *uniform patterns* \[53\]. For this, a uniformity measure of a pattern is used: $U$ ("pattern") is the number of bitwise transitions from 0 to 1 or vice versa when the bit pattern is considered circular. A local binary pattern is called uniform if its uniformity measure is at most 2. For example, the patterns 00000000 (0 transitions), 01110000 (2 transitions) and 11001111 (2 transitions) are uniform whereas the patterns 11001001 (4 transitions) and 01010011 (6 transitions) are not. In uniform LBP mapping there is a separate output label for each uniform pattern and all the non-uniform patterns are assigned to a single label. Thus, the number of different output labels for mapping for patterns of $P$ bits is $P(P-1)+3$. For instance, the uniform mapping produces 59 output labels for neighborhoods of 8 sampling points and 243 labels for neighborhoods of 16 sampling points.

I don't understand why the number of different LBP output labels is $P(P-1) + 3$. Could someone explain why?....

Thnx for any help =)

Update: I think I have some idea already :) I included an example from my book:

# Answer
> 1 votes
A pattern with uniformity measure exactly 2 is determined by: the value $b$ of bit 0, the position $i\>0$ of the first bit that is different from bit 0 and the position $j$ of the first bit after the $i$th that is different from bit $i$. (We may have $j=0$, for example in the pattern 00001111, which has $b=0$, $i=4$, $j=0$.) How many choices are there for the triple $(b,i,j)$? Clearly, there are two choices for $b$. For $i$ and $j$, there are $\tfrac12(P-1)(P-2)$ choices with $i\<j$ and $P-1$ choices where $j=0$. Thus, the total number of choices for $i$ and $j$ is $$ \tfrac12(P-1)(P-2) + P-1 = \tfrac12P(P-1)\\,.$$

To that, you need to add three more labels: all zeroes, all ones and the label for all patterns of uniformity measure strictly more than 2.

---
Tags: image-processing, binary-arithmetic
---


# Question
Title: Has there been a lexer that takes in much more than a regular language?
I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to be "approximately" regular languages.

Yet I would be interested if any attempt in any programming language, possibly esoteric language, has been taken to completely eschew the conventional division between type-3 lexers and type-2 parser.

# Answer
* FORTRAN is famous for having some difficult to lex constructs, but those difficulties result probably more from having been designed before the classification was established (or at least known in programming circles)
* Several languages are described with a type-3 lexers but some characteristic are easier to handle by feeding information from the parser to the lexer (C/C++ typedef, C++ templates, Ada/VHDL attributes)
* Several languages have layout rules (Python, Haskell) which are usually not described as type-3 lexers (I don't know if it is possible to do so or not)
> 1 votes

---
Tags: reference-request, regular-languages, compilers
---


title: How to compute Gabor feature vector?

text:
# Question
Title: How to compute Gabor feature vector?
I'm working on semi automatic texture segmentation using level set and gabor feature vector described by Manjunath und Ma \[1\]. I consider their feature representation is better than others since I can get good result on several images but somehow performs really bad on other images data. So I guess there's something wrong with my understanding.

They describe that the feature vectors consist of $\mu\_{mn}$ (mean) and $\sigma\_{mn}$ (standard deviation). I use scale $S = 4$ and orientation $K = 6$, thus my feature vector will be 48 dimension (4 * 6 * 2 = 48):

$f = \\{ \mu\_{00}, \sigma\_{00}, \mu\_{01}, \sigma\_{01}, \mu\_{02}...\mu\_{35}, \sigma\_{35} \\} \tag1$

I am confused with their equation:

$W(x, y) = \int I(x\_1,y\_1)g\_{mn} * (x - x\_1, y - y\_1) dx\_1 dy\_1 \tag2$

$\mu\_{mn} = \int \int |W\_{mn}(x,y)|dxdy \tag3$

$\sigma\_{mn} = \sqrt{ \int \int (|W\_{mn}(x,y) - \mu\_{mn}|)^2 dxdy } \tag4$

So my first question is: **are $\mu$ and $\sigma$ simply mean and average?** So far, I just average every pixel value of the magnitude to obtain $\mu$ and compute the standard deviation to obtain $\sigma$.

After I compute the feature vector, I need to do distance measure between two vectors $f\_i$ and $f\_j$

$d(i, j) = \sum\_{}^{m}\sum\_{}^{n} d\_{mn}(i, j) \tag5$

$d\_{mn}(i, j) = |\frac{\mu\_{mn}^i - \mu\_{mn}^j}{\alpha(\mu\_{mn})}| + |\frac{\sigma\_{mn}^i - \sigma\_{mn}^j}{\alpha(\sigma\_{mn})}| \tag6$

I'm really puzzled with $\alpha(\mu\_{mn})$ and $\alpha(\sigma\_{mn})$ ? **What are they?** I have tried to calculate 48 standard deviations from $ (1)$

$\alpha = \\{ \alpha(\mu\_{00}), \alpha(\sigma\_{00}), \alpha(\mu\_{01}), \alpha(\sigma\_{01}), \alpha(\mu\_{02})...\alpha(\mu\_{35}), \alpha(\sigma\_{35}) )\\} \tag7$

and use it to calculate the distance function but I'm not convinced with my calculation since **it seems not better than simple euclidean distance.**

---

1. Texture Features for Browsing and Retrieval of Image Data by B.S. Manjunath and W.Y. Ma (1996)

# Answer
$\mu$ and $\sigma$ are simply mean and standard deviation. I assume there is also a normalizing coefficient out there. Or the normalization as you mentioned comes from $\alpha$, since it $\alpha$s are vectors composed of the standard deviation and mean.
> 1 votes

---
Tags: algorithms, image-processing, computer-vision
---


# Question
Title: Finding an isomorphism between finite automata
Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states.

More specifically, heres an example:

It's easy to generate a regular expression by hand and see that both FA produce: b + (ab\*a(a+b)), though their states are renumbered, they are identical.

What I'm trying to do is figure out a way to check if the two states are the same apart from state renumbering without generating a regular expression.

Since the states are just renumbered, I'm thinking it has something to do with permutations of the states(1 2 3 4) but am not seeing how to determine if they are equivalent. I'm thinking it has something to do with input like this and relating it to the 24 permutations of the states:

```
Left       Right
1 a 2      4 a 3
1 b 4      4 b 1
2 a 3      3 a 2
2 b 2      3 b 3
3 a 4      2 a 1
3 b 4      2 b 1

```

Im more so trying to figure out the algorithm to renumber the states Any ideas or help is greatly appreciated!

# Answer
I can identify a permutation on the set of states $\\{1,2,3,4\\}$ the turns the left-hand diagram into the right-hand one. In other words, if you renumber the states on the left-hand diagram, you get the right-hand diagram. Thus the two automata are identical up to renumbering.
> 3 votes

# Answer
Here's a simpler approach to testing whether two descriptions of regular languages $L\_1, L\_2$ are descriptions of the same language ($L\_1 = L\_2$).

1. Compute the complement of $L\_2$, denoted $\overline{L\_2}$. If it's represented as a DFA, this can be done in polynomial time (linear I believe).
2. Compute the intersection of the automata, $L\_1 \cap \overline{L\_2} $. If they're both DFAs, then this is can be done in quadratic time and space.

If the intersection is null, then you know there's no word in $L\_1$ which is not in $L\_2$, meaning that $L\_1 \subseteq L\_2$.

Perform the same test with $L\_1$ and $L\_2$ interchanged. If $L\_1 \subseteq L\_2$ and $L\_2 \subseteq L\_1$, then the langauges are equal, meaning the minimal DFAs are isomorphic. If your input DFAs are known to be minimal, this will test for isomorphism.
> 5 votes

# Answer
Your question seems to concern only deterministic finite automata $\mathcal{A}\_1 = (Q, A, \cdot\_1, i\_1, F\_1)$ and $\mathcal{A}\_2 = (Q, A, \cdot\_2, i\_2, F\_2)$ with the same set of states $Q = \\{1, ..., n \\}$. It is simpler to deal with complete automata (just add a new state $0$ in both automata and put $q \cdot a = 0$ when $q \cdot a$ is undefined) Here is a simple approach. You have to find a permutation $\pi$ on $\\{0, 1, ..., n \\}$ such that $\pi(0) = 0$, $\pi(i\_1) = i\_2$, $\pi(F\_1) = F\_2$ and for all $q \in \\{0, 1, ..., n \\}$ and $a \in A$, $\pi(q \cdot\_1 a) = \pi(q) \cdot\_2 a$.

This gives you a simple algorithm to find $\pi$. Start in $i\_1$ and perform a depth-first search of the graph of $\mathcal{A}\_1$ to compute $\pi$ step by step. Then verify that $\pi$ satisfies the required properties.

In your example, $i\_1 = 1$ and $i\_2 = 4$, thus $\pi(1) = 4$. Then $2 = 1 \cdot\_1 a$ whence $$ \pi(2) = \pi(1 \cdot\_1 a) = \pi(1)\cdot\_2 a = 4 \cdot\_2 a = 3. $$ Next $3 = 2 \cdot\_1 a$ whence $$ \pi(3) = \pi(2 \cdot\_1 a) = \pi(2)\cdot\_2 a = 3 \cdot\_2 a = 2. $$ Finally, $4 = 3 \cdot\_1 a$ whence $$ \pi(4) = \pi(3 \cdot\_1 a) = \pi(3)\cdot\_2 a = 2 \cdot\_2 a = 1. $$ It remains to check that $\pi$ defines an isomorphism, but this is now easy: \begin{align} \pi(1 \cdot\_1 b) &= \pi(4) = 1 \text{ and } \pi(1)\cdot\_2 b = 4 \cdot\_2 b = 1 \\ \pi(2 \cdot\_1 b) &= \pi(2) = 3 \text{ and } \pi(2)\cdot\_2 b = 3 \cdot\_2 b = 3 \\ \pi(3 \cdot\_1 b) &= \pi(4) = 1 \text{ and } \pi(3)\cdot\_2 b = 2 \cdot\_2 b = 1 \\ \pi(4 \cdot\_1 a) &= \pi(0) = 0 \text{ and } \pi(0)\cdot\_2 a = 0 \cdot\_2 a = 0 \\ \pi(4 \cdot\_1 b) &= \pi(0) = 0 \text{ and } \pi(0)\cdot\_2 b = 0 \cdot\_2 b = 1 \\ \end{align} Finally $F\_1= \\{4\\}$ and $F\_2 = \\{1\\} = \pi(F\_1)$.
> 3 votes

---
Tags: automata, finite-automata, graph-isomorphism
---


title: Does $DTIME(2^n)$ contain $NSPACE(n)$ ?

text:
# Question
Title: Does $DTIME(2^n)$ contain $NSPACE(n)$ ?
As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?

# Answer
> 3 votes
Generally, for functions $f(n) \in \Omega(\log(n))$, we have that $$ \mathrm{NSPACE}(f) \subseteq \mathrm{DTIME}(2^{O(f)}) $$ A proof can be found on slide 28 onwards of the slide set from:

```
 http://www.informatik.uni-leipzig.de/alg/lehre/ws12_13/KOMPL/folien-eng.pdf

```

I don't know if $\mathrm{NSPACE}(n) \subseteq \mathrm{DTIME}(2^{n})$ is true. TSP is in $\mathrm{NSPACE}(n)$, but the best deterministic algorithm known is in $ \mathrm{DTIME}(n^22^{n})$ (as far as I know).

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Is there evidence that using dynamic languages has an impact on productivity?
I am wondering if there are any experiments that show the existence or the non-existence of a correlation between usage of a dynamic language (such as Python, Ruby, or even languages that run on the Java platform such as Groovy, Clojure) over a static language (such as C/C++), and the difference in the productivity.

# Answer
> 11 votes
While I'm not aware of research on productivity, there's been research on comprehension. Philip Wadler has been collecting links to papers on this topic: see this post and this one.

# Answer
> 8 votes
Specifically on productivity, Hanenberg has investigated the impact in development time when the same task was implemented in Java (static) vs Groovy (dynamic). Their results were described in the following paper:

Static vs. dynamic type systems: an empirical study about the relationship between type casts and development time, 2011.

There's also been research on the impact of static/dynamic typing in software maintainability. This is a very recent paper on the subject:

An empirical study on the impact of static typing on software maintainability, 2014

The authors have also published previous work on the same area, including this one (also listed in one of the links that Suresh mentioned):

Do Static Type Systems Improve the Maintainability of Software Systems? An Empirical Study, 2012 (PDF available)

Furthermore, if you intend to pursue this research topic, keep in mind that one of the key problems here is the definition of **productivity** \- and how exactly are you going to measure it.

---
Tags: programming-languages, empirical-research, software-engineering
---


# Question
Title: Graphs with bounded degree and small max independent set
Graphs with degree $\Delta$ have a maximum independent set of size $\alpha \geqslant \frac{n}{\Delta}$ where $n$ is the number of vertices. But, are there graphs such that $\alpha \approx \frac{n}{\Delta}$, or even $\alpha = c \frac{n}{\Delta}$ for some constant $c \leqslant 1$?

# Answer
> 1 votes
First of all, the correct bound is $n/(\Delta + 1)$. This is tight for unions of cliques of size $\Delta+1$. If you want a connected graph, take a union of $\Delta$-cliques and connect them in a path or a cycle. This gives $n/\Delta$, so there is a small loss over the lower bound $n/(\Delta+1)$. If you want a connected regular graph, add a matching to the previous graph.

---
Tags: graphs
---


# Question
Title: Is it possible to prove EQTM is undecidable by the Rice theorem?
Given the problem $EQ\_{TM} = \\{ \langle M\_1, M\_2\rangle \mid M\_1 \text{ and } M\_2 \text{ are } TM, L\_{M\_1} = L\_{M\_2}\\}$, is it possible to prove that this is undecidable by using (a variant of) Rice theorem?

I have proven this problem by reduction to $E\_{TM}$, but was wondering if it was easier to do with Rice.

# Answer
You can reduce it to a problem about single Turing machines by fixing one of the inputs. For example, you can take $M\_2$ to be some Turing machine which accepts nothing. This shows that $EQ\_{TM}$ is at least as hard as deciding emptiness.

Another approach is to encapsulate the pair of Turing machines $M\_1,M\_2$ in one Turing machine $M$, which upon input $0x$ will simulate $M\_1$ on $x$, and upon input $1x$ will simulate $M\_2$ on $x$ (on the empty input it can arbitrarily halt). There is a simple reduction showing that $EQ\_{TM}$ is equivalent to the corresponding problem for $M$, and then you can apply Rice's theorem.
> 6 votes

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: Updating maximum sum subrectangle in a sparse matrix when one element is changed
I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane's 2-d algorithm of O(m^2 n) for sufficiently sparse matrices. The sparse matrix algorithm, which is also O(m^2 n) time for dense matrices, matching Kadane's algorithm, can be found here https://stackoverflow.com/questions/17558028/maximum-sum-subrectangle-in-a-sparse-matrix .Now I want to know if the optimal solution can be updated quickly if one entry in the matrix is changed. By "quickly" I mean something like O(m log n) time or better. It's possible that perhaps the matrix does not have to be sparse to work out a solution, however a solution when N = O(min(m,n)) would be ok. Preprocessing is also ok as long as the amortized cost of preprocessing time per element changed matches or beats something like O(m log n) time for m changes.

# Answer
> 1 votes
Yes, absolutely. There is a straightforward way to do what you want, if you work through the details of the algorithm given at the link in your question. The trick is to use persistent data structures, to avoid re-computing data multiple times.

The algorithm given at your link builds a one-dimensional array `A[]` for each `i,j` (where $1\le i \le j \le m$), where `A[k] = sum{B[i..j,k]}`. So, let's keep a copy of each of those arrays. That can be done by using a persistent data structure for the array, say, a persistent balanced binary tree. In this way, the output of the algorithm shown there is $m(m-1)/2$ 1-D arrays, one for each `i,j`.

Now let's say that the entry `B[i*,k]` gets modified in the matrix `B`. Obviously, this affects the entry `A[k]` in each of the arrays for `i,j`, where `i <= i* <= j`. That's at most $O(m^2)$ of the 1-D arrays. And, we can go update that one entry of those arrays in $O(m^2)$ time. In fact, for a sparse matrix, the running time is even less: it is something like the square of the number of non-zero entries in the `k`-th column of the matrix `B`.

---
Tags: algorithms, dynamic-programming, matrices
---


title: Is regex golf NP-Complete?

text:
# Question
Title: Is regex golf NP-Complete?
As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation problem) is the puzzle of defining the shortest possible regular expression that accepts every word in set A and no word in set B. Norvig's post includes an algorithm for generating a reasonably short candidate, and he notes that his approach involves solving an NP-complete Set Cover problem, but he's also careful to point out that his approach doesn't consider every possible regular expression, and of course his isn't necessarily the only algorithm, so his solutions aren't guaranteed to be optimal, and it's also possible that some other assuredly polynomial-time algorithm could find equivalent or better solutions.

For concreteness' sake and to avoid having to solve the optimization question, I think the most natural formulation of Regular Expression Separation would be:

> Given two (finite) sets $A$ and $B$ of strings over some alphabet $\Sigma$, is there a regular expression of length $\leq k$ that accepts every string in $A$ and rejects every string in $B$?

Is anything known about the complexity of this particular separation problem? (Note that since I've specified $A$ and $B$ as finite sets of strings, the natural notion of size for the problem is the total lengths of all strings in $A$ and $B$; this swamps any contribution from $k$). It seems highly likely to me that it *is* NP-complete (and in fact, I would expect the reduction to be to some sort of cover problem) but a few searches haven't turned up anything particularly useful.

# Answer
> 16 votes
Assuming the TCS-variant of regex, the problem is indeed NP-complete.

We assume that our regexes contain

* letters from $\Sigma$, matching themselves,
* $+$, denoting union,
* $\cdot$, denoting concatenation,
* $\*$, denoting Kleene-Star,
* $\lambda$, matching the empty string

and nothing else. Length of a regex is defined as the number of characters from $\Sigma$. As in the comic strip, we consider a regex to match a word, if it matches a substring of the word. (Changing any of these assumptions should only influence the complexity of the construction below, but not the general result.)

That it is in NP is straightforward, as explained in the comments (verify a candidate-RE by translating it into an NFA and running that on all words from $A$ and $B$).

In order to show NP-hardness, we reduce Set cover:

> Given a universe $U$ and a collection $C$ of subsets of $U$, is there a set $C' \subseteq C$ of size $\leq k$ so that $\bigcup\_{S \in C'} S = U$?

We translate an input for Set cover into one for regex golf as follows:

* $\Sigma$ contains one character for each subset in $C$ and one additional character (denoted $x$ in the following).
* $A$ contains one word for each element $e$ of $U$. The word consists of exactly the characters representing subsets in $C$ that contain $e$ (in arbitrary order).
* $B$ contains the single word $x$.
* $k$ is simply carried over.

This reduction is obviously in P and equivalence is also quite simple to see:

* If $c\_1, \ldots, c\_k$ is a solution for the set cover instance, the regex $c\_1 + \cdots + c\_k$ is a solution to regex golf.
* A regex matching the empty subword would match $x$. Thus, any regex solving the golf problem has to contain at least one letter from each of the words in $A$. Hence, if the golf instance is solvable, there is a set of at most $k$ letters from $\Sigma$ so that each word in $A$ is covered by this set of letters. By construction, the corresponding set of subsets from $C$ is a solution to the set cover instance.

---
Tags: complexity-theory, np-complete, regular-expressions
---


# Question
Title: Simulating a TM with a 2-head, right moving TM
Is it possible to simulate a regular Turing Machine with a TM with the following specs?

1. There are two heads, one of which can read, one of which can write
2. Both heads can only move right
3. When a head reads (or it writes) it moves right

I know it's possible to simulate a TM that only moves right. But, is it possible to simulate the left moves as well?

# Answer
> 3 votes
Yes you can simulate a standard Turing machine, indeed you can easily simulate a Tag System which is Turing complete (and can simulate a Turing machine with only a polynomial-time slowdown).

Informally to simulate a k-tag system, you keep the write head at the end of the tape (on the first blank symbol) and use internal states to store the production rules; with the read head you can read k symbols, and append the symbols of the corresponding production rule at the end of the tape.

For example if you have a 2-tag system with the following production:

```
a --> aab

```

and the tape is:

```
a b a b c a b c _
^               ^
Read            Write

```

you can read the first two symbols and apply the production:

```
a b a b c a b c a a b _
    ^                 ^
    Read              Write

```

Furthermore it is also easy to see how a k-Tag system can simulate a Turing machine; a hint: use a special symbol to mark the position of the head, and just rewrite (with one symbol of delay) on the right what you read with the read head but on the "new copy" change the symbol on the right of the head marker according to the transition table of the simulated TM and also change the head marker position one step left or right (and at every "copy cycle" write also two "empty spaces" to allow the expansion of the tape); use internal states to keep track of the copy phase and of the current state of the simulated TM.

For example if you use # to mark the head position and one transition is:

```
q1, read a -> q2, write b, move left

a c # a a b c a b c _ a _
    ^RH               ^WH (q1 and c are buffered in the internal states)

a c # a a b c a b c _ a _
      ^RH               ^WH (here the "simulated" TM is on symbol "a"
in state q1 and we can apply the transition above)

a c # a a b c a b c _ a # c b _
        ^RH                   ^WH (q2 is buffered in the internal state)

continue with the copy and start another "cycle":

a c # a a b c a b c _ a # c b a b c a b c _
                    ^RH                   ^WH

```

... let me know if you need more hints.

---
Tags: turing-machines, turing-completeness, simulation
---


# Question
Title: Why are there multiple computer languages instead of multiple libraries?
If someone realizes that a computer language is deficient under some aspect or the other, couldn't he just create a **library** for the new language instead of a new language?

Couldn't you have a library In C that lets you process list as if they were lisp? Or that write simple code as if it was Python?

Why does evolution have to mean breaking with the past?

# Answer
> 7 votes
There are many features that cannot be simulated by a library (or rather - are very hard to simulate by a library), for example garbage collection, or exception handling. And even features which can, say object-oriented programming, are much easier to use when they're part of the core language.

You can certainly have a library in C implementing an interactive python interpreter, and then you can just put python code in quotes as input. There are several problems with this: it will be hard to debug, and syntax highlighting could be a nightmare. However, the real issue here is that if you've gone that far, you actually have a python interpreter.

Simulating python in any other way seems difficult: how would you implement control structures, for example? How would you implement message passing, operator overloading and so on? You will need to replace the usual operators by named functions like **add** and so on, which aren't going to be very easy to use. And to implement message passing you will need to use variadic functions with string parameters, taking care to handle somehow named parameters. You will do all that, and still lack the interactive python interpreter.

You can say the same regarding any other language - even if you could simulate language features, it would be awkward. This even goes to object-oriented programming in the C++ tradition. You will need to have a special calling mechanism which wouldn't be able to do static type-checking, for example. And how about templates? This sounds even harder. You will need to have void\* pointers, and to instantiate the code yourself.

Summarizing, modern languages are more than just syntactic sugar above C, and even if they were just that, it would still be very awkward to program them directly in C.

---
Tags: programming-languages
---


title: Turing Machine states

text:
# Question
Title: Turing Machine states
When defining a Turing Machine formally, you enumerate its states. But I don't understand what states a TM can be in. Reading, Writing, and moving the head are the only ones that come to mind.

Specifically, the turing I am trying to describe behaves like this:

```
    WHILE the symbol under the FH head is not $ DO
        IF this symbol is not marked 0 THEN write it on the tape
        ELSE write the symbol 1 on the tape
            Read the next symbol (which is a 0) and write a marked 0 on the tape
    Write $ on the tape

```

Where FH is the reading head which begins on the far left of the tape, and BH is the writing head which begins on the blank space after the last symbol on the tape. Once a cell is read or written into, the head in question moves one cell to the right.

The starting configuration for the TM is this: 100!0110\\$ where the 0! indicates that the 0 is a marked symbol. The FH head begins on the first 1, and the BH head begins on the blank cell after the \\$. The ending configuration for that TM with that input is then 100!0110\\$1010!110\\$

So, when describing this TM, what would its states be? Thanks!

# Answer
Raphael is correct in stating the states of a TM is a theoretical construct defining the operating program. What you are thinking of ("reading", "writing", and "moving") are operations the machine can do out of a particular state.

Wikipedia has a nice little write up about it. Explaining that each state, tells the machine what next operation to perform based off of a current state.
> 2 votes

---
Tags: terminology, turing-machines
---


# Question
Title: How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet?
I am looking for an automated way to answer the question: what are the URLs on the world wide web that contain at least two strings from a set of strings.

So if I have a set of strings {"A", "B" and "C"} -- I want to know, what pages on the world wide web contain "A" and B", "A" and "C", "B" and "C" or "A", "B" and "C."

Obviously, for this simple example: Google it!

But I want a scaleable, automated, and free solution. Google does not permit automated queries. Yahoo makes you pay.

One idea I have is (1) start with a URL, (2) check the text at that URL for the search strings (3) parse out the links from the text (4) record that you have checked the page and if it contains the strings then (5) search the links from the initial URL. Repeat until you have searched the tree.

How feasible is this in terms of time and space on a single commodity machine -- given the size the internet? The internet is really, really big -- but only a comparatively few pages will contain these strings (they are proper names).

I don't want to index the whole web as if my laptop were google!

Most of the crawler's time will be spent confirming that the pages don't contain the strings.

I'm trying to get a rough ballpark to understand if this is even remotely feasible.

# Answer
This is not remotely feasible. The number of pages indexed by Google and Bing are in the tens of billions. To get anything close to what they are doing you are going to need to process terabytes of data. It will take you days to download all of these webpages using your home internet connection at full speed. And you will probably hit some bandwidth cap by your ISP before you finish. Even if there was no bandwidth cap from your ISP you would have to be careful in how you request the pages. If you request too many from one server in too short a time you'll probably get your ip blocked by that server. So you'll need some kind of program to optimize the order in which you visit these hundreds of millions of URLs. You will never be able to finish visiting all of the URLs in your queue. New content will be added to the internet faster than you can keep up with it.
> 2 votes

---
Tags: algorithm-analysis, search-problem, searching
---


# Question
Title: What is usually the next step after showing the VC dimension?
I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\epsilon}ln \frac{d}{\delta}$ and with probability at least $1-\delta$ I will get a hypothesis with error at most $\epsilon$.

My question concerns what is usually the next step(s),with regard to the big picture of learning a structure $X$, after showing its VCD?

I thought about studying other complexity measures for $X$ but wish to hear others suggestions.

# Answer
A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other subject. While VC dimension might be useful in coming up with algorithms (as in the case of SVMs), it appears to have no practical import.

When constructing theoretical algorithms such as learning algorithms under the PAC model, the story could be different, but unfortunately I don't know too much about that. From the little I've seen, VC dimension doesn't get mentioned even there. In fact, it seems that VC dimension is mentioned mostly in literature attempting to relate it to other parameters.
> 6 votes

# Answer
If, as you've stated, you're interested in coming up with a PAC learning algorithm then finite VC-dimension is a prerequisite. This follows from what is sometimes referred to as the Fundamental Theorem of Statistical Learning Theory. In brief this results says that if a concept class $C$ has finite VC-dimension $d$ then a learning algorithm that produces a hypothesis $h \in C$ consistent with a sample $S$ of size $m$ is a PAC learning algorithm, where $$ m \ge c\_0 \left(\frac{1}{\epsilon}\log{\frac{1}{\delta}} + \frac{d}{\epsilon}\log{\frac{1}{\epsilon}}\right). $$ Notice that we haven't made any reference to time taken by the learning algorithm, instead we've placed a bound on the number of samples required. This is why I said prerequisite, since obviously no algorithm running in polynomial time could make use of more than a polynomial number of samples.

My favorite reference for this result is the book An Introduction Computational Learning Theory by Kearns and Vazirani, although I much prefer the shifting proof of the Sauer-Shelah Lemma to the more common inductive approach they use. It appears as Theorem 3.3. They then go on to show (Theorem 3.5) that this result is tight within a factor of $\log{\frac{1}{\epsilon}}$.
> 6 votes

---
Tags: machine-learning, learning-theory, vc-dimension
---


title: Is this language context free?

text:
# Question
Title: Is this language context free?
In a recent test, I was asked to recognize if the below language is context free:

$\qquad\displaystyle L = \\{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\\}$

I think it is context free, and can be accepted by below context free grammar, where $S$ is the start symbol and $Y$ is a non-terminal:

$\qquad S \to S0 \mid Y$

$\qquad Y \to 0Y1 \mid \epsilon$

However, my answer was considered wrong and that the language $L$ is not context free.

I'm confident about my answer, but the response has got me confused. Is my understanding correct? Please let me know if I've missed something.

# Answer
You can use Ogden's lemma. Choose the word $w = 0^p1^p0^p$ for large enough $p$, and mark the rightmost $0^p$. Ogden's lemma gives you a decomposition $w = uxyzv$ with $xz$ pumpable and containing at least one marked point. Since $xz$ contains a $0$, it can't contain a $1$, as otherwise $ux^2yz^2v \notin 0^\*1^\*0^\*$. A simple case analysis now leads to a contradiction.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Efficient Median Algorithm With Very Constrained Operators
What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are not allowed. The algorithm I have come up with so far seems very inefficient and goes like so:

1. For an array of length n, create a working array of length 2n by doing pairwise Max() comparisons for every pair of elements in the input array. This 2n array is guaranteed not to contain the lowest value from the original (or one fewer of the lowest value if there were ties for the lowest value)
2. Recursively call (1) n/2 times
3. Take min() of final array

There's got to be a faster algorithm!

# Answer
> 1 votes
I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all that just to find the minimum; instead of making that large array (which sounds like it contains $\binom n 2$ elements, not $2n$, unless I misunderstood you), you can basically do the following:

Starting from the left, take every pair of consecutive elements, and put the minimum of the two on the right. Something like this in pseudocode:

```
temp1 = min(array[i], array[i+1])
temp2 = max(array[i], array[i+1])

array[i] = temp2
array[i+1] = temp1

```

What will happen is that the minimum element gets moved all the way to the far right using $2(n-1)$ mins and maxs. We can then do our recursive call on the first $n-1$ elements, and repeat until we finally pull out the median.1

---

1 Some of you reading this will note that basically what we end up with is a bubble sort (reverse in the example I gave) where we stop as soon as we figure out the median. If you decide to move the max to the right instead, then we pretty much *are* doing a normal bubble sort, but stopping once we get the median.

---
Tags: algorithms, search-algorithms
---


# Question
Title: Empirical studies about benefits of Q&A sites for programming
I'm looking for empirical papers which investigate if a user can benefit from Q&A sites like Stack Overflow. I welcome any papers related to this topic, e.g:

* an experiment, investigating if a specific task can be executed faster,
* an analysis, investigating if a user understands the solutions on Q&A sites or if he just does copy&paste without thinking about it,
* a comparative analysis of the code quality of users with access to Q&A sites in contrast to users without internet access (but just offline documentation of APIs).

# Answer
There was a presentation on ICSE 2011, at the New Ideas and Emerging Results track, entitled "How do programmers ask and answer questions on the web?". They only had initial results, but they sounded very interesting and promising. Maybe you could contact the authors if you need more info (they're from the Dept. of Comput. Science, University of Victoria, Victoria, BC, Canada). Here is the full reference:

Treude, C.; Barzilay, O.; Storey, M. **How do programmers ask and answer questions on the web?**. In Proc. of the 33rd International Conference on Software Engineering (ICSE), 2011.

UPDATE: This paper was just mentioned at the Stack Exchange blog:

Chris Parnin, Christoph Treude, Lars Grammel, Margaret-Anne Storey. **Crowd Documentation: Exploring the Coverage and the Dynamics of API Discussions on Stack Overﬂow**. Georgia Institute of Technology, Tech. Rep, 2012. \[PDF\]
> 4 votes

# Answer
The conference paper "StackOverflow and GitHub: associations between software development and crowdsourced knowledge" looked at the correlation between activity on StackOverflow and GitHub for users who have accounts on both. From the abstract:

> In this paper we investigate the interplay between StackOverflow activities and the development process, reflected by code changes committed to the largest social coding repository, GitHub. Our study shows that active GitHub committers ask fewer questions and provide more answers than others. Moreover, we observe that active StackOverflow askers distribute their work in a less uniform way than developers that do not ask questions. Finally, we show that despite the interruptions incurred, the StackOverflow activity rate correlates with the code changing activity in GitHub.

Bogdan Vasilescu, Vladimir Filkov, Alexander Serebrenik. **StackOverflow and GitHub: associations between software development and crowdsourced knowledge.** 2013 ASE/IEEE International Conference on Social Computing (Washington DC, USA, September 8-13, 2013), pp.188-195
> 3 votes

---
Tags: reference-request, software-engineering, empirical-research, social-networks
---


# Question
Title: Why have additional symbols on a Turing machine?
What is the point of non-binary printed letters on a turing machine? I understand that these need to be omitted to get a computable number, but why are they used in the first place?

# Answer
Turing Machines are an abstract model of computation, their purpose is to define in a mathematical way what problems are theoretically computable and which are not.

It is true that a binary alphabet is enough to reach the full expressive power of Turing Machines. However, when playing with them "in practice" to prove theorems and to communicate these proofs, it can be more convenient to use more symbols, instead of encoding everything in binary. We could always go back to binary if it's absolutely needed.

An extreme example of the same sort would be "why are we still using 26 characters to write texts, now that we know that two are enough? It would save time when learning the alphabet!".
> 4 votes

# Answer
Turing machines with many symbols can be simulated by Turing machine with two symbols. The idea is to consider groups of bits as representing one symbol, in the same way that files are stored in the computer byte by byte. In that sense, having more symbols gives you no more power than a single symbol. Moreover, the simulation has "constant throughput" — it only slows down the machine by some constant.

There is a fine point regarding input encodings. Usually inputs are blank-separated or blank-terminated. If you have only two symbols and are using this convention, then everything has to be encoded in unary — $1^n0$ for the number $n$. This has a strong effect on input *length* and so on running times (making them appear much *faster*), so either you use an unconventional encoding (say encode "characters" in groups of two symbols), or you need to have at least three symbols (including the blank symbol).
> 1 votes

---
Tags: computability, turing-machines
---


# Question
Title: Eliminating $\varepsilon$-productions during elimination of left recursion
I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any.

I have the grammar

$\qquad S \to Aa \mid b$
$\qquad A \to Ac \mid Sd \mid \varepsilon$

I can see after removing the epsilon productions the grammer becomes

$\qquad S \to Aa \mid a \mid b$
$\qquad A \to Ac \mid Sd \mid c \mid d$

I'm confused where the $a \mid b$ for $S$ and $c \mid d$ for $A$ come from. Can someone explain this?

# Answer
The idea of the algorithm is to first find out which non-terminals can produce $\epsilon$, and then eliminate them in all possible ways.

**Finding out which non-terminals produce $\epsilon$.** The idea here is to start with the set $X^{(0)}$ of non-terminals which have an $\epsilon$ production. We then construct the set $X^{(1)}$ which includes $X^{(0)}$ and all other non-terminals having productions in $X^{(0)\*}$ (that is, have productions in which the right-hand side consists of non-terminals in $X^{(0)}$ only). Continue this way until the process stops. The final set $X$ consists of all non-terminals which could produce $\epsilon$.

For example, in your case $X = X^{(0)} = \\{A\\}$. If there was a production $S \to A$, then you would have $X^{(0)} = \\{A\\}$ and $X = X^{(1)} = \\{A,S\\}$.

**Eliminating non-terminals which could produce $\epsilon$.** Now we simply take all productions containing non-terminals in $X$, and eliminate these non-terminals in all possible ways. That is, for each production containing terminals in $X$, you add additional productions resulting from deleting some of the non-terminals in $X$, in all possible ways. If you get $\epsilon$ productions this way, you just remove them (unless it's the possibly allowed $S\to\epsilon$).

For example, in your case the affected productions are $S \to Aa$ and $A \to Ac$. Handling the first, you add the production $S \to a$, and handling the second, you add the production $A \to c$.
> 1 votes

---
Tags: context-free, formal-grammars, compilers, left-recursion
---


# Question
Title: Fast ways to compute the smallest prime with a given substring?
So, I've got this problem:

> Given a string $\omega\in\\{0,\ldots,9\\}^\*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0.

What I'm asking is a fast algorithm for the problem?

# Answer
This answer only shows that every string actually appears in some prime. Without loss of generality, $\omega$ doesn't start with zero (otherwise, consider $1\omega$ instead). Consider all digits in the range $\omega \times 10^N$ to $\omega \times 10^N + 9 (10^{N-1} + \cdots + 10^0)$, an interval of length $10^N$. Let $M = \omega \times 10^N$. According to the prime number theorem, there are roughly $(M+10^N)/\log M - M/\log M \approx 10^N/\log M$ prime numbers in this interval. Since $10^N/\log M \to \infty$, for large enough $M$ there will be a prime number in the interval, and its most significant digits would be exactly $\omega$.

I don't expect there to be an algorithm much faster than going over all primes in sequence. If you *expect* the answer to be one of the first few primes (here *few* can be a rather large number, say $10^9$), then you can probably do some preprocessing to be able to handle such queries fast.
> 1 votes

---
Tags: algorithms, strings, primes
---


# Question
Title: Counting and finding all perfect/maximum matchings in general graphs
Recently i've been dealing with a problem that led me to the following questions:

* Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph?
* Is there a good algorithm for finding all maximum/perfect matchings in a general graph?
* Are these two problems equivalent in their complexity?

I've stumbled upon the following references:

Both algorithms' complexity depend on the number of perfect matchings in the graph (meaning exponential running time in the worst case).

Moreover, both articles deal with bipartite graphs, I couldn't find similar articles dealing with the same problem in general graphs.

I'd appreciate information and references about the above problems.

# Answer
Counting the number of perfect matchings in bipartite graphs amounts to computing the permanent of 0–1 matrices, which is $\\# P$-complete. It follows that there is a reduction from all the other counting problems you mention (which are all in $\\# P$) to this problem. You can compute the number of perfect matchings in *planar* bipartite graphs, and you can approximate the number of perfect matchings in general bipartite graphs. See for example this survey. Approximating the number of perfect matchings in general graphs is apparently more difficult, see for example this paper or that paper. Both papers mention that their algorithms seem to perform well on random graphs, but not necessarily that well in the worst case.

The problems of counting and of enumerating matchings in graphs are of different kinds, so it's hard to say whether they are "equivalent". Note, however, that if you could enumerate matchings then you could count them. This shows that, in some sense, enumerating is harder than counting. For the case of perfect matchings in bipartite graphs, there appears to be a difference, since you can approximate the number of perfect matchings, but computing them exactly is $\\# P$-hard.
> 8 votes

---
Tags: algorithms, complexity-theory, graphs, reference-request, matching
---


title: Big-O in computer Science

text:
# Question
Title: Big-O in computer Science
As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.

# Answer
> 1 votes
The most conspicuous use of big O notation is in the analysis of running times of algorithms. Since the exact running time depends on the cost of specific instructions, there is no point in saying that a certain algorithm takes time $14.3n$. Also, it is difficult, and pointless, to analyze everything exactly. Big O notation hides all these details while keeping the nucleus, which is the asymptotics of the running time. As an example, since quicksort is $O(n\log n)$ while insertion sort is $O(n^2)$, you should expect the former to outperform the latter for large values of $n$. (Of course, it all depends *in practice* on the so-called hidden constants.)

---
Tags: asymptotics
---


# Question
Title: The Absolute Minimum Every Software Developer Absolutely, Positively Must Know about Computer Science (No Excuses!)
Yes, I borrowed the title form a famous joelonsoftware post for my question because I didn't exactly know how to ask this.

I'm a professional programmer for a few years now and although I followed informatics courses in school there was a lot of stuff missing from the curriculum, as I now know but wasn't aware then. For example I didn't do any compiler theory, algorithm analysis (the Big-O), have no idea what P-NP meant etc.

So I want to catch up now!

But the field of computer science is big. Really big! So from here my question: What's the absolute minimum every software developer absolutely, positively must know about computer science (no excuses!)?

# Answer
\> What's the absolute minimum every software developer absolutely,
\> positively must know about computer science (no excuses!)?

IMO every software developer should **absolutely** know (no excuses!) the quote attributed to E. W. Dijkstra:

*"Computer science is no more about computers than astronomy is about telescopes"*

:-D :-D
> 4 votes

# Answer
Programmers need to know enough basic logic (at least some first-order logic) so that they find it natural to write assertions and specifications in a declarative way. Most programmers tend to only see the imperative aspects of programs. This does not help when you have to reason about your programs, or design good interfaces for modules and components.
> 2 votes

---
Tags: education, applied-theory
---


# Question
Title: Proof that {$a^m b^n$ | m!=n} is not regular
I know that the language $\\{a^m b^n | n\neq m\\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?

# Answer
Suppose $L = \\{ a^m b^n : m \neq n \\}$ were regular. Then $a^\*b^\* \setminus L = \\{ a^n b^n \\}$ would also be regular.

There is a variant of the pumping lemma in which you mark certain symbols of your choice (at least as many as the pumping constant $p$), and then the pumped part is certain to contain at least one of these symbols (and at most $p$). Now consider $a^p b^{p+p!}$ for large enough $p$, and mark the $a$ part. We arranged things so that whatever the length of the pumped part (which must consist solely of $a$s), you can pump it to exactly $a^{p+p!} b^{p+p!}$.

Another possibility is to use the Myhill--Nerode theorem. The words $a^n$ ($n \in \mathbb{N}$) are an infinite set of pairwise inequivalent words: if $n \neq m$ then $a^n b^n \notin L$ yet $a^m b^n \in L$.

Take your pick...
> 2 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Interpreting probabilistic time turning machines
I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better:

$$ Pr\_{r \in \\{0,1\\}^l}\[A(r) = \text{"yes"}\]$$

Where r is a truly random bit string and A is a polynomial time deterministic machine. I've been having some problems understanding what this expression means conceptually (or intuitively).

So far these are some of my thoughts and I will try to point out my doubts too.

A is just a standard TM so we can image that on l steps, it will yield $2^l$ branches. Each branch has a chance of occurring depending on which r occurs. Therefore, I was wondering if the above probability expression just mean "the fraction of branches that out yes"? Is that basically the same as the chance that A will output yes on the given random bit string? The thing that was confusing me and I was not sure how to deal with it was that, A(r) always outputs the same thing ("yes" or "no") on a given r (say it always accepts or rejects if r = 1010100 or something), it didn't seem to me that it a probabilistic sense, unless we randomly choose r. So I was wondering how the community interpreted this equation and what it mean.

Also, since this is a probability, it seems to me that A(r) is just r.v. that only takes two values (yes or no), right? So this distribution only has two probability values, the one that A outputs yes or no, right? I was wondering how that related to the string r and I was not sure how to resolve this.

# Answer
As the notation implies, the probability is taken over the choice of $r$. So it's the fraction of $r$s which the machine $A$ "accepts" (answer *Yes*). You're right that the random variable $A(r)$ has two possible values, *Yes* and *No*, and so for example the probability to get *Yes* and the probability to get *No* add up to $1$.

We usually think of $A$ as a statistical test. For example, $A$ might test the the number of $1$s in $r$ is roughly $\ell/2$, say between $\ell/2-\sqrt{\ell\log \ell}$ and $\ell/2+\sqrt{\ell\log \ell}$, and then it accepts with probability $1-2/\ell^2$ or higher (using Chernoff's inequality).

Something you are confused about is the *branching*. The machine $A$ can read its input bits many times. There is always one computation branch. After $\ell$ steps, there is still only one computation branch. On the other hand, *at the outset* there are $2^\ell$ different computations to consider.
> 2 votes

---
Tags: terminology, probability-theory, randomized-algorithms, randomness
---


title: How to get 2-state PDA for CFG?

text:
# Question
Title: How to get 2-state PDA for CFG?
I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown Automaton (PDA). I am however a little bit confused that why this is possible.

# Answer
Depending on your acceptance definition, you might be able to get away with only a single state. The basic idea is to keep the state information on the stack. The first thing you'd try is for each symbol on the stack to contain the "current state", i.e. each symbol is a tuple $(s,X)$, where $s$ is a state of the original PDA and $X$ is a stack symbol in the original stack alphabet. That way, the state information is stored on the stack. There is a problem here, however: if we pop $(s,X)$, we don't know what state the PDA should be in. For the solution, see these lecture notes. The construction heavily relies on non-determinism.
> 4 votes

# Answer
Transforming a PDA into a CFG is hard, as we need to get rid of the states.

The converse, transforming CFG into single state PDA is straightforward, using an expand-match technique, see wikipedia. Single state when using empty stack acceptance. Two sates are necessary when transforming into final state acceptance (you need two to distinguish yes/no accepting, of course).
> 4 votes

---
Tags: formal-languages, context-free, formal-grammars, pushdown-automata
---


# Question
Title: $L \in RE/R$ such that $L^R \cup L \in R$
> Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$

Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but couldn't. What I know for sure is that I need a language in $RE/R$ such that $L \cup L^R = \Sigma^\*$, or am I also wrong?

# Answer
> 6 votes
Since this sounds like a homework question to me, I will give the answer as a series of hints. (You should make a serious effort to solve the question after each hint, instead of just reading them all in short succession.)

First: Such an $L$ exists and $L \cup L^R$ is not necessarily $\Sigma^\*$.

> Try $L \cup L^R = \\{a^nb^n\\} \cup \\{b^na^n\\}$.

---

> For each $n$, $L$ should contain exactly one of the words $a^nb^n$, $b^na^n$. How can you do this so that $L$ is in $RE/R$?

And finally the solution:

> Let $K$ be any set in $RE/R$ and let $L = \\{a^nb^n \mid n \in K\\} \cup \\{b^na^n \mid n \notin K\\}$.

---
Tags: formal-languages, computability
---


# Question
Title: Kleene star closure of a context free grammar
I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful.

> Give an counter-example to show that the following contruction fails in to proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -\> SS e call the resulting grammar G'. That grammar is expected to generate a\*"

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'-\>SgSg'|e} or in another words Rg': Rg U {Sg'-\>SgSg'|e}. Even if that it is correct I don't understand why {Sg'-\>SgSg'|e} is necessary

# Answer
There is a silly problem that you might need to add a production of the form $S\to\epsilon$, since otherwise you don't necessarily generate $\epsilon$. But the real problem is that $S$ can be used in the right-hand side of productions, and when you add the rule $S\to SS$, things could break. The "correct" way to turn a grammar of $A$ into a grammar of $A^\*$ is to add a *new* start symbol $S'$ and the productions $S' \to S'S|\epsilon$.

In order to find a counterexample, think of the problems mentioned in the previous paragraphs, and try to find an example which manifests them. All it requires is some experimentation.
> 2 votes

---
Tags: formal-languages, context-free, closure-properties
---


title: Decidability of an regular expression

text:
# Question
Title: Decidability of an regular expression
I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing.

> Be A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

Answer: Create a turing machine P, this machine receives a pair where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to loop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?

# Answer
> 2 votes
When showing that something is decidable, we don't usually invoke the concept of Turing machines. Rather, we use the Church–Turing thesis that states that informally described algorithms are realizable by Turing machines. Even when describing Turing machines, there is no need to describe subroutines—that's a programming concept that you are misusing here. Finally, there is absolutely no need to add consistency checks to your code! This code isn't going to be compiled. You can assume that it is bug-free. That's why we only give an informal description, in which these messy details are missing.

Another mistake you make in describing your program is the input $W$. This input is constant, and so there is no need to include it. Also, you haven't explained how you represent $W$: the set of all strings containing $111$ is infinite.

Let me rephrase your algorithm informally. The algorithm gets as input a regular expression $r$, which it then converts to an equivalent DFA (there is no need to explicitly go through the intermediary NFA; we already know that regular expressions can be converted to equivalent DFAs). Then it goes over all strings containing $111$ in lexicographic order, and if the DFA accepts any of them, it outputs **Yes**.

Do you see the problem with your algorithm? It never outputs **No**. When the answer is **No**, it never halts. So you haven't shown that the problem is decidable, only that it is semidecidable (i.e. recursively enumerable).

Let me offer a different direction. Suppose I gave you a regular expression, and asked you whether the language it describes has a word containing $111$. How would you answer that? Can your answer be implemented mechanically? If so, you've found an algorithm and shown that the problem is decidable.

---
Tags: computability, regular-languages, undecidability
---


title: Tips for teaching using Live Coding

text:
# Question
Title: Tips for teaching using Live Coding
I am involved in a first year programming and algorithms course. In a recent lecture, I decided to present the material using *live coding*, which essentially meant that I sit behind the keyboard and write code and evaluate it, using *emacs* to facilitate the process.

This was quite successful and students commented on how much they appreciated the more (inter)active format. As this was my first attempt using this teaching format, I know that it did not run perfectly. Some of the problems were related to being not as savvy with *emacs* as I should be, and others were to do with allowing student questions to take me too far from my script. I know I can do better.

> What are some guidelines for giving lectures (and other demonstrations) using live coding lectures?
> What are the pitfalls to avoid?

# Answer
> 8 votes
Here are some tips and pitfalls I've collected after using live coding for a week, and from talking to a colleague.

DOs

* Prepare a script to follow and try to stick to it.
* Clear the buffers frequently to focus on relevant part.
* Start afresh for each new topic.
* Use a bigger font.
* Master the tool you are using, to avoid wasting too much time on trivialities.
* Have background functions precoded. If not particularly relevant, ensure they can be imported, rather than appearing in the working file.
* Ideally work in a language that give you immediate feedback. Languages with an interactive shell are best in this regard.
* When using a typed, give the expected type of the function you are writing. This provides a guiding light for the students.
* Freely make mistakes (though not too many). Step through how these should be fixed.
* Don't forget – a picture paints a thousand words: interleave slides and black/whiteboard work with your coding session.
* Have summary slides for the points you've covered
* Sometimes, when modifying code, maybe make a copy and modify the copy. This provides a point of comparison.
* Clean up code periodically.
* Accept that you will make mistakes and openly allow students to correct you --- this makes your job easier and empowers them.
* Write code in your own style. For example, you may have copied the code from elsewhere. But this will be hard to reproduce. Better to write it in your own style. For instance, I always write curried functions, because I program mostly Haskell. But Standard ML uses the idiom less frequently. Expecting curried functions is the most common error I make in class.
* Physically, make sure you have your space set up well. Good keyboard, at the right height, cables all in the right places, physical obstacles out of the way, etc. Take a minute before you start to get your space working for you, not against you.
* One approach is to write whatever students say, even if it is wrong. This get students to do the coding, and the fixing. It is a good idea to clean the code up at the end. This approach can create a classroom model of attention and interaction, because students need to pay attention to follow what is going on.

DON'Ts

* Don't optimise your code on the fly and break it in such a way that you cannot fix it.
* Avoid talking to the computer. Talk to the students!
* Avoid too much typing, especially of boilerplate code. Utilise your environment to help you spit out the templates for you.
* If you use a text editor, avoid constantly scrolling around. It will cause motion sickness it those trying to follow.
* If you use a text editor, before making radical changes to your code, warn students that you are going to do so, so that they can track what is going on.

---
Tags: education, didactics
---


# Question
Title: Is it possible to encode an arbitrary computation as a series of NP complete problem instances?
For example, can I make a compiler that transforms a C program (Turing complete language) into a bunch of SAT instances.

This encoding would be motivated as a way for specifying a problem piecemeal, where work on each piece could be verified in polynomial time.

# Answer
> 0 votes
Each program instance can be encoded as a (possibly very long; even infinite, if the program doesn't halt) series of NP complete problem instances, e.g. as follows:

For each "wire" inside a computer, we can derive a SAT formula that describes how the value (on or off) on this wire after the following clock signal depends on the currrent values of several other wires. Using such SAT instances along with a set of variables that describe the current state of the computer, we are able to simulate any computation through a series of SAT instances.

Of course it is possible to combine multiple of these instances (or use a different approach), in order to simulate larger chunks of the computation at once. But there are limits:

If your original problem is in NP, then of course you can encode it as a single NP complete problem instance. But you probably will not gain much from doing this.

If your original problem is not in NP then you will need a superpolynomial number of NP complete problem instances in order to solve it, since a polynomial number of NP complete problem instances can be solved in polynomial time by an NDTM, implying that the problem is in NP.

So the short answer to your question is: "Yes, but usually not in a way that is helpful in the sense of your motivation."

---
Tags: complexity-theory, computability, np-complete
---


title: NFA to DFA final states proof

text:
# Question
Title: NFA to DFA final states proof
> When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA.

What should my arguments be in order to prove this?

# Answer
> 2 votes
Your statement is incorrect for two reasons.

First, there are in general **several** final states in the DFA corresponding to an NFA and not a single one. Next a set in the DFA is final if and only if it contains **at least one** final state of the DNA (and not all of them as you wrote). Furthermore, the initial state of the DFA is the set of **all** initial states of the DFA.

You can find the formal proof in any textbook on automata, but here is the intuition.

Let $\mathcal{A} = (Q, A, E, I, F)$ be a NFA. Let us call *successful* a path in $\mathcal{A}$ starting in $I$ and ending in $F$. By definition, a word $u$ is accepted by $\mathcal{A}$ if and only if there exists a successful path with label $u$.

Now, what happens when you use the subset construction to compute a DFA $\mathcal{B}$ equivalent to $\mathcal{A}$? You know that the states of $\mathcal{B}$ are subsets of $Q$. Furthermore, there is a path from $P$ to $R$ with label $u$ (where $P$ and $R$ are subsets of $Q$) if and only if $$ \text{for each $r \in R$, there is a state $p \in P$ and a path in $\mathcal{A}$ from $p$ to $r$ with label $u$.} $$ Thus intuitively, this path $P \xrightarrow{u}\_{\*} R$ in the DFA encodes all the possible paths in the DNA from a state of $P$ to a state of $R$.

Suppose now that $P = I$ and that $R$ contains a final state of $\mathcal{A}$, say $f$. Then there is a state $p \in I$ and a path in $\mathcal{A}$ from $p$ to $f$ with label $u$. Thus this path is successful and $u$ is accepted by $\mathcal{A}$.

In the opposite direction, suppose that $u$ is accepted by $\mathcal{A}$. Then $u$ is the label of a successful path in $\mathcal{A}$, say from $p \in I$ to $f \in F$. Let $R = I \cdot u$ (in the DFA $\mathcal{B}$). Then $f \in R$ by construction and thus $R$ contains a final state.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Why is ww a linear indexed language while www is not?
I am a little bit confused on one idea regarding indexed languages.

> $\\{ww \mid w \in \\{a,b,c\\}^\* \\}$ is a linear indexed language, but
>
> $\\{www \mid w \in \\{a,b,c\\}^\* \\}$ is not a linear indexed language.

What is the difference? As far as I know, indexed languages can be recognized by stack automatons, but I am a little confused on this.

# Answer
In linear indexed languages, the intuition is that you cannot copy a big information in one step, you have to do it in aletter-by-letter way. This causes things like $ww^R$ much easier to do than $ww$. We can still do $ww$ because you can first "create" the word $w$ by pushing its letter onto the stack and writing them at the same time on the output. Then you can pop the letters to the right or to the left as you prefer, so you can always produce $ww$. For $www$ it's not possible anymore, because after producing $w$ on the stack and writing in on the output, you need to duplicate the stack, which is not allowed. However you could produce $www^R$, by writing the letters on both sides when popping the stack.
> 1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Pick parameter function that minimises whole function
I have a recursive algorithm defined by the following recursion.

$$T(n) = T(n/f(n)) + O(\log f(n)).$$

I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = \Theta(\log n)$. If $f = O(n)$ then $T(n) = \Theta(\log n)$. Is this true for all functions $f$ that $T(n) = \Omega(\log n)$ or can I get asymptotically better behaviour for some $f$? The reason I think there might be is that you can look at an extended binary search where you split your domain into $f(n)$ sections and then examine each section to see if your value is in that section. This recursion can be presented as follows:

$$T(n) = T(n/f(n)) + O(f(n)).$$

Binary search clearly runs in logarithmic time or worse for all values of $f$. This is the same as my recursion except that it is linear in $f$ instead of logarithmic. So you might expect better behaviour.

# Answer
> 2 votes
This is probably not possible. Let $n\_1,\ldots,n\_k$ be the sequence of $n$s encountered in the recurrence, starting with $n\_1 = n$. Using the concavity of $\log$ (and eliminating the big $O$), we get that $$ T(n) \geq k \log \frac{f(n\_1) + \cdots + f(n\_k)}{k}. $$ Assuming $f$ is monotone, we have $k \geq \log n\_1/\log (n\_1/n\_2) = \log n/\log f(n)$. This monotonicity also shows that $n\_{(k+1)/2} \geq \sqrt{n}$. Therefore $$ T(n) \geq \log n \frac{\log f(\sqrt{n}) - 1}{\log f(n)}. $$ For all $f(n)$ I can think of, $\log f(\sqrt{n})/\log f(n) = \Theta(1)$, so they can't give you anything better than $\log n$. This also says that if you're looking for a monotone $f$ which beats $\log n$, then it must satisfy $\log f(\sqrt{n}) = o(\log f(n))$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Is this the correct way to use the pumping lemma?
I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not regular. I don't know quite how to apply the lemma and want to understand if I'm doing it right. If I had something like:

**w** = {anbk, n =/= k}

am I correct in that I can say that:

**h** = {anbn + r, r \> 0} is a subset of **w**, and thus if I show by the lemma that **h** is not regular, that **w** must not be regular since **h** is a subset of **w**.

The way I would show this is as follows:

1. h = xyz
2. |xy| \<= n
3. x = an-r
4. y = ar
5. z = bn + r
6. xyz = an-rarbn + r
7. xy2z = an-ra2rbn + r = an + rbn + r

Thus **h** cannot be regular since an + rbn + r is not of the form {anbn + r, r \> 0}, and since **h** is not regular **w** must not be regular, since **h** is an element of **w**.

Have I applied it correctly? I understand how to apply it for an easy language like {anbn}, because I can apply the lemma directly to this language, but the only way I could think of for my language was to create a subset that belongs to my language, and apply the lemma to that.

If I haven't applied it correctly, is there a way to show that my language is not regular (or regular), using another lemma, or perhaps with closure properties?

This is a really awesome topic, even if I don't understand the pumping lemma fully, I'm excited to explore it further!

# Answer
> 2 votes
A subset of a regular language could be non-regular, so the entire line of reasoning is flawed. As an example, every non-regular language over $\\{0,1\\}$ is a subset of the regular language $(0+1)^\*$.

Regarding the language $H$, you'd do better writing your proof in paragraph-style rather than as a cryptic list. In addition, you made the following mistakes:

1. You never mention which $h$ you take.
2. You don't get to choose the decomposition $h = xyz$. The proof has to work for *every* such decomposition satisfying the properties given in the lemma ($|xy| \leq n$, where $n$ is the "pumping constant").

Several ways of showing that your original language is not regular are given in this answer.

---
Tags: formal-languages, regular-languages, pumping-lemma
---