# Question
Title: Applying Brewer's theorem (CAP) to a single node
I'm going through Brewer's theorem and its proof by Nancy Lynch and Seth Gilbert. But the paper left me with one question. What prevents the theorem from being applicable to a single node?

I haven’t encountered any explicit definition of network partition that restricts its applicability to a network. There are some hints in \[1\] that suggest that a network partition with a single node would mean cutting off all communication to that node itself. This doesn’t make a whole lot of sense to me because you could always have a partition with all the service nodes on one side and the client node on the other. No service could possibly tolerate that.

A single node data object can be consistent and available if requests sent to it get through. To me, the definition of a network partition and where it applies leaves something to be desired. What am I missing here?

\[1\] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Seth Gilbert and Nancy Lynch

# Answer
> 2 votes
In my opinion, the CAP theorem is applicable intentionally to distributed systems. To quote the article "Perspectives on the CAP Theorem @ IEEE Computer'2012 by Gilbert and Lynch":

> Brewer first presented CAP in the context of a Web service implemented by a set of servers distributed over a set of geographically diverse datacenters. Clients issue requests to the service, which sends back responses.

In this context, the "network" in CAP theorem refers to *communications among servers* (instead of communications among clients or between clients and servers). This can be justified by the following two arguments.

1. To quote the above article again (with *emphasis* added):

> Unlike the other two requirements, partition tolerance is really a statement about the underlying system rather than the service itself: communication *among the servers* is unreliable, and the *servers* can be partitioned into multiple groups that cannot communicate with one another.

2. In the *proof* of the CAP theorem in the above article, it says,

> Consider an execution in which the servers are partitioned into two disjoint sets: $\\{p\_1\\}$ and $\\{ p\_2, \ldots, p\_n\\}$. Some client send a read request to server $p\_2$.

The proof followed is based on the communication among the two disjoint sets of *servers*.

*To summarize*, CAP theorem (*again, it is my own opinion*) does not consider the situation in which client nodes and server nodes are partitioned. After all, we can do almost nothing in this bad situation. In other words, CAP theorem *assumes* that the communications between clients and servers behave well and focuses on the theory and implementation of the distributed service itself.

---
Tags: computer-networks, database-theory
---


# Question
Title: Disconnecting a complete graph by removing edges randomly
Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph.

I want to find out the minimum number of edges that I must remove randomly to disconnect the graph. Also the value of $p$ where I can disconnect the graph by removing the least number of edges.

# Answer
> 3 votes
For your first question, an empty graph becomes connected roughly when $n\log n$ random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper *On the evolution of random graphs*, and recounted in textbooks on random graphs.

Your second question is not stated precisely and so is difficult to answer.

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


# Question
Title: Is the infinite union of computable sets computable?
My intuition is telling me that this is untrue. But I am having trouble formulating a proof for this. Can anyone point me in the right direction? I've seen a proof by contradiction involving the union of all singletons in an infinite language but I am needing a to look at this from a different angle.

Related question: Is the infinite union of computably enumerable sets also computably enumerable? I also believe this to be untrue.

# Answer
The claim as stated is easy to refute, so let's ask a (slightly) more difficult question: is the *countable* union of computable languages computable? The answer is again negative: the language $L = \\{ 1^e : \text{ program $e$ halts on the empty input}\\}$ is not computable, but is the union of countably many singletons.

What if we require the countably many languages to be uniformly computable? This means that not only is there a one-parameter program $P\_i$ for the $i$th language $L\_i$ such that $P\_i(x) = T$ iff $x \in L\_i$, but also there is a two-parameter program $P$ such that $P(i,x) = T$ iff $x \in L\_i$ (both $P\_i$ and $P$ are required to always halt). In this case, the union still need not be computable. For example, let $L\_n = \\{ e : \text{ program $e$ halts on the empty input within $n$ steps}\\}$. These programs are uniformly computable, but their union $L$ is not computable.

A union of a sequence of uniformly computable languages is known as *recursively enumerable* (r.e.) or *computationally enumerable* (c.e.), and is a fundamental concept in computability theory. The relation between computable languages and c.e. ones is the same as that between P and NP.
> 2 votes

# Answer
(Following Shaull's comment)

## No.

For any $w\in \Sigma^\*$, the singleton $L\_w=\\{ w \\}$ is a computable set.

Yet, every set $L$ (finite or infinite, computable or not) can be written as an (in/)finite union of singletons $$ L = \bigcup\_{w\in L} L\_w$$

Therefore, some infinite unions of computable sets *do* give a computable set (e.g., union over all the possible singletons), and some infinite unions *don't* give a computable set.
> 3 votes

---
Tags: computability
---


title: How to XOR automata?

text:
# Question
Title: How to XOR automata?
Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.

$x\\; \mathrm{XOR} \\;y\\; \mathrm{XOR} \\;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$. This is way too complicated and time consuming to draw. Isn't there another way?

Thank you for taking the time!

# Answer
> 10 votes
Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.

# Answer
> 6 votes
Since the three machines are all deterministic the combined operation is not complicated at all. Run the machines in parallel, using a direct product construction like the one that is also used for intersection, and at each triple state XOR the presence of final states to verify whether the new state for the XOR product should be accepting.

# Answer
> 2 votes
Since you are only working with DFAs, you can XOR two automata by building the cross product of the two automata and then taking as accepting states those pairs of states of which one state is an accepting state, but not both.

Note that this construction only works for DFAs in which each state has *exactly one* successor state for each alphabet symbol. This ensures that you always reach a state when simulating the automaton and the acceptance of a word only depends on whether this state is an end state or not. Sometimes, DFAs are defined so that each state has *at most one* successor state for each alphabet symbol. In this case, the construction above doesn't work anymore, because there is now a second reason why a word is not accepted: with some words no state is reached at all.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Can all languages have semantic and logical errors?
I have been reading about PHP and many authors mention semantic and logical errors separately. As an example of a semantic error, they give a function called with incorrect number of parameters: this will not be caught by the parser, but will throw an error when run.

Yet in languages such as C++, this will be caught by the compiler. I would say that it's a syntax error then. What is the difference then between a semantic and a logical error?

For example, in How to think like a computer scientist, the author uses "logic error" and "semantic error" interchangeably. On the other hand, in the Visual Basic .NET. Primer Plus, "logic error" is separated from "semantic error".

# Answer
> 8 votes
I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't *have* a precise universally accepted definition, and so people are using the terminology slightly differently. I wouldn't get hung up on it.

Both "logic" and "semantic" imply something to do with the meaning of the programming, so it would be easy to regard them as the same.

If I were to draw a distinction, a useful one I can see is that a logic error is when the program ends up meaning something other than what the programmer intended, and a semantic error is when the program ends up not meaning anything (consistent) at all. With those definitions, you could either regard logic errors as a superset of semantic errors, or that logic errors exclude errors that result in the program being inconsistent.

For example, the following pseudo code contains only a logic error:

```
x = read_number_from_user("x: ")
y = read_number_from_user("x: ")
print("The product of x and y is: ")
print(stringify(x + y))

```

The meaning of this program (taken solely as-is and without considering the programmer's intent) is perfectly straightforward and consistent. But it doesn't mean what the programmer intended it to mean.

OTOH, the following pseudo code contains a semantic error:

```
name = read_string_from_user("What is your name?")
print(name + 1)

```

At least, it does if we assume that adding a string and a number doesn't mean anything. In languages like PHP it *does* mean something, and this wouldn't be a semantic error.

Your example of a semantic error in PHP as calling a function with an incorrect number of parameters is actually interesting, because it's debatable whether you should call that a semantic error (with the definition I'm using).

Functions are defined dynamically at runtime in PHP. So calling a function with an incorrect number of parameters *could* be regarded as a logic error; perhaps the wrong include statement was executed, causing a different function with the same name to be included than the one the call was supposed to go to. Even if not, calling a function with the wrong number of arguments does mean *something*; it means lookup the function with this name and pass it these arguments. It's only operationally at runtime that it turns out the interpreter is unable to carry out those requests; just as `x / y` means something, but may be impossible to carry out if `y` happens to be 0 at runtime.

Ultimately, how you classify errors using a distinction *like* the one I'm making here between logic and semantic errors (even if it's not exactly the one I'm making) depends very much on the particular language you're talking about and **how you assign meaning to programs in the language**. Most commonly used languages *do not have* a standard way of assigning meaning to their programs, which means that everyone uses a slightly different way of doing so (though everyone's interpretation would agree very closely on almost all *operational* effects), and would analyse the "logical" vs "semantic" distinction differently.

Another similar way of looking at it would be to say that semantic errors are whatever causes the programming language to reject the program as invalid (apart from syntactic errors, though again you could call those a subset of semantic errors if you want). If the programming language accepts the program then it means *something*, and if it fails at runtime then that is the result of a logic error. This is pretty much assigning the programming language implementation (interpreter, compiler + runtime system, whatever) as the definition of what programs mean.

# Answer
> 3 votes
It's possible to distinguish many categories of errors in programs based on the point at which they manifest. Some categories don't arise in certain contexts (depending on the programming language, on how the program is designed, on how the program is used…). The terminology varies a lot between communities. I'll show a typology of the main categories; keep in mind that

* there are workflows where some of these categories won't apply;
* there are workflows where it's convenient to make other distinctions;
* similar errors may end up in different categories depending on the programming language and tools that are used;
* different people have different terminologies, the names I give are plausible but by no means consensual.

You can distinguish different categories of errors based on the point at which they are noticed.

1. Syntax errors
The compiler or interpreter tells you that what you wrote doesn't even make sense. In most languages, this is a fatal error, which won't let the program even begin to be executed.
Example: a missing close parenthesis.
2. Static type errors and other compiler errors
The compiler or interpreter tells you that while it understood what you requested, that doesn't make sense. The distinction between syntax errors and other kinds of compiler errors is a matter of internal compiler design, or sometimes of the design of the programming language.
Example: using a variable that has not been defined (this is often considered a syntax error but not always)

In statically typed languages, the compiler rejects programs that attempt some kinds of invalid operations. In dynamically typed languages, such errors are runtime errors, either fatal or not. Example: trying to divide an integer by a string.
3. Startup errors
This is the first category of errors that is revealed to the person who runs the program rather than the person who makes the program.
The program won't start, or won't reach a state where it actually does something.
Example: trying to use an external library that is not present on the system.
Example: any syntax or compilation error in an interpreted language (where the programmer distributes the source code).
4. Fatal runtime errors
At some point, the program stops working.
Example: memory access violation (attempting to access memory that isn't allocated to the program)
Note that sufficiently complex programs may attempt to catch just about any error, turning them into recoverable errors.
5. Unexpected, but recoverable runtime errors
Some component of the program stops working, but the program keeps going. Example: running out of memory (if the program is designed to handle this gracefully)
Example: one process in a multiprocess application crashes, but the other processes keep running
6. Expected runtime errors
Some error condition is expected, but it has been programmed for. This is just normal behavior, reacting to an external event which is somehow “bad” but which can happen. When you consider the program as a whole, these are not really errors.
Example: file not found
Example: network disconnection
Example: invalid user input
7. Programming errors
The program is doing something, but that's not what it's supposed to be doing according to its specification. There's a difference between what the programmer intended to do and what the source code actually means.
Example: a web application is supposed to let you upload a file, but it doesn't work on file names containg spaces; the application rejects the file and goes on working.
Example: a program designed to multiply some number returns a result, but the mathematical operation is not performed correctly.
8. Specification errors
The program is doing something, and conforms to its specification or documentation. However, upon reflection, the program's behavior in this situation is not good. (“Not good” is of course a subjective judgement.)
Example: component 1 expects a space-delimited list of file names. Component 2 sends it a single file name that contains spaces. The two components weren't carefully designed to work together.
Example: a program to predict the weather announces rain which doesn't come, because its modeling of the physical world wasn't good enough.

It is fairly typical to consider 2–4 to be semantic errors and 7–8 to be logic errors. (However, note again that the terminology can vary.) Recoverable runtime errors are not errors of the program as a whole, but may be seen as runtime errors of some part of it.

There is a different terminology that considers that

* semantic errors are what a compiler with a static type system would typically catch, or what would cause a “protective” runtime system to abort a program with an exception that is not due to an external event (e.g. method not found as opposed to file not found);
* logic errors are what would not be caught.

This can be a fairly precise distinction when you consider a specific language and a specific type checker. However, when people use these terms, they often have a very imprecise idea of what that hypothetical compiler would be. For example, if you're programming in Java, passing the wrong number of arguments is caught by the compiler. If you're programming in PHP, it's caught by the runtime system. If you're programming in Perl, it's likely to not be caught (in the absence of any argument declaration, extra arguments are ignored and missing arguments produce a default value).

Or, to give another example: suppose you have a 10-element array and you try to access the 11th. In some languages such as C, this causes your program to access some unrelated zone of memory, leading to unpredictable behavior. In other languages, this causes an exception to be thrown; depending on whether the programmer expected this, this may be a semantic error (the programmer expected that the index might be out of bounds but did not check for that situation), a logic error (the programmer mistakenly thought that the index would always be valid), or not an error at all (the programmer relied on the exception to test whether the array index was within the bounds of the array).

The moral of the story is that these classifications are highly variable. Don't attach much importance as to which errors are put into which categories by which authors. The important thing is to understand the relationship between what you write and what the program should do. As a programmer, your job is to bring the huge gap between *what I write* and *what I mean*. If something falls in the gap, don't get hung up on fitting it with a label; concentrate on understanding what is going wrong and how to fix it.

# Answer
> 1 votes
Basically you have to look at the languages itself first.

PHP is an interpreter language, that means the scripts are compiled and executed every time at runtime C++ is a compiler language, that means the scripts are compiled with a compiler once at build time and can be executed then.

so both compilers recognise the semantic error from your example, but the php compiler does this at runtime, and the c++ compiler at compile time.

A good explanation for your question can be found at Wikipedia and here (difference between semantic and syntax)

# Answer
> 0 votes
My guess:

* A *semantic(al) error* is a programming mistake which produces code that is syntactically valid, but cannot possibly do what its programmer intended, no matter what that intention was. The code is definitely wrong and might be flagged as such by software tools - although software tools cannot possibly flag *all* such errors (by Rice's Theorem).
* A *logic(al) error* is a programming mistake which produces code that is syntactically valid, but doesn't do what its programmer intended, although it might have been correct if the programmer had had a different intention. The code is only wrong given the programmer's intentions; software tools cannot flag the code as wrong, the best they can do is hint at the possibility of this mistake.

# Answer
> 0 votes
A program is a text intended to express the computation of a result that answers a question about the data. For example, a sorting program will take a list of values (the data) and should compute a result which is another list of the same values, but sorted according to some comparison function.

This text is to be expressed formally in some kind of language that is (or should be) precisely defined, both regarding what constitute a legitimate program text, and how some computational meaning can be associated to this text. Such a precise definition is often abstract (possibly mathematical), and may ignore some concrete problems such as computer limitations.

But then, the language is implemented so that programs can be executed. There are again many ways of doing such an implementation, using a intepreter of the original program text, or compiling to some intermediate code (byte-code for example), then possibly interpreting this intemediate code, or compiling it further into machine code. And there could be other variations. And of course, there are many ways of writing a compiler or an interpreter, and many machines to run them on.

Furthermore there may be several formal definitions, and several implementations, hopefully consistent.

**Errors can be classified in relation the structure of either or both a formal definition or/and an implementation.** However you could have strange situations where errors are classified according to an old reference implementation which is no longer the one being used.

This essentially means that **classification of errors is a not really a very stable topic**. Furthermore, some languages may distinguish several levels of errors depending on whether something is definitely wrong (the program will not even run) or on whether you are doing something not recommended, but that will still produce some computation, that might make sense. This is even reflected in features of programming languages such as exceptions, that may or may not be recovered from.

Standard distinctions are:

**Syntax errors**: the text given does not conform the structure of a program text, independently of what it should mean. This may refer only to a formal language syntax, usually context-free. It may sometimes go further and include the checking some basic features such as variable declarations (if any) or type consistency, though these may also be considered as semantic errors.

**Semantic or logical errors**: these are errors that can be detected when actually running the program which are due to the fact that the program runs into a calculation that does not make semantic sense, such as dividing by zero, or indexing an array out-of bounds. Calling a function with the wrong number of arguments, or with arguments of the wrong type may also be considered a semantic error. In some languages, errors may actually be user-defined by means of exceptions, when they correspond to some user defined higher-level semantics for part of his program (though there are other uses of exceptions). Some of these errors are sometimes also called run-time errors as they are detected at runtime, but they should not be confused with hardware limitation errors.

**Hardware limitation errors**: these are errors due to the fact that the implementation is on a real machine that has limitations. For example this may be an integer too large to fit in a memory word, or lack of sufficient memory to create a data structure. These also usually detected at run-time.

Regarding semantic errors, and hardware limitation errors, it is sometimes possible to detect them before executing the program, with what is called **static semantic analysis**. This is often the case for declarations or uninitialized variables, or for type errors, or for division by zero and some array bound checking, but it may go much further. Static semantic analysis is also important in compilers for many optimisation techniques. There is often a separation between static and dynamic semantics. The best definition I can imagine is that static semantics concerns properties that are decidable at compile time, without the actual data. So division by zero would not be part of static semantics in general. This goes to say that some dynamic semantic errors may still be sometimes detected at compile time. The same goes for hardware limitation errors.

But **every language designer or implementor has a right to classify errors as he will**, unless bound by a contract or license. That may well be the case for your PHP example. And anyone may as well make a distinction between semantic and logical errors, though I would not know how to define a difference, unless possibly being told in detail about these errors. One could be used to denote error in intent (logical error) , and would not be detectable by the system.

Note that **there may be other kinds of error in a program**, that will not usually be detected by the system. That includes in particular inconsistencies of the program with its specification (or what I called error in intent: the user is not doing what he meant do do), or possibly errors in the specification itself. There may also be errors due to hardware limitations such as rounding errors when working with real numbers.

# Answer
> -2 votes
According to my higher computing course notes, semantic errors and logical errors are just different names for the same thing.

---
Tags: terminology, programming-languages, compilers, program-correctness
---


# Question
Title: Creating a CFG that connects lengths of three blocks
I have to create a CFG which generates

$$\\{a^n (ab)^n c^m d^\ell e^k \mid n\>0, k, \ell, m\ge0, k\<m, m=\ell+k\\}$$

The first part is easy enough, I came up with

$$\begin{align\*} S &\to aS\_2abS\_3 \\ S\_2 &\to aS\_2ab \mid \epsilon \end{align\*}$$

However, the second part is very confusing. So far I have

$$S\_3 \to S\_4 \mid \epsilon$$

The problem I have is how do I possibly keep track of all of these variables? $k$ has to be less than $m$, $m$ has to be equal to $\ell + k$, and $\ell$ must be at least $1$ by extension. Can someone give me some general tips for approaching these CFG's?

# Answer
Here comes the grammar based on your part of the answer and the comments of Raphael and Rick Decker (including $l\ge 1$). At first, your part:

$S\to aA\_1abA\_2$
$A\_1\to aA\_1ab\mid\varepsilon$

Secondly, we create rules for $A\_2$ such that we get words of the form $c^kA\_3e^k$

$A\_2\to cA\_2e\mid A\_3$

Finally, we create rules for $A\_3$ such that we get words $c^ld^l$ with $l\ge1$:

$A\_3\to cA\_3d\mid cd$
> 1 votes

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


# Question
Title: Who (and when) first defined interval graphs?
I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949.

So, I'm trying to track down the original paper introducing interval graphs for citation, but it's been rather elusive so far.

# Answer
I was able to track the first occurences of interval graphs down to

**G. Hajos, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957) page 65**

This reference refers to a book of (talk) abstracts. In the abstract of Hajos interval graphs are defined, without actually calling them *interval graphs*. Moreover it says, that he gives conditions whether a graph is a interval graph and he discusses how to reconstruct the intervals defining the graph, when the graph fulfills these conditions.
> 5 votes

# Answer
According to Golumbic \[1\], Hajös proposed the following problem in 1957 (translation by Golumbic):

> Given a finite number of intervals on a straight line, a graph associated with this set of intervals can be constructed in the following manner: each interval corresponds to a vertex of the graph, and two vertices are connected by an edge if and only if the corresponding intervals overlap at least partially. The question is whether a given graph is isomorphic to one of the graphs just characterized (Hajös \[1957, p. 65, translated by M.C.G.\]).

Golumbic also discusses how interval graphs were related to a question in biology made by Benzer \[2\] in 1959.

---

\[1\] Golumbic, Martin Charles. Algorithmic graph theory and perfect graphs. Vol. 57. Elsevier, 2004.

\[2\] Benzer, Seymour. "On the topology of the genetic fine structure." Proceedings of the National Academy of Sciences of the United States of America 45.11 (1959): 1607.
> 2 votes

---
Tags: graphs, reference-request, history
---


title: Decide whether DFA have useless states

text:
# Question
Title: Decide whether DFA have useless states
A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that it is decidable.

I know how to prove it with Turing Machines, but not DFAs. So here is my proof for TM:

Let $U\_{\mathrm{TM}} = \\{\left \langle M \right \rangle|M \text{ is a TM that has a useless state}\\}$. We show that $U\_{\mathrm{TM}}$ is undecidable by a reduction from $\mathrm{HALT\_{TM}}$ to $U\_{\mathrm{TM}}$:

If $\left \langle A,w \right \rangle \in \mathrm{HALT\_{TM}}$, then $A$ halts on input $w$ and $M\_A$ visits all its states on every input; thus, $\left \langle M\_A \right \rangle \notin U\_{\mathrm{TM}}$. iIf $\left \langle A,w \right \rangle \notin \mathrm{HALT\_{TM}}$, then $A$ loops on input $w$ and so does $M\_A$; therefore, $M\_A$ will never visit state $q\_u$ and $\left \langle M\_A \right \rangle \notin U\_{\mathrm{TM}}$. Since $\mathrm{HALT\_{TM}}$ is undecidable, $U\_{\mathrm{TM}}$ is undecidable.

But for DFA I have to show that the language is DECIDABLE. Do you have any ideas how I can go with that?

# Answer
> 1 votes
In order to show decidability, you need to provide an algorithm that will always halt, and yields a yes / no answer.

The following algorithm will return if there is a useless state in a given DFA (and can return the useless state).

Given a DFA $A$, run a BFS from the initial state ($q\_0$), and mark every node that is being visited.

When BFS terminate (and it will, because we're dealing with a deterministic finite automata), every state that wasn't visited during the scan is a useless state.

---
Tags: computability, finite-automata
---


# Question
Title: Prove that the equal-length concatenation of regular languages is context free
If A and B are regular, then prove that $A@B = \\{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\\}$ is always context free.

So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.

# Answer
> 3 votes
To expand a bit on @babou's comment, let $M\_A$ and $M\_B$ be the FAs for $A, B$ respectively. Make a PDA that acts like this:

```
(1) repeat
      read the input, using MAs transition rules.
      For each character read, push a marker on the stack.
    until MA enters a final state or no input remains
(2) if no input remains and MA is in a final state, go to (3)
    else if no input remains and MA is in a non-final state, halt and reject
    else nondeterministically go to (1) and (3) [guessing that we're done with the first half]
(3) repeat
      run the PDA on any remaining input, using MBs transition rules
      For each character read, pop the stack
    until the stack is empty or no input remains
(4) if MB is in an accept state, no input remains, and the stack is empty, halt and accept
    else halt and reject

```

(I apologize in advance for any missing details/programming errors, but the intent, I hope, is clear: process the first part of the input, guess that we're in the middle and process the second part.)

# Answer
> 1 votes
You can prove that $A@B$ is context free using closure properties:

* $L\_1 = \\{a^n\\$b^n | n \geq 0\\}$ is context free (generated by $S \rightarrow \\$ \ |\ aSb$)
* Define $f: \\{a,b\\} \rightarrow \Sigma$. Context free languages are closed under homomorphism, so $L\_2 = f(L\_1) = \\{u\\$v\ |\ u,v \in \Sigma^\* , |u|=|v| \\}$ is context free
* Regular languages are closed under concatinations, so $L\_3 = A\\$B$ is also regular
* The intersection of context free language with regular language is context free, so $L\_4 = L\_3 \cap L\_2$ is context free.
* $L\_4 = \\{ x\\$y \ | \ x \in A, y \in B, |x| = |y| \\}$
* Define $h: \Sigma \cup \\{\\$\\} \rightarrow \Sigma^\*$ as follow. $h(\sigma) = \sigma, h(\\$) = \epsilon$
* Context free languages are close under homomorphism, so $h(L\_3)$ is context free.
* $h(L\_4) = \\{ xy \ | \ x \in A, y \in B, |x| = |y| \\} = A@B$

Therefore, $A@B$ is context free.

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


# Question
Title: How to find an IP in overlapping ranges of IPs?
I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP?

I could iterate over all the ranges and check for every range if it contains the IP, but I'm looking for a complexity better than O(n).

# Answer
Store your IP address as an integer or long depending on whether it is 32 or 64 bit. Then put the ranges into an interval tree or similar data structure that will allow you to find all ranges that intersect with a given range or point (in this case the IP address you want to check against). This will have a query time of O(lg N) after a preprocessing time of O(N lgN). For K queries this is thus O((N+K)\*lg N) which should be fast enough.
> 3 votes

---
Tags: algorithms, intervals
---


title: Concatenation of languages in NP

text:
# Question
Title: Concatenation of languages in NP
I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my Prof about the problem today, but I can't wrap my head around it. Can you help me out?

# Answer
> 6 votes
Take the concatenation of $\Sigma^\*$ with any language that contains the empty word but is known not to be in **NP** (for example, an undecidable language).

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: Range update + range query with binary indexed trees
I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates.

I found the following sources:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http://apps.topcoder.com/forums/?module=Thread&threadID=756271&start=0&mc=4#1579597

But even after reading through all of them I could not understand what the purpose of the second binary indexed tree is or what it does.

Could someone please explain to me how the binary indexed tree is modified to handle these?

# Answer
Suppose you had an empty array:

```
0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

```

And you wanted to make a range update of +5 to \[3..7\]:

```
0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

```

How could you store the desired cumulative sums using 2 binary indexed trees?

The trick is to use two binary indexed trees, BIT1 and BIT2, where the cumulative sum is calculated from their contents. In this example, here's what we'd store in the the two trees:

```
0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

```

To find `sum[i]`, you compute this:

```
sum[i] = BIT1[i] * i - BIT2[i]

```

For example:

```
sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

```

To achieve the desired BIT1 and BIT2 values for the previous range update, we do 3 range updates:

* We need to do a range update of +5 to indices 3..7 for BIT1.
* We need to do a range update of +10 to indices 3..7 for BIT2.
* We need to do a range update of -25 to indices 8..9 for BIT2.

Now let's do one more transformation. Instead of storing the values shown above for BIT1 and BIT2, we actually store their cumulative sums. This lets us do the 3 range updates above by making 4 updates to the cumulative sums:

```
BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

```

In general, the algorithm to add a value v to a range\[i..j\] would be:

```
BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

```

where the += and -= syntax simply means to update the BIT cumulative sum data structure with a positive or negative value at that index. Note that when you update the BIT cumulative sum at an index, it implicitly affects all indices to the right of that index. For example:

```
0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

```

Fenwick trees store sums in a binary tree. It is easy to do the updates shown above to a Fenwick tree, in $O(\log n)$ time.
> 9 votes

---
Tags: data-structures, binary-trees, search-trees
---


# Question
Title: Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?
This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was,

> Consider the following six classes of languages: Context free (CFL), Regular(REG), P, NP, Recursive(R), and Recursively enumerable(RE). (1) indicate the relationships between these six classes e.g., by drawing a Venn diagram. (2) name the minimum type of machine needed to recognize languages in the different classes.

OK, so we know that REG$\subseteq$CFL, either P$\subseteq$NP or P=NP, NP=RE, and P=R.

We also know that the minimum machine type for each language class is REG:DFA, CFL:PDA, P/R:DTM, NP/RE:might be NTM.

We know that a Turing machine is more powerful than a pushdown automata, but we can't find anything that actually proves that all CFLs can be recognized in polynomial time, or think of a way to prove it ourselves. When I asked the teacher who originally wrote the problem about this, he didn't have a ready answer.

# Answer
Why, of course. I'd expect any formal language textbook to contain at least proof of this statement:

> The CYK algorithm¹ parses context-free grammars in polynomial time.

Furthermore, note that every CFL is accepted by a PDA (in linear time). PDAs can be simulated by TMs with polynomial overhead.²

---

1. Or any other suitable parsing algorithm; there are several.
2. This claim is *somewhat* true (we always have the other proof after all) but I don't actually know a direct simulation. Do you?
> 7 votes

# Answer
There are several misconceptions in this question and too many to cover in a comment.

1. We do not know that $\mathrm{P}=\mathrm{R}$ or that $\mathrm{NP}=\mathrm{RE}$. In fact, we know that both of these things are false. The time hierarchy theoreom tells us that both $\mathrm{P}$ and $\mathrm{NP}$ are strictly contained within the recursive languages.
2. $\mathrm{P}$ is not the class of languages accepted by any old deterministic Turing machines: they're DTMs running in polynomial time. Similarly, $\mathrm{NP}$ languages are accepted by NTMs running in polynomial time.
3. Without time bounds, the class of deterministic TMs and the class of nondeterministic TMs accept exactly the same languages: you can simulate nondeterminism deterministically but exponentially slower.
4. Also, we know that $\mathrm{REG}\subsetneq\mathrm{CFL}$, which is consistent with what you wrote but a stronger statement. Exercise: can you give an example of a context-free language that is not regular?
5. Another nitpick: you write "$\mathrm{P}\subseteq\mathrm{NP}$ or $\mathrm{P}=\mathrm{NP}$"; the second statement is already included in the first.
> 8 votes

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


# Question
Title: Brzozowski's algorithm for DFA minimization
Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by:

1. reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N'$ for the reverse language,
2. using powerset construction to get $G'$ for the reverse language,
3. reversing the edges (and initial-accept swap) in $G'$ to get an NFA $N$ for the original language, and
4. doing powerset construction to get $G\_{\min}$.

Of course, since some DFA's have an exponential large reverse DFA, this algorithm runs in exponential time in worst case in terms of the size of the input, so lets keep track of the size of the reverse DFA.

If $N$ is the size of the input DFA, $n$ is the size of the minimal DFA, and $m$ the size of the minimal reverse DFA, then **what is the run time of Brzozowski's algorithm in terms of $N$,$n$, and $m$?**

In particular, **under what relationship between $n$ and $m$ does Brzozowski's algorithm outperform Hopcroft's or Moore's algorithms?**

I have heard that on typical examples in *practice/application*, Brzozowski's algorithm outperforms the others. **Informally, what are these typical examples like?**

# Answer
> 6 votes
Most of the below is from Parsing Theory by Sippu and Soisalon-Soininen.

Let $Q$ be the set of states of the DFA. Let $T$ be the input alphabet. Let $|M|=O(|T| \cdot |Q|)$ be the size of the machine. Exercise 3.40 gives a $O(|T|\cdot|Q|^2)$ algorithm for state minimization. As Wikipedia describes, Hopcroft's algorithm has a running time of $O(|T| \cdot |Q| \cdot \log|T|)$ and Moore's algorithm has a running time of $O(|T|^2 \cdot |Q|)$.

Theorem 3.30 states that the subset construction can be done in $O(2^{|T|+\log|T|+\log|Q|})$ yielding an automaton of size $O(2^{|T|+\log|Q|})$ (actually, if the resulting automaton has $|T'|$ states, the running time is $(|T'| + |T|\cdot|M|) \cdot |Q|$). The two reversals and the second determinisation are therefore inconsequential in the running time, so the asymptotic running time of Brzozowski's algorithm is the same as that of the subset construction.

This means that in the worst case, Brzozowski's algorithm is exponentially slower than the other three algorithms. Note that the worst case really does occur: the classic example of the NFA for the language $(a|b)^\*a^k$ has $k+1$ states and its corresponding minimal DFA has $O(2^k)$ states, while the reverse of the NFA is deterministic, so running Brzozowski's algorithm on this reversed NFA triggers the worst-case behavior.

However, if the subset construction yields an automata of size $|T'|=O(|T|)$, then its running time is also $O(|T|^2 \cdot |Q|^2)$, which is often the case on real-life inputs. Furthermore, if proper care is taken when computing the closure of a state, then this can be done much faster in most cases (that is, cases where the closure is small), saving a factor $|T|$ in practice (for essentially the same reason that transitive closures can be computed quite quickly on real-world examples). Furthermore, if the input and intermediate automatons are sparse, which means that states have few transitions, then a factor $|Q|$ is saved, which gives a $O(|T| \cdot |Q|)$ running time on 'good' inputs.

Unfortunately, I'm not familiar enough with Hopcroft's or Moore's algorithms to give an analysis of their running times in typical cases. Wikipedia talks about a $O(|T| \log \log |T|)$ running time in some cases, which would make the three algorithms comparable.

# Answer
> 5 votes
Here's partial answer regarding your third question. In fact, perhaps Brzozowski's algorithm really doesn't outperform all the other algorithms so clearly in DFA minimization.

In \[1\], the authors investigate the practical performance of DFA/NFA minimization algorithms. The algorithms are Hopcroft's, Brzozowski's, and two variants of Watson's. They conclude that there's no clear winner, but Hopcroft's algorithm performs better for DFAs with small alphabets. For NFAs, Brzozowski is clearly the fastest one.

The paper itself is quite short and clearly written. There's also additional discussion and references that might be helpful.

---

\[1\] Almeida M., Moreira N., and Reis R. On the Performance of Automata Minimization Algorithms, Fourth Conference on Computability in Europe, June 2008.

# Answer
> 1 votes
De Felice and Nicaud show that Brzozowski's algorithms is asymptotically hyper-polynomial. David has shown that, for several distributions on final states, Hopcroft's algorithm is slower that Moore's algorithm.

**References**

S. De Felice and C. Nicaud, "Brzozowski Algorithm is Generically Super-Polynomial for Deterministic Automata". In *Proceedings of 17th International Conference on Developments in Language Theory (DLT 2013)*, Lecture Notes in Computer Science, pp. 170–190, 2013. (PDF)

J. David, "Average complexity of Moore’s and Hopcroft’s algorithms". *Theoretical Computer Science*, 417:50–65, 2012. (Science Direct)

---
Tags: algorithms, finite-automata, runtime-analysis
---


title: Dividing large numbers modulo m

text:
# Question
Title: Dividing large numbers modulo m
I have numbers $a$, $b$ and $m$, and I need to get the result of $\ \dfrac{a}{b} \mod m$.

The catch is that while $m \leq 10^9$, $a$ and $b$ can get extremely large ($2^{100,000}$), so I'm keeping them as a multiset of their prime factors.

I read about modular multiplicative inverse but I haven't found a way to use it in this problem and would appreciate any help.

Also, note that $m$ is not necessarily prime;

# Answer
If $a = \prod\_i a\_i$ and $b = \prod\_j b\_j$ then $$\frac{a}{b} \pmod{m} = \prod\_i a\_i \pmod{m} \times \prod\_j b\_i^{-1} \pmod{m},$$ where the products on the right are performed modulo $m$.
> 2 votes

---
Tags: modular-arithmetic
---


# Question
Title: recurrence - Iteration method T(n)=T(n-a)+n
I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1.

So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n =T(((3n-3a)+n)-a)+n =T(4n-4a)+n

this brings me to the Basic: T(kn-ka)+n.

Is it right ? I am not sure how to solve such Terms with a constant ? thank you for your help !!

# Answer
> 0 votes
Hint: Let's solve the case $a = 1$; I'll leave the generalization to you: $$ \begin{align\*} T(n) &= n + T(n-1) \\ &= n + (n-1) + T(n-2) \\ &= n + (n-1) + (n-2) + T(n-3) \\ &= \cdots \\ &= n + (n-1) + (n-2) + \cdots + (1) + T(0) \\ &= \frac{n(n+1)}{2} + T(0). \end{align\*} $$ In the general case, if $n = ma$ then you'll get $am(m+1)/2 + T(0) \approx n^2/(2a) + T(0)$.

# Answer
> 0 votes
Okay :) let´s try again.

T(n) = T(n – a) + n / a=1

1. T(n) = T(n-1) + n /Iterationstep
2. T(n-1) = T(n-2) + (n-1) / (n-2) Iterationstep
3. T(n-2) = T(n-3) + (n-2)

-\> T(n-1), T(n-2) in T(n):

T(n) = T(n-2) + (n-1) + n

T(n) = T(n-3) + (n-2) + (n-1) + n

Base= T(k-a) + kn – ½(k(k-1))

n - k =1 --\> T(1)

T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

(n(n+1))/2= Ω (n2)

So this is my solution for a = 1 I think/hope it is right ?!

---
Tags: recurrence-relation
---


# Question
Title: Turing-recognizable languages closed under star operation
I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a language A = { a2n: *n* \>= 0 }, all strings of a's which length is a power of 2. So here's where I get confused, if I have `A*`, then I can have `(aa)*`, which could then lead to `(aa)(aa)(aa) = aaaaaa`, and this has a length that is not a power of 2. What part of my logic here is wrong?

# Answer
> 1 votes
You're confusing the definition of $A^{\ast}$ and $A$. It is only $A$ in your example that contains strings of $a$s whose lengths are powers of two. $A^{\ast}$ does not have this restriction - it has that restriction that its strings are *made up of* strings from $A$.

So the individual components of each string in $A^{\ast}$ have to have lengths of powers of two (because they're from $A$), but together we only get that for every string $a^{m}$ in $A^{\ast}$ there is some set $N = \\{n\_{1},\ldots,n\_{k}\\}$ (different for each string) such that $m = \sum\_{n\_{i} \in N} 2^{n\_{i}}$.

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


# Question
Title: Is it necessary to traverse every letter in the tape of a Turing Machine?
Say I want to make a very simple Turing Machine that accepts only strings that contain one or more a's. Can I simply send have the machine move a HALT state once it reads one *a*, even if there are many letters after that first a? Or would this be bad practice or unacceptable for a Turing Machine?

# Answer
> 1 votes
To the title question - no, to the flipped version of the same question in the body - yes. It is typically fine to halt without processing the entire input (however see Raphael's answer for certain technicalities in this respect).

There's not really such a thing as "good" or "bad" practice with a Turing Machine in the sense that there are "good" and "bad" practices when programming on a "real" computer.

As they are theoretical models for computations, they are at their best when they prove (or assist in proving) what you need to prove in as clear and direct manner as possible. In this light, as long as your machine only performs permissible actions, then everything is fine - so no cheating, but beyond that it's all good.

# Answer
> 1 votes
There are definitions of Turing machines in which the output is defined to be the tape content from the head on to the right (until the first empty cell) at termination. Depending on whether you allow your TM to (re)write empty cells, you have to more to the right or erase most of the input, or at least insert a gap after your output.

There are special (sub)models for deciders and acceptors. In these, there is no output on the tape; there are special (non-)accepting states in which the TM halts. In such models, you can terminate whenever you want without having to worry about the tape content.

---
Tags: turing-machines
---


title: Internal and External Fragmentation

text:
# Question
Title: Internal and External Fragmentation
I am working over a homework problem and am confused on how to determine whether there is internal and external fragmentation given the following table:

```
Characteristic                   Design 1 Design 2 Design 3
Physical Memory Address Width:     8 bit    16 bit   32 bit
Virtual (Logical) Address Width:   12 bit   20 bit   24 bit
Page/Frame size in bytes:          16 bytes 32 bytes 64 bytes

```

More specifically, which design has the most internal fragmentation and external fragmentation and why?

# Answer
> 1 votes
I have found the answer. External fragmentation happens over time when small spaces in memory are not effectively employed. This leads to hole everywhere in memory. Therefore it cannot be determined from the chart that there is external fragmentation.

On the other hand, internal fragmentation is the idea when there is over-allocation of memory space to a process. In the above chart, internal fragmentation depends on the page/frame size. Since it is possible for a page to only have one byte of data then larger page sizes have more internal fragmentation. Design 3 has the most spread which is the answer.

# Answer
> -1 votes
I know that external fragmentation occurs by memory problem, when we have less memory space in `mvt` partition (multiprogramming with variable no. of task) called external frag..

when we have less memory space in `mft` partition (multiprogramming with fixed no. of tasks) called internal frag....

# Answer
> -1 votes
External Fragmentation happens when a dynamic memory allocation algorithm allocates some memory and a small piece is left over that cannot be effectively used. If too much external fragmentation occurs, the amount of usable memory is drastically reduced. Total memory space exists to satisfy a request, but it is not contiguous.

---
Tags: operating-systems
---


title: Conversion from Decimal form to BCD

text:
# Question
Title: Conversion from Decimal form to BCD
I have seen a way how to convert a decimal number to BCD (packed & unpacked) using 8,4,2,1 weighing forms but how to do it using 4,2,2,1 and 7,4,2,1 ? Any method please.Suggestions

# Answer
> 0 votes
If we want to represent 8 base 10 then it will be represented as follows:

```
A) 7421 code
   8(10)= 7+1 = 8
   1 0 0 1 -> 7 4 2 1 code
   1x7+4x0+2x0+1x1=7+0+0+1=8
   8(10)=1001(7421)

B) 5421 code
   8(10)= 5+2+1
   therefore   5 4 2 1
               1 0 1 1
  8(10)= 1011(5421)

C) 4221 code
   8(10)= 4+2+2
   therefore 4 2 2 1
             1 1 1 0
   8(10)= 1110(4221)

```

There you go. If this is helpful then please select this as an answer.

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: Can subtracting o(1) from the parameter of a function change its Θ-class?
I would like to know if it is possible that two functions $f(n), g(n)$ can exist such that both of the following conditions are met:

1. $g(n) = o(1)$
2. $f(n-g(n)) \neq \Theta (f(n))$

I though I found $1/n$ and $1/n^2$ but I think I got it all wrong.

Is it even possible?!

# Answer
> 4 votes
Let $g(n) = 1/n$ and define $$ f(n) = \begin{cases} n & \text{if $n$ is an integer}, \\ \log \lceil n \rceil & \text{otherwise}. \end{cases} $$ For an integer $n\>1$, $f(n) = n$ while $f(n-g(n)) = \log n$.

---
Tags: asymptotics
---


title: Relations and Zero One Matrices

text:
# Question
Title: Relations and Zero One Matrices
I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices. For example if I have a set A = {1,2,3} and a relation R = {(1,1), (1,2), (2,3), (3,1)}.

What is the resulting Zero One Matrix representation? How exactly do I come by the result for each position of the matrix? How to tell if it is reflexive, transitive, antisymmetric or symmetric?

# Answer
The resulting zero-one representation is the $|A|\times |A|$ matrix $M$ with $M\_{ij} = 1$ if $(i,j) \in R$, and $M\_{ij} = 0$ if $(i,j) \notin R$. In our case, the matrix is $$ M = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}. $$ Take it as an exercise to prove the following properties:

1. $R$ is reflexive iff the diagonal of $M$ is all 1s.
2. $R$ is symmetric iff $M$ is symmetric.
3. $R$ is antisymmetric iff the off-diagonal entries of $M+M^T$ are 0/1 (but not 2).
4. $R$ is transitive iff the support of $M^2$ is a subset of the support of $M$, where the support is the set of non-zero entries.
> 3 votes

---
Tags: discrete-mathematics, matrices
---


title: Simple Pushdown Automaton

text:
# Question
Title: Simple Pushdown Automaton
I'm currently learning about PDAs and their power when constructing them from Context-Free Grammars, however I'm still unsure of how to properly construct a CFG, and then a PDA from that CFG.

In the book, Formal Languages, Automata, and Complexity, by J. Glenn Brookshear, there are a few exercises requiring I construct a PDA from a given CFG.

One of them is

$\qquad L= \\{x^n y^m x^n \mid n,m \geq 0\\}$.

I can construct a PDA for $x^n y^m$, but am unsure of how to finish off the PDA.

# Answer
> 3 votes
You can create a context free grammar for L thus:

```
L -> B | xBx | xLx
B -> ε | yB

```

Then you can follow a construction algorithm converting a context free grammar into a pushdown automaton.

Here is an example of such a construction (please excuse my lousy graphics):

---
Tags: automata, pushdown-automata
---


# Question
Title: PDA - Sum of Two Characters = Sum of Two Other Characters
For one problem I have to solve, I'm given a Language:

```
L = {a^r b^s c^t d^u | r+s = t+u}

```

And from it told to construct a PDA that accepts it. I can construct a PDA for

```
L1 = {a^r b^s | r,s >= 0}

```

And for

```
L2 = {c^t d^u | t,u >= 0}

```

As they are, essentially, the same language. However, I'm confused as to how I can make sure that the sum of characters in `L1` equal those in `L2`

# Answer
You can probably build a PDA for the language $\\{p^nq^n\mid n \ge 0\\}$. If so, you're almost there. Just treat the a's and b's as if they were all p's and the c's and d's as if they were q's, like this (with details elided):

1. Count the a's and b's by pushing a marker on the stack for each one (making sure that all the a's precede any b).
2. Match them up with the c's and d's: for each one seen, pop a marker off the stack (again, making sure that the input is correctly formed).
3. If the stack is empty after having read all the input, accept.
> 1 votes

---
Tags: context-free, automata, pushdown-automata
---


# Question
Title: Counting the number of words accepted by an acyclic NFA
Let $M$ be an acyclic NFA.

Since $M$ is acyclic, $L(M)$ is finite.

**Can we compute $|L(M)|$ in polynomial time?**

**If not, can we approximate it?**

---

Note that the number of words is not the same as the number of accepting paths in $M$, which is easily computable.

---

Let me mention one obvious approach that doesn't work: convert the NFA to a DFA (which will also be acyclic), then count the number of accepting paths in the DFA. This doesn't result in a polynomial-time algorithm, since the conversion can cause an exponential blowup in the size of the DFA.

# Answer
Here's one approach that I expect should give you a multiplicative-factor approximation, with polynomial time running time.

Let $L$ be a regular language that is a subset of $\\{0,1\\}^n$, e.g., $L=L(M) \cap \\{0,1\\}^n$. We will try to compute the approximate size of $L$.

At a high level, our approach to approximate $|L|$ will look something like this:

1. Pick a fraction $p$, where $0\<p\<1$.
2. Choose a regular language $R$ such that, roughly speaking, $R$ is a random subset of $\\{0,1\\}^n$ of size approximately $p2^n$ (i.e., $|R|\approx p2^n$).
3. Check whether $L \cap R$ is non-empty. Note that this check can be done in polynomial time.

Repeatedly perform steps 1-3 for various values of $p$. This gives you some information that will let you approximate $|L|$.

In particular, if $|L|=m$, then we'd expect

$$\Pr\[L \cap R = \emptyset\] = (1-p)^m \approx e^{-pm}.$$

So, if you happen to choose $p=1/m$ and repeat steps 1-3 a bunch of times, you should expect to see an empty intersection about 37% of the time. If you see an empty intersection significantly more often then that, then increase $p$ and try again. If you see an empty intersection significantly less often then that, you might decrease $p$ and try again.

In this way, using something like binary search, you should be able to approximate $|L|$ to within a multiplicative approximation factor.

You'll still need to pick some way to choose $R$ so that it is regular but also behaves like a random subset. There are many possibilities, but one might good way might be to choose a random 2-universal hash $h:\\{0,1\\}^m \to \\{0,1,2,\dots,k-1\\}$, pick $y \in \\{0,1,\dots,k-1\\}$ randomly, and let $R=\\{x \in \\{0,1\\}^n : h(x)=y\\}$. Choosing $k=\lceil 1/p \rceil$ gives you a random set $R$ of approximately the right size, and because $h$ is 2-universal, all of the mathematics above should work out properly.

This should solve your problem for the case where all strings in the NFA have the same length, say $n$. If they have varying lengths, then you can handle each possible length separately. Since $M$ is acyclic, the maximum lengths of any string in $L(M){}$ is at most the number of states in $M$, so this does not increase the runtime too much.

(This construction might remind you of the Valiant-Vazirani theorem about unambiguous SAT.)
> 3 votes

# Answer
Assume that you can count in polynomial time the number of words of a language given by an acyclic NFA. In this case, considering two acyclic NFAs $A\_1$ and $A\_2$, you can compute in polynomial time the cardinal $n\_1$ (resp. $n\_2$) of the language of $A\_1$ (resp. $A\_2$). By a direct product (preserving acyclicity) you can also compute in polynomial time the cardinal $n\_3$ of the intersection of these two languages. The two automata accepts the same language iff $n\_1=n\_2=n\_3$. Therefore you can test the equality of two finite languages given by acyclic automata in polynomial, which is known to be an NP-complete problem. So, unless $P=NP$, you can't solve your problem in polynomial time.
> 1 votes

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


# Question
Title: Average Intelligence Quotient of Computer Scientists?
Have there been studies measuring the average IQ of successful computer scientists/programmers? The US military uses the AFQT test to determine intelligence of potential recruits (100 million Americans aren't intelligent enough to be accepted, according to the source). But I know of no similar way to gauge the average IQ makeup of computer scientists/programmers. That a considerable number of them have a facility with math and have degrees doesn't suggest that they are necessarily geniuses, but does suggest they would place much higher than the average person on IQ tests. I've known a few people who have pursued computer programming and have given up, And not for lack of effort but due to what they felt was a lack of brainpower necessary to grasp a language.

# Answer
> 4 votes
This is not necessarily the most robust estimation, and is just a blog post (hence I'm not sure it's reliable enough to do anything real with), but here is a posting which uses GRE/SAT scores to estimate IQ across different majors. It puts the average IQ of CS students at ~124.

Another blog post uses GRE/SAT scores again to do the estimate, arriving at 128.5 for CS.

Their original data are from here and here, respectively. I haven't puzzled out yet whether they're using the same base data yet.

Undermining these a little is that there are no supporting statistics (again they are just blog posts, not scientific articles).

I would use these results with a great deal of caution. If nothing else, they appear to be heavily biased to the US setting (simply because of the source data), and given the relatively rapid ups and downs of CS popularity, the data for at least one is somewhat old.

---
Tags: education
---


# Question
Title: Can a DPDA be created for a Language which includes the null string?
Can a DPDA be created for a Language which includes the null string?

The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a state, a is some input, and Z is a stack-character.

Also, if you have a transition Delta(q,lambda,Z), you can't accept any other input from that state.

So, back to the original question. Can a DPDA accept a language which lambda and anything else?

# Answer
Yes, we can simply make the starting state an accept state. With no input (i.e. empty string) the machine halts immediately, and accepts.
> 2 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?
Using the following definition:

> Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using:
>
> * Polynomial number of standard computational steps, plus
> * Polynomial number of calls to oracle that solves problem $Y$.
>
> Notation $X \leq\_{P} Y$

Say we had the case where $X$ can be solved in polynomial time using $O(n\log n)$ of computational steps, with zero calls to the oracle / black box used to solve instances of $Y$.

Can we still say $X \leq\_{P} Y$? As 0 still classifies as a polynomial number of calls to the oracle that solves problem $Y$, and a polynomial number of standard computation steps were used to solve $X$.

# Answer
Yes. As you note, $f(n) = \sum\_{i=0}^{k}0\cdot n^{i} = 0$ is a perfectly valid polynomial in $n$ (for every fixed $k$).

What you have left over without the oracle calls is just a polynomial time algorithm. This observation also underlies the fact that any polynomial-time solvable problem has a polynomial-time reduction to *any* other non-trivial problem.
> 2 votes

---
Tags: reductions, polynomial-time
---


# Question
Title: How P2P search engines prevent corruption of distributed index by malicious peers?
As a hobby, I am writing a simple and primitive distributed web search engine. It occurred to me that it currently has no protection against malicious peers trying to skew the search results.

The principle idea of the project is:

* To store the inverse indices and ranking factors in a Kad (Kademlia) DHT (Distributed Hash Table).
* The peers update the inverse indices as they crawl web.

I used Google Scholar to find a solution. It seems that most of the authors of proposed P2P web search ignores the above-mentioned problem.

I think I need some kind of reputation system or trust metrics. My knowledge in this domain is sufficiently lacking. I would very much appreciate a few pointers.

# Answer
When tackling such problems, think in general terms. Researchers have studied the impact of malicious peers in numerous papers. Most of these systems should work.

However, define your problem clearly. Ex: What are the malicious peers trying to do in this case? do you want to:

1. protect your system from unwanted outsiders (security),
2. protect your data from faulty peers (fault tolerance),
3. protect your data from greedy peers (greedy peers), or others?

Also note that Kademlia is very similar to Chord, SkipNet, Pastry and others (some researchers call these networks "common prefix networks - I can't remember", others: ring-based p2p networks, etc ... Some solutions may be designed specifically for these networks. However, I don't see why a solution made for a structured P2P networks would not work for your architecture.
> 1 votes

---
Tags: distributed-systems, fault-tolerance
---


# Question
Title: Where does the need for conditionals (if, switch, jump tables, etc...) truly arise?
I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind.

When we program we have no doubt that we need conditionals, like the if statement. I will use the "if" statement as a reference throughout the topic.

I mean, if we have a program like

```
int main(int argc, char** argv)
{
int n = atoi(*argv);
if(n%2==0)
  printf("even");
else
  printf("odd");
}

```

Given these conditions, where we can only use what comes after the input is passed to the program to perform our computation, i cannot deny that i need an if statement to distinguish between an even and an odd number. This is just an exemple.

But then i wonder, what if we could mess with what comes before the argument passing occurs?

Let's assume that this program is called oddEven.exe. When the user executes the program by writing oddEven(3) for instance, on the command line, the keyboard sends a signal to the computer with the number 3, which is simply written to memory. No analysis is done on the input, it is simply dumped into memory.

Given this situation, once we run the program, we know only what a number (actually a sequence of characters) was written, but not which one was written. Now let's assume that the hardware itself would be responsible for calling the appropriate branch of the program once the number is written, as if two diferente programs were written.

```
int mainEven()
{
//code for even numbers;
printf("even");
}

int mainOdd()
{
//code for odd numbers;
printf("odd");
}

```

The hardware would then be responsible for decoding the signal sent by the keyboard and, treating it as a number, check whether it is odd or even. We could at this point argue that such a machine would make it possible to program without ifs. Yet, haven't we just implemented the if statements at the hardware level? Hence we couldn't get rid of conditionals.

Now, what if the computer was actually made out of several subcomputers, each implementing a diferent branch of the program. We can also see this as if we had 2 computers. Consider that once a button is pushed, computer C1 prints "even" whereas computer C2 prints "odd".

The user would then be responsible for choosing which computer to use based on the output he knows is right for the number he has in mind. At this point, neither the hardware nor the software contain conditionals. Is the problem solved? No! The conditionals are now "running" on the user's brain, who has to decide which computer to use.

My point is, where do conditionals come from? Where do they stop? Can we avoid them somehow? Can you prove me we need them? If we do, why do we put them at the hardware level? Why does the input of a program have to be compared against values to determine the branch to execute?

I am a computer scientist myself, but i feel like i have lost my path once i thought about this subject. I'm having trouble proving that i undeniably need conditionals to perform computation.

I'd be glad for some insightful answers! Thanks in advance

# Answer
> 1 votes
It is certainly possible to avoid all conditionals, but most programmers get majorly annoyed if they try to use functional style on a very large program.

But then, no one ever programs anything serious directly in a Turing machine either.

# Answer
> 1 votes
You have asked basically the same question a few times already, so I suppose this is something you care deeply about. But as long as you don't give a definition of what a conditional is, exactly, you will not really get any definite yes or no answer. For example, in your odd-even example, some code is run or not run based on some condition; I would call this a "conditional" regardless of whether the choice is made in software, or in hardware, or by looking at figures in your morning coffee.

You might find theoretical programming languages like the lambda calculus interesting. In the lambda calculus you have three constructs: a lambda term is either a variable, a function definition, or a function application. There is nothing else (no if-then-else or switch statement), or rather, everything else has to be defined in terms of these three constructs. Still, the lamdba calculus is Turing-complete. You can give a lambda term which behaves like an if-then-else.

This basically works by getting rid of values: every value is a program and thus has certain behavior. The value true is a function which takes two arguments, evaluates the first and ignores the second argument. The value false is a function which takes two arguments, ignores the first and evaluates the second argument. So applying a boolean value to two terms results in the first term being evaluated if the boolean is true, and the second if the boolean is false. Something like this might come close to what you mean by a language without conditionals.

# Answer
> 0 votes
Let's remove the user from the equation. Simple use case. A computer needs to process information arrived from another computer. Based on what information arrived or from who it arrived the computer needs to do specific operations.

Let's say we have a server that manages a home network and depending on what information comes from each computer he needs to do specific stuff.

How would he choose what to do without a conditional?

Also explaining on your code. Let's say now that you indeed have a separate piece of software for exactly each part of a conditional.

```
int mainEven()
{
//code for even numbers;
printf("even");
}

int mainOdd()
{
//code for odd numbers;
printf("odd");
}

```

but let's say that in your initial program after this check you moved on with the same code. So basically you have code before the conditional and code after the conditional that is the same in both cases. (odd or even) would you copy that code in all different software? Let's say now that you have 30 `if` statements in your code. Each being an `if-else`. You would have 60 different pieces of software that each does a specific part of code. Would you copy all the surrounding code in all 60? Or would you run the softwares in a specific row depending on what the answers are to each `if-else` statement? That would create 60^2 possible combinations (or is it 2^60? I keep getting confused about this).

Now let's go to a video game.

```
if (HP==0){
//player dead
player.FallDown();
gameOverScreen.show();
}

```

How would you code this without a conditional?

---
Tags: turing-machines, computation-models
---


# Question
Title: What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible combinations of $N$ groups of two values are obviously $2^N$.

However I don't know how to "spot" an algorithm with $\Theta(N \log N)$ complexity. A recursive mergesort implementation, for example, is one. What are the common characteristics of mergesort or other $\Theta(N \log N)$ algorithms that would give me a clue if I was analyzing one?

I'm sure there is more than one way an algorithm can be of $\Theta(N \log N)$ complexity, so any and all answers are appreciated. BTW I'm seeking general characteristics and tips, not rigorous proofs.

# Answer
> 17 votes
Your archetypical $\Theta(n \log n)$ is a **divide-and-conquer** algorithm, which divides (and recombines) the work in **linear time** and recurses over the pieces. Merge sort works that way: spend $O(n)$ time splitting the input into two roughly equal pieces, recursively sort each piece, and spend $\Theta(n)$ time combining the two sorted halves.

Intuitively, continuing the divide-and-conquer idea, each division stage takes linear time in total, because the increase in the number of pieces to divide exactly matches the decrease in the size of the pieces, since the time taken by division is linear. The total running time is the product of the total cost of a division stage multiplied by the number of division stages. Since the size of the pieces is halved at each time, there are $\log\_2(n)$ division stages, so the total running time is $n \cdot \log(n)$. (Up to a multiplicative constant, the base of the logarithm is irrelevant.)

Putting it in equations (), one way to estimate the running time $T(n)$ of such an algorithm is to express it recursively: $T(n) = 2 T(n/2) + \Theta(n)$. It's clear that this algorithm takes more than linear time, and we can see how much more by dividing by $n$: $$ \frac{T(n)}{n} = \frac{T(n/2)}{n/2} + \Theta(1) $$ When $n$ doubles, $T(n)/n$ increases by a constant amount: $T(n)/n$ increases logarithmically, or in other words, $T(n) = \Theta(n \log n)$.

This is an instance of a more general pattern: the master theorem. For any recursive algorithm that divides its input of size $n$ into $a$ pieces of size $n/b$ and takes a time $f(n)$ to perform the division and recombination, the running time satisfies $T(n) = a \cdot T(n/b) + f(n)$. This leads to a closed form that depends on the values of $a$ and $b$ and the shape of $f$. If $a = b$ and $f(n) = \Theta(n)$, the master theorem states that $T(n) = \Theta(n \log n)$.

# Answer
> 11 votes
Two other categories of algorithms that take $\Theta(n \log n)$ time:

Algorithms where each item is processed in turn, and it takes logarithmic time to process each item (e.g. HeapSort or many of the plane sweep computational geometry algorithms).

Algorithms where the running time is dominated by a sorting pre-processing step. (For example, in Kruskal's algorithm for minimum spanning tree, we may sort the edges by weight as the first step).

# Answer
> 9 votes
Another category: Algorithms in which the *output* has size $\Theta(n \log n)$, and therefore $\Theta(n \log n)$ running time is *linear* in the *output size*.

Although the details of such algorithms often use divide-and-conquer techniques, they don't necessarily have to. The run-time fundamentally comes from the question being asked, and so I think it is worth mentioning separately.

This comes up in data structures which are based on an augmented binary search tree, where each node stores a linear size data structure to search over the leaves in that node's subtree. Such data structures come up often in geometric range searching, and are often based on a *decomposition scheme*. See Agarwal's Survey.

For a concrete example, consider the range-tree, built to answer two dimensional orthogonal range queries. Although the space was later reduced using some compression techniques to pack multiple objects into a single word, the textbook (and most intuitive) version of the data structure requires $O(n \log n)$ space (each leaf is stored in an auxiliary structure at each node on the path from the leaf to the root, or in $O(\log n)$ places), and the construction algorithm takes time *linear in the space requirement*.

# Answer
> 6 votes
A complexity of $O(n\log n)$ arises from divide and conquer algorithms which divide their input into $k$ pieces of roughly equal size in time $O(n)$, operate on these pieces recursively, and then combine them in time $O(n)$. If you only operate on some of the pieces, the running time drops to $O(n)$.

# Answer
> 5 votes
Those are typically algorithms of the "divide and conquer" variety, where the cost of dividing and combining subsolutions isn't "too large". Take a look at this FAQ to see what kinds of recurrences give rise to this behaviour.

# Answer
> 3 votes
Typically, Divide-and-conquer algorithms will yield O(N log N) complexity.

# Answer
> -1 votes
A generic example of a *loop* (**not** an algorithm per se) that runs in $O(n \log n)$ is the following:

```
for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

```

(note that this nested loops are ***not*** $O(n^2)$. Also note that it isn't divide-and-conquer nor recursive.)

I can't give a concrete example of an algorithm that uses this loop, but it comes up often when coding custom algorithms.

---
Tags: algorithm-analysis, time-complexity, intuition
---


# Question
Title: Is Dijkstra's algorithm just BFS with a priority queue?
According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.

# Answer
You can implement Dijkstra's algorithm as BFS with a priority queue (though it's not the only implementation).

Dijkstra's algorithm relies on the property that the shortest path from $s$ to $t$ is also the shortest path to any of the vertices along the path. This is exactly what BFS does.

Or in another perspective: how would Dijkstra's algorithm behave if all the weights were 1? Exactly like BFS.
> 32 votes

# Answer
> *First, how can we adapt BFS to more general weighted graph $G = (V, E)$?*

Here is an idea from the book "Algorithms (Section 4.4)" by Dasgupta et al:

*For any edge $e = (u,v)$ of $E$ (with weight $l\_e$), replace it by $l\_e$ edges of length $1$, by adding $l\_e - 1$ dummy nodes between $u$ and $v$.*

As a result, the edges of the result graph $G'$ all have unit length. Therefore, we can compute distances in $G$ by running BFS on $G'$.

> *Second, how does Dijkstra algorithm on $G$ beat BFS on the transformed graph $G'$?*

BFS on $G'$ can be really slow if some $l\_e$ are big because it wastes too much time on computing distances to those dummy nodes that we don't care about at all. The Dijkstra algorithm avoids this by setting estimated distances for nodes and relaxing them whenever possible.

> *Third, how does Dijkstra algorithm behave on unweighted graphs?*

It behaves exactly the same as BFS does. We elaborate this from two major points.

* On "relaxation".

For Dijkstra algorithm on general, weighted graph, the relaxation is

```
for all edges (u,v) in E:
    if dist(v) > dist(u) + w(u,v)
       dist(v) = dist(u) + w(u,v)

```

For BFS on unweighted graph, we know that $dist(v) = \infty$ and $w(u,v) = 1$, so the relaxation is simpler:

```
for all edges (u,v) in E:
    if dist(v) = \infty
       dist(v) = dist(u) + 1

```
* On "priority queue".

When Dijkstra algorithm is run on unweighted graph, at any time, the priority queue contains at most two distinct (distance) values. Therefore, a FIFO queue of BFS suffices.
> 4 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Probability of Success in Slotted Medium Access
Suppose you have a network which uses time division multiplexing (i.e. Slotted Aloha). There are $N$ nodes each transmitting in a given slot with probability $p$.

I understand that the probability a node is successful in a slot is $p(1 - p)^{N-1}$. This is just a geometric distribution. But our book then says that the probability there is success in a slot (i.e. no collisions) is $Np(1-p)^{N-1}$.

I don't understand:

1. What the difference between the two probabilities (how is the probability that a node is successful in a slot different from the probability of success in a slot).
2. Why you need to multiply the probability by the number of nodes $N$ since $p(1 -p)^{N-1}$ gives you the probability that one node transmits and all other nodes don't transmit. Could it be because this is the probability that node might transmit given that all other nodes don't transmit, which isn't guaranteed. But we want to find the probability that any of the nodes transmit when all other nodes don't transmit - hence the multiplication by $N$?

# Answer
There is a clear explanation given in these lecture notes MIT course *Digital communication systems* (read by H. Balakrishnan and G. Verghese).

The specific part that you require is this\>

> If each node sends with probability $p$, then the probability that exactly one node sends in any given slot is $Np(1 − p)^{N−1}$.
>
> The reason is that the probability that a specific node sends in the time slot is $p$, and for its transmission to be successful, all the other nodes should not send. That combined probability is $p(1 − p)^{N−1}$. Now, we can pick the successfully transmitting node in $N$ ways, so the probability of exactly one node sending in a slot is $Np(1 − p)^{N−1}$.
> 3 votes

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Are fixed-point combinators general recursive?
I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?

# Answer
Yes, fixed point combinators are sufficient for general recursion and Turing complete computations.

In my Awelon project languages, fixed point combinators are the only way to model recursion. In practice, working directly with fixed point is rather annoying. However, it isn't difficult to build more conventional loop primitives (while, until, repeat) and collections-oriented abstractions (fold, map, scan, foreach, etc.) above fixed points. I hope to build a big enough library of loop functions that I rarely need to directly use fixpoint.

And to answer David Richerby's follow-on question: Yes, there are some interesting things we can do if *all* we have is fixed point combinators.

1. It is possible to name any function by use of secure hash, which can be convenient for content-addressable linking models. With name-based recursion, you cannot use the secure hash of a function's name to refer to itself. Besides myself, it seems Paul Chiusano aims to take advantage of this \[\].
2. The language is much more streamable, by which I mean that program execution can proceed by processing each element in a stream of instructions then forgetting it. This is a nice feature for mobile code or remote control applications. Conventional languages model loops by *jumping backwards*, which requires the computer hold onto the code (i.e. stored program computing).

Use of fixed point combinators is not a sufficient condition for these features. Other aspects of the language must also align. But fixed point combinators do not entangle program semantics with the namespace, which does simplify things.
> 3 votes

---
Tags: programming-languages, turing-completeness, combinatory-logic
---


# Question
Title: Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities
> Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$.

Here's a sketch of a proof I have in mind:

> Suppose $G = (V, \Sigma, P, S)$ is a grammar satisfying $L(G) = L$. Then, since $L$ is inherently ambiguous, it must be that $G$ is ambiguous. Hence, there exists a string, call it $z$, with two different derivations in $G$. Now, if the right-hand side of every production in G is of length $\leq d$, and if $|z| \geq d^{|V| + 1}$, then by Ogden's Lemma, if $d^{|V| + 1}$ or more symbols of $z$ are marked arbitrarily, there exists a decomposition $z = uvwxy$ such that there exists a variable $A$ in G such that
>
> $S \Longrightarrow^\* uAy $
>
> $ A \Longrightarrow^\* vAx$
>
> $A \Longrightarrow^\* w$
>
> Hence, every derivation of $z$ must at least contain the sentential forms $S \Longrightarrow^\* uAy \Longrightarrow^\* uvAxy \Longrightarrow^\* uvwxy = z$
>
> In particular, we may indefinitely "pump" the sentential form $uvAxy$ in both derivations via repeated application of $ A \Longrightarrow^\* vAx$. Hence, the resulting two derivations must at least contain the sentential forms
>
> $S \Longrightarrow^\* uAy \Longrightarrow^\* uvAxy \Longrightarrow^\* uv^iAx^iy \Longrightarrow^\* uv^iwx^iy \in L$
>
> Both derivations; however, are still different, and thus we have that strings of the form $uv^iwx^iy \in L$, with $i \geq 2$ have 2 distinct derivations. Hence, there are infinitely many strings in $L$ with 2 different derivations.

Now, I do see some problems with this sketch. For one, we cannot guarantee that $|z| \geq d^{|V| + 1}$. Second, even if $|z| \geq d^{|V| + 1}$, I'm not sure that we can guarantee that both derivations of z must contain the sentential forms $S \Longrightarrow^\* uAy \Longrightarrow^\* uvAxy \Longrightarrow^\* uvwxy = z$.

> Given $k = |V|$, suppose that every string of length $\geq d^{k+1}$ is unambiguous in G. Let $z$ be an arbitrary string in $L$, with $|z| \geq d^{k+1}$. Then by Ogden's lemma, there exists a decomposition $z = uvwxy$ and a derivation of $uv^2wx^2y$, namely:
>
> $S \Longrightarrow^\* uAy \Longrightarrow^\* uvAxy \Longrightarrow^\* uv^2Ax^2y \Longrightarrow^\* uv^2wx^2y$. Clearly, $|uv^2wx^2y| \geq d^{|V| + 1}$, and thus the provided derivation for the string is unique. But now, mark only the characters in $uv^2wx^2y$ which appear in $u, w, \text{ or } y$. The resulting derivation for $uv^2wx^2y$, obtained using Ogden's Lemma, must differ from the previous derivation for $uv^2wx^2y$, contradiction. Hence, there exists an ambiguous string of length $\geq d^{|V| + 1}$, and we may apply the argument above.

# Answer
> 4 votes
Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous grammar $G'$, thus contradicting the inherent ambiguity. The way you would resolve the ambiguity is something like this: you would generate all small strings (say at most $\ell$, the length of the maximal ambiguous word in $G$) explicitly (and unambiguously), and modify the grammar so that all other strings that it generates are longer; for example, you could have a different subgrammar for every prefix of length $\ell+1$ which simulates $G$.

Of course, this is only one argument, there might be completely different ones.

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


# Question
Title: Dual problem of a maximization primal problem $P$?
Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$.

The dual problem is defined (*Introduction to Linear Optimization by Dimitris Bertsimas*) only for a primal minimization problem.

Then what is the dual problem of $P$ ?

Is it implicit, that the dual problem of $P$ is the dual problem of $P$ stated as the minimization problem $\min -c^T x$ ?

Surely these two primal problems are equivalent in the sense that their optimal solution $ \bar x$ are equal (if it exist). However, the objective values are the same only if we ignore the sign !

# Answer
As you mention, maximization and minimization problems are equivalent. Given a recipe for dualizing a minimization problem, you can convert it into a recipe for dualizing a maximization problem as follows:

1. Negate the objective function and change the maximum to a minimum.
2. Compute the dual.
3. Negate the objective function and change the maximum to a minimum.

The new dual problem will have the same objective value as the primal one (under some mild conditions). This property easily follows from the same fact for duals of minimization problems.

If you're careful enough, you should also get that dualizing twice brings you back to the original program.
> 2 votes

---
Tags: linear-programming
---


# Question
Title: Is it possible to write an HTML compiler with no mutable state?
That's probably a vague question but allow me to try and give an example:

My compiler does transformations on HTML (from HTML to HTML). It scans a flattened DOM tree, and relies on lookbehinds (on elements pushed onto a stack) to decide what transformation to apply. I can give more detail if necessary but I don't want to lose the reader.

Can such logic be alternatively implemented with no mutable state? I have become a big believer in functional programming and have made it a point to make my code as functional-style as possible. I don't like loops that perform actions based on the content of a previous iteration, by saving the information from a previous iteration in stacks or booleans. I need to augment the functionality of this routine and will probably tip the code from being "just about understandable" to "only the author will understand this, everyone else don't touch".

But I have little background in compiler theory & development so am wondering if the problem domain necessitates mutable state in practice.

# Answer
In theory, any program can be treated as functional by treating every operation as "replace the world with a world this piece of state replaced by a different value". In practice ... this actually works pretty well.

Your code will look something like:

```
root_node = parse_html()

for each operation:
    root_node = root_node.replace_using_operation(operation)

```

For a leaf or node that you know won't be affected by this operation, `replace_using_operation` looks like:

```
fn replace_using_operation(self, op):
    return self

```

For the typical non-leaf case, `replace_using_operation` will look like:

```
fn replace_using_operation(self, op):
    children = new List<Node>();
    # pedantically, this is not "functional", but realistically it is.
    # if your language has generators or a iterator map function you can
    # make it purely functional, but most people find this easier to read.
    for each ch in self.children:
        children.append(ch.replace_using_operation(op))
    new_self = new Node(children)
    delete self
    return new_self

```

Of course, depending on what knowledge you have of the operation, you might want to perform different operations on some children. Also note that you're perfectly free to pass additional arguments (including snapshots of other branches of the tree - just remember you don't own them) or to have entirely separate replace\_\* functions instead of passing `operation` as an argument.

This code is *only* a very rough skeleton, after all.
> 2 votes

# Answer
You might be interested to know that XSLT is almost a functional language.

It does not have mutable state. The only reason it is not a functional language is because it "lacks the ability to treat functions as a first class data type" \[1\].

Depending on what your compiler is doing, maybe you could do the same with XSLT. It is specifically designed to do transformations on XML and HTML documents.

\[1\] https://stackoverflow.com/questions/110031/is-xslt-a-functional-programming-language
> 2 votes

---
Tags: compilers, pushdown-automata, functional-programming
---


# Question
Title: Selection problem on the union of two ordered dictionaries
> Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the kth smallest key in the union of keys from S and T. (assuming no duplicates)

I am confused on what the question is asking. I am assuming the keys are not ordered, otherwise all you would have to do is compare the first key in each dictionary, or is that what array-based ordered sequence means? Also are we creating a larger dictionary that holds both S and T inside? Would this add to the complexity if so? For the search algorithm, would we use a binary search since its complexity is O(log n)?

# Answer
The following algorithm uses the divide-and-conquer technique. In the course of divide-and-conquer, the lengths of both sorted arrays $S$ and $T$ will change. We denote the length of $S$ (or, $T$) by $len(S)$ (or $len(T)$) at any time. Notice that I only summarize the algorithm and have intentionally omitted the tricky things about *indexes* (e.g., taking floor or ceiling).

**Notations and Basic Idea:**

At any iteration, denote the median index of $S$ by $s\_m \triangleq len(S) /2$ and the median of $S$ by $S\[s\_m\]$. Similarly, denote the median index of $T$ by $t\_m \triangleq len(T) / 2$ and the median of $T$ by $T\[t\_m\]$.

> The basic idea is as follows: we compare $s\_m + t\_m$ with $k$ and $S\[s\_m\]$ with $T\[t\_m\]$ to determine which (left or right) half part of which array ($S$ or $T$) can be discarded and then we can leave the smaller sub-problem to recursion.

**Algorithm:**

1. Case 1 ($s\_m + t\_m \geq k$):

1.1 Case 1.1 $S\[s\_m\] \geq T\[t\_m\]$.

We can discard the right bigger half of array $S$ (i.e., from $S\[s\_m\]$ to its end). Then *recursively* find the $k$-th smallest element in $T$ and the left smaller half of $S$.

1.2 Case 1.2 $T\[t\_m\] \> S\[s\_m\]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.
2. Case 2 ($s\_m + t\_m \< k$):

2.1 Case 2.1 $S\[s\_m\] \geq T\[t\_m\]$.

We can discard the left smaller half of array $T$. Then *recursively* find the $(k - t\_m)$-th smallest element in $S$ and the right larger half of $S$.

2.2 Case 2.2 $T\[t\_m\] \> S\[s\_m\]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.

**Time Complexity:**

At each iteration, we discard a half of some array. So the time complexity is $O(\lg (len(S)) + \lg (len(T)))$, which is $O(\lg n)$ for input arrays $S$ and $T$ of size $n$.

**References:**

1. How to find the kth smallest element in the union of two sorted arrays?
2. Finding kth smallest number from n sorted arrays A generalization to multiple sorted arrays.
> 1 votes

---
Tags: data-structures, search-problem, dictionaries, selection-problem
---


# Question
Title: What is the formal name for this algorithmic problem?
I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction.

The problem is this, Given a long straight road S is the set of the locations of houses down the road. For example S = \[1,2,3\] would be that houses are placed at 1km 2km and 3km from the end of the road.

We have radio towers that cover a range of 1km and we want to place radio towers at locations along the road so that all houses are covered using the minimum number of towers.

I already know the algorithm to do it, however I'm finding it difficult to understand the proof so would really like the formal name for this problem so that I can research it further.

# Answer
> 7 votes
This general form of problem is a **facility location problem**. The specific version you're asking about is a **covering problem** – you have a set of points (the houses) and you're trying to cover them with circles of some radius (the areas that get reception from each tower).

---
Tags: terminology, optimization
---


# Question
Title: Example of a superword w such that v^2 isn't its subword
What is an example of an infinite word(superword) w such that if a nonempty word v belongs to L = {1,2,3}\*, v^2 isn't a subword of w?

For example if w = 123123123...123 and v = 123, v^2 = 123123 hence it's a subword of w, I can't seem to find a superword that fits the requirement.

# Answer
> 5 votes
There is a dedicated page on "square-free words" on wikipedia here, with references. As you can see, there is an exemple of a square-free word on a three lettre alphabet.

---
Tags: formal-languages
---


# Question
Title: What's an "applicable event" in the context of the FLP paper?
I am reading *Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson.* **"Impossibility of distributed consensus with one faulty process."** Journal of the ACM (JACM) 32.2 (1985): 374-382, available here, the paper in which the well known FLP Theorem was proved.

I am having trouble understanding the notion of an "applicable event" used in this paper. Here's a quote from the paper (Section 2):

> Since processes are deterministic, the step is completely determined by the pair $e = (p,m)$, which we call an *event*. (This "event" should be thought of as the receipt of $m$ by $p$.) $e(C)$ denotes the resulting configuration, and we say that $e$ can be *applied* to $C$.

I can't understand this definition. When is an event applicable? When is it not applicable?

# Answer
An event $e$ is applicable in configuration $C$ if it *could* happen at configuration $C$. Since $e = (p,m)$ means that message $m$ arrives at processor $p$, $e$ is applicable at $C$ if the message queue at $C$ contains the message $m$ directed at $p$. If there is no message directed at $p$ with contents $m$ then $e$ is not applicable at $C$.
> 3 votes

---
Tags: distributed-systems
---