title: Number of states in an AND-OR DAG

text:
# Question
Title: Number of states in an AND-OR DAG
Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND node or an OR node.

Under this setting, I define a notion of a *feasible state*. A state is a feasible if and only if:

* for every AND node in the true state, all of its parents are in the true state.
* for every OR node in the true state, at least one of its parents are also in the true state.

(Note that a state can still be feasible even if some AND node is false but all of its parents are true.)

As an example, consider the following DAG. Grey nodes are leaf nodes (nodes 1 and 2), orange nodes are OR nodes (node 3), and red nodes are AND nodes (nodes 4,5, and 6). Note that nodes 4 and 5 can be classified as either AND nodes or OR nodes since they only have one parent.

There are 18 feasible states of this DAG if I counted right, as seen below. Nodes with a dark interior are true; nodes with a white interior are false.

**Question**: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?

# Answer
> 3 votes
Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x\_{i\_1} \lor x\_{j\_1}) \land \cdots \land (x\_{i\_m} \lor x\_{j\_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no efficient algorithm for solving your problem. In particular, you won't find any closed form.

Roth showed that the number of satisfying assignments is even NP-hard to approximate within $2^{n^{1-\epsilon}}$ for any $\epsilon \> 0$. This means that even finding a decent closed-form approximation can be ruled out.

---
Tags: counting, dag
---


# Question
Title: Difference between IO threads and worker threads
I have read that NodeJs is able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete. They use event driven IO. Similarly in .NET we have Async keyword which allows the worker thread to be returned to perform other tasks while the "IO" call is executing. How does that all work. There has to be some thread monitoring for the IO to complete and notify when its ready?

# Answer
> 2 votes
I don't know NodeJs or .NET, and they would be off-topic here anyway, but the underlying concepts are common among programming frameworks and programming models, so I'll answer in general terms.

The word *thread* can mean several things.

* There is the conceptual meaning: one thing happening after another.
* There is the way this conceptual meaning is represented in a programming language. In almost all programming languages, most ways to combine program fragments lead to those fragments being executed one after the other, thus in a single thread, e.g. `a; b` is a very common syntax for “execute `a` then `b`”. A few keywords, operators or library functions allow code to be executed in a way other than in sequence, e.g. `fork` in Unix or `Async` in .NET. These create conceptual threads.
* There are ways to implement this concept at the operating system level. These fall mainly in two categories (refinements are possible but I won't get into those):

+ Kernel threads are managed by the OS kernel. The threads live independently. If one thread in a program is blocked on an IO call, that doesn't affect the other threads.
    + User threads (also called green threads) are managed by the program. From the perspective of the kernel, there is a single thread, so if the program blocks on an IO call, none of its threads can run. To allow non-blocked threads to keep running, the programming library must ensure that it makes only non-blocking system calls (it may expose blocking functions in the programming interface, however).

There isn't always a direct match between programming language threads and operating system threads. There are several potential reasons for such a mismatch:

* The language was designed with a certain model in mind, but it's implemented on an operating system which doesn't have primitives that map directly to that model.
* The language induces programmers to use threads a lot, but kernel threads are somewhat expensive. So many programming language threads are executed in the same kernel thread. Instead of using blocking IO, the library functions uses non-blocking IO exclusively, and calls a function such as `select` or `poll` which returns as soon as *one* pending I/O is unblocked.
I don't know NodeJS, but “able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete” sounds to me like this is what's happening.
* The language discourages programmers from explicitly using threads, possibly because threads with shared memory is extremely hard to get right (the potential for race conditions is huge). Instead, it favors higher-level abstractions where parallel threads are mostly independent. Under the hood, those abstractions may be implemented with operating system threads.
I don't know .NET, but `async`/`await` sounds to me like it's implementing a rendezvous abstraction. The `async` keyword creates a thread which lives its own life until `await` joins it with its parent.

---
Tags: threads
---


# Question
Title: Lambda calculus outside functional programming?
I'm a university student, and we're currently studying Lambda Calculus. However, I still have a hard time understanding exactly why this is useful for me. I realize if you do loads of functional programming it might be useful, however I reckon that it's not really needed for learning functional programming, what do you think?

Secondly, is there any use for Lambda Calculus within the realm of Computer Science but outside of functional programming languages?

# Answer
The lambda calculus is fundamental in logic, category theory, type theory, formal verification, ... Basically, anything to do with programming language semantics and formal logic. It is such a fundamental formalism that people working in these fields do not even question the benefit of it.

I think that it is extremely useful for understanding functional programming because it gives you the essence of functional programming. Functions, application, substitution. Based on this you can build your skills in reasoning about functional programs and transformations of them. Higher-order functions are a breeze.

Sure you could learn functional programming without the lambda calculus, but you would never truly understand functional programming without it.
> 15 votes

# Answer
You are asking for an application outside of computer science and logic. That is easily found, for example in algebraic topology it is convenient to have a cartesian closed category of spaces, see convenient category of topological spaces on nLab. The formal language corresponding to cartesian closed categories is precisely the $\lambda$-calculus. Let me illustrate with a very simple example how this comes in handy.

First, as a warmup exercise, suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2 e^x + \log (1 + x^2)$ is differentiable. You do not actually have to prove that it is, you just observe that it is a composition of differentiable functions, therefore differentiable. In other words, you made an easy conclusion based on the *form* of definition.

Now for the real example. Suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by $$f(x) = \left(\lambda f : \mathcal{C}(\mathbb{R}) . \int\_{-x}^{x} f(1 + t^2) dt\right)(\lambda y : \mathbb{R} . \max(x, \sin(y + 3))$$ is continuous. Again, we can immediately answer "yes" because the function is defined using the $\lambda$-calculus and starting from continuous maps $\max$, $\int$, $\sin$, etc.

Various extensions of the $\lambda$-calculus make it possible to do the same sort of thing in other areas. For example, because a smooth topos is a cartesian closed category, any map which is defined using the $\lambda$-calculus, starting from derivatives and the ring structure of the reals (and you can throw in the exponential function if you wish) is automatically smooth. (Actually, the main thrust of the smooth topos is the existence of nilpotent infinitesimals which allow you to meaningfully say things like "we disect a disc into infinitely thin isosceles triangles".)
> 18 votes

# Answer
One way of looking at $\lambda$-calculus is as a simple and terse model of parametersing programs. You parameterise code in almost any programming language that has functions, procedures or methods, and in any language that has modules or that enables you to parameterise types. Parameterisation is a form of reuse. Because $\lambda$-calculus is so simple, the commonalities between many programming languages that enable you to parameterise code, come to the fore especially clearly.

It's certainly possible to be a very good programmer without knowing about $\lambda$-calculus, but you are missing out on something beautiful that is also highly useful.
> 7 votes

# Answer
Microsoft LINQ (Language INtegrated Query) grafts functional programming capabilities into procedural languages. It makes extensive and quite direct use of $\lambda$-calculus to untangle dependencies and segregate portions of the expression tree that can be delegated to the database server. This is an extremely practical application with high commercial value.

I have written a small commercial application using a functional language and I can assure you that while well worthwhile to academics and researchers they are less useful commercially than their procedural cousins. Really it's a question of horses for courses, and most practical of all is a language that can be procedural or functional as required. As a consequence, functional capabilities that were introduced (to C#) in support of LINQ, such as $\lambda$-expressions, get quite a lot of use outside of the context of database queries.

So when you finally find yourself compelled to do icky things because you'd like to be paid, you may find $\lambda$-calculus more useful than you expected even though you almost certainly *won't* be using a functional language.
> 5 votes

# Answer
Without knowing more about it, I hear that linguists are using lambda calculus.

http://www.sfu.ca/~jeffpell/Ling406/LambdaAbstractionOH.pdf, https://files.nyu.edu/cb125/public/Lambda/
> 2 votes

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Difference between a minimal DFA and a canonical DFA
given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The minimum DFA will be unique unless the names of states. Now my question is what is the difference between minimal and canonical DFA? They are the same thing?

# Answer
Yes. The canonical DFA for a regular language $L$ is the automaton that is based on the equivalence classes of the relation defined by $L$, i.e., they cannot be "distinguished" in $L$ by extending them with the same suffix.

It is part of the Myhill-Nerode results that that yields a minimal DFA for $L$.
> 2 votes

---
Tags: regular-languages, automata, finite-automata
---


title: Family of types in type theory

text:
# Question
Title: Family of types in type theory
Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a "family" ?

I understand index by a value (n length sequence) then what you mean by index by a type. Any example how you index by a type ? Thanks.

# Answer
> 6 votes
Consider the example of the dependent type of number sequences of length $n$. It might be defined like this in Coq:

```
  Inductive Sequence : nat -> Type :=
  | nil : Sequence O
  | cons : forall (n : nat), nat -> Sequence n -> Sequence (S n).

```

For every `n : nat` we have a type `Sequence n`. We say that `Sequence` is *indexed by `nat`* or that *`Sequence` depends on `nat`*. We could also say that `Sequence n` depends on the index `n`.

In any case, we are just discussing terminology here. The following are equiavalent ways of saying the same thing:

* Type $B$ depends on type $A$
* $B$ is a type family indexed by type $A$
* $B$ is a dependent type indexed by type $A$
* $B : A \to \mathsf{Type}$
* for $x : A$, $B(x)$ is a type
* $x : A \vdash B(x) \ \mathsf{type}$

The reason we use the word *family* is that in mathematics a collection of sets indexed by a set, $\lbrace A\_i \rbrace\_{i \in I}$, is called a family of sets. It corresponds to a dependent type $A$ indexed by a type $I$.

---
Tags: type-theory, dependent-types
---


# Question
Title: What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use?
I understand what it is, but I don't see how it is any use for algorithms or anything. Maybe I am missing something. I need someone to give me an example of how it can be used so I can understand it better.

# Answer
The obvious application of the lambda calculus is any functional programming language (e.g., Lisp, ML, Haskell), and any language that supports anonymous functions.

As for combinator calculus, does there have to be a "real-world application"? Turing machines, for example, are hardly ever used "in the real world" but they form the basis of the theory of computation. One useful feature of combinator calculi is that they're simpler systems than, e.g., Turing machines. If you want to prove that some other system is Turing-complete, it might be easier to show how it can simulate combinators than to show it can simulate a Turing machine.
> 11 votes

# Answer
I found SKI useful to understand some logical axioms.

For instance, a Hilbert-style axiomatization of (intuitionistic) implication is

$$ \begin{array}{l} (a \rightarrow b \rightarrow c) \rightarrow (a \rightarrow b) \rightarrow a \rightarrow c \\ a \rightarrow (b \rightarrow a) \end{array} $$

The first time I saw these axioms, I wondered why on earth they should work. Sure, it's easy to check that they hold. But why should these be enough, i.e. why using these two postulates alone is enough to prove (through modus ponens) all the other implicational tautologies? Mystery... or is it?

Well, it turns out that every tautology must correspond to the type of some lambda-term, thanks to the Curry-Howard isomorphism. But said lambda term can be equivalently rewritten in term of combinators $S,K$ alone. So, the types of $S$ and $K$ must generate, through application, the types of any tautology. And indeed, the two axioms above are the most general types for $S$ and $K$.
> 5 votes

# Answer
Have a look at Microsoft's LINQ (Language INtegrated Query). It makes extensive and quite direct use of lambda calculus to manipulate and transform expression trees. Probably the most complete and sophisticated example would be Linq2SQL (the SQL Server implementation) which efficiently performs complex transformations that segregate the portions of the expression tree that can be delegated to the database server.

This is hardly the first technology that allows queries that combine data from several sources, but it may well be the first one that automates the untangling of dependencies to leverage the bulk manipulation capabilities of database servers. It's not perfect (sometimes you have to help it out) but it does the grunt work very nicely and with an attention to detail you won't get from humans.

When you *do* have to help it out, understanding the calculus will take you a long way toward figuring out what's bothering it - so in addition to *What use is it?* there's your answer to *Why do I have to learn this when machines will do it for me?*
> 2 votes

---
Tags: algorithms, lambda-calculus, combinatory-logic
---


# Question
Title: What is the number of degrees of freedom of my problem in this Simulated Annealing context?
I'm trying to apply a Simulated Annealing technique to solve my (NP-complete) optimization problem. I'm using this book to help myself out.

In the section on Simulated Annealing and more specifically in the section on practical suggestions for beginners, the authors state:

> *Change in temperature stage*: can take place as soon as one of the 2 following conditions is satisfied during the temperature stages:
> \- $ 12 \cdot N$ pertubations accepted;
> \- $ 100 \cdot N$ pertubations attempted,
> $N$ indicating the number of degrees of freedom (or parameters) of the problem

Because I'm still relatively new to Simulated Annealing, I'm willing to trust this guideline blindly for a first implementation.

A (non-optimal) solution to the problem is represented by a vector of integers $\mathbf{\[a\_1, a\_2, a\_3, ..., a\_n\]}$ with $ 0 \< a\_i \leq f(i), \forall i \in \mathbb{N} : 0 \< i \leq n$.

What is the degree of freedom ($N$) here? Is it $n$?

Additionally, for this not to be a yes/no question:
**Intuitively**, why is this a bad/mediocre/good (pick one) guideline ? (i.e. why $\underline{12} \cdot N$ and $\underline{100} \cdot N$?)

# Answer
The parameter $N$ is the length of the vector you're running simulated annealing on. In your case, $N = n$. The values $12,100$ are completely heuristic, and were probably chosen experimentally.
> 2 votes

---
Tags: heuristics
---


# Question
Title: An algorithm to check if all intervals are disjoint
> There are $n$ intervals on the real line , the intervals are given with start- and end point. The $i$-th interval is $(d\_i,f\_i)$ where $d\_i$ is the start point and $f\_i$ is the end point$d\_i\<f\_i$. it is given that $d\_i,f\_i\in \mathbb Z$ and $0\<d\_i,f\_i\<n^4$
>
> Write an algorithm that checks if all intervals are disjoint.
>
> e.g for $n=3\qquad (2,5),(6,7),(1,4)$ the algorithm will return `false`
>
> because $3$ is common for $(1,4),(2,5)$
>
> For $n=2\qquad (6,7),(1,4)$ the algorithm will return `true`

I've been stuck for a couple of hours, I thought maybe I could put all pairs of points into an array but I'm not sure if I should sort the array or not. Any hints please on how to approach this question?

# Answer
> 2 votes
You can solve this in $O(n)$. Here are some hints:

1. Consider a set of disjoint intervals on the line, sorted from left to right, with endpoints $(x\_1,y\_1),\ldots,(x\_n,y\_n)$. Then $x\_1 \< y\_1 \< x\_2 \< y\_2 \< \cdots \< x\_n \< y\_n$. Given unsorted disjoint intervals, you can recover this order by looking only at the $x$s or only at the $y$s. Use this idea to solve your problem in $O(n\log n)$.
2. Since $0 \< x\_i,y\_i \< n^4$ in your case, you can use radix sort to improve the running time to $O(n)$. Think of each $x\_i$ or $y\_i$ as a base $n$ number with 4 digits.

# Answer
> 0 votes
Two intervals, say $i, j$, have some thing in common only if $d\_i \leq d\_j$ and $d\_j \leq f\_i$ (or $d\_j \leq d\_i$ and $d\_i \leq f\_j$, no difference does it make).

So you can simply sort the intervals by the start point of the intervals. For each interval $i,j$ where $d\_i \leq d\_j$, you should check if $d\_j \leq f\_i$ holds. If so then the interval $\[d\_j,f\_i\]$ is the shared interval between $i,j$. For $n$ intervals you need $O(n\log n)$ to sort and there are $ \binom {n} {2}$ cases to check the start and end point of intervals, so it takes $O(n^2)$ time complexity. In the aggregate the algorithm takes $O(n^2)$ time.

---
Tags: algorithms, data-structures
---


title: Best search in Heap Array

text:
# Question
Title: Best search in Heap Array
Can someone give me the best search algorithm in a max heap?

In particular simply implemented as an array. I knew it has complexity of $O(N)$ *but* it can be done better. For example, if $A\[i\] \< \mathrm{key}$ it's useless to search in the sub-tree with that root in the $i$th position.

# Answer
> 1 votes
Since you don't state otherwise, I assume you are interested in worst-case performance.

Your claim "it can be done better \[than $\Theta(n)$\]" is plainly wrong¹; if the desired key $x$ is on the lowest level but all keys on the second-to-lowest level are larger than $x$, you'll not be able to skip any subtree.

---

1. Assuming we have a "plain" binary max-heap and the algorithm would work as you suggest. For a more general statement we'd have to fix the exact heap implementation and invest more work to prove a lower bound.

---
Tags: algorithms, data-structures, search-algorithms, arrays, heaps
---


# Question
Title: Why do these NFAs need epsilon transitions?
In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.

# Answer
> 3 votes
They do not make a difference. In fact, we don't *need* epsilon transitions, in the strict sense. Even though they can not be just left out in general, they can always be replaced by several edges using the *epsilon closure* (cf. the powerset construction).

These examples most likely stem from Thompson's construction, a simple algorithm that creates an NFA equivalent to a given regular expression. It uses epsilon transitions to link recursively constructed subautomata together.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Does my simple, static hash table have O(1) worst case lookup?
Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the problems, and is there a simple solution?

### Construction

Let's assume we have a static set of $n$ keys. We also have a fully random universal hash function $h\_i(x)$ (let's say we use SHA-2 with $i$ as the IV). Now we try to partition the set of keys into $m$ buckets, where $m = \lceil n/100 \rceil$. First we try with $i$ 0. If one bucket has more than 1000 entries (this is possible, but *extremely* unlikely, much less likely than to get a SHA-2 hash collision), start from scratch, that is re-build the hash table but use a different hash function, that is $h\_1(x)$. Do this in a loop until we find an index $i$ that works. Now the largest bucket has less than 1000 entries. Each bucket is stored as a list, sorted by hash value. The index $i$ is also stored.

### Evaluation

For the static hash table constructed above, with the stored index $i$, calculate $h\_i(x)$. Calculate the bucket, and in this bucket, do a binary search. I believe (hope) that this is an O(1) operation, because there are at most 1000 entries in this bucket.

Closely related: (When) is hash table lookup O(1)?. But I have a static set, and I have a fully random universal hash function. I know about FKS hashing, but I can't use it in my case, because it would require too much memory, and I would like to have a simpler algorithm. I understand my algorithm is terribly inefficient, but I'm mostly interested in a *guaranteed* $O(1)$ worst case access time.

# Answer
Yes, your access time is $\mathcal{O}(1)$. Your construction time is a bit more complicated. Let $P(k)$ be the propability, that a set structure containing $k$ elements has a bucket with more than 1000 entries. If there is an overflow after the initial construction in $\mathcal{O}(k)$, everything is rearranged with costs of $\mathcal{O}(k)$. But this might clash again. Thus you get expected costs of $\mathcal{O}(k) + \sum \limits^\infty\_{j=1}P(k)^j\mathcal{O}(k)=\mathcal{O}\left(\frac{k}{1-P(k)}\right)$.
> 4 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, hash-tables
---


title: Dijkstra's algorithm on huge graphs

text:
# Question
Title: Dijkstra's algorithm on huge graphs
I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.

# Answer
> 6 votes
> There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (\>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

> Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (\<1s for country-wide queries like your 3mio nodes example) and is **optimal** in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

> road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)

# Answer
> 2 votes
You do not need to put all edges that are adjacent in the priority queue. "Lie" to Dijkstra's algorithm and give it only the shortest vertex, v, incident to the vertex, say w, pulled off the stack. Then, when v is pulled of the queue you say "oops" I made a mistake and should have given you this vertex too, which is the next closest to vertex w. It is easily seen that this way you will have a correct solution and the queue size is dramatically reduced to one incident vertex only instead of the many. You need though to keep track of the incidences to always give the next closest vertex - when required. One of the comments claimed road networks are planar that is incorrect. In fact, a study has shown they are highly non-planar. Think of all motorways crossing via bridges through a city inducing many non-planarities.

# Answer
> 0 votes
Dijkstras algorithm while applicable is regarded as not optimal for this problem although more efficient variants could be considered as "similar". there are various simplifications. road networks are hierarchical and planar. here are the basic approaches. the area is generally known as "route planning in road networks".

* a graph structure can be "compiled" from the adjacency list data. this is the approach in the library you cite, SpatiaLite. these graph structures are stored in a compressed binary format where graph locations are represented by binary-encoded integers etc., so the graph representation and manipulation takes much less space than storing all the road names etc.; it appears the SpatiaLite algorithm is not "online" and runs entirely in memory.
* there are parallel/ distributed algorithms. see eg Scalable GPU Graph Traversal / Merrill, Garland, Grimshaw.
* the question uses client-server terminology ie "queries". the algorithms do not run by "querying" the database in the client-server sense. higher level query languages such as SQL are an interface to the database and may be used to transmit the request to compute the minimal routes but are not used by the algorithm internally. generally the algorithm runs "inside the database" ie entirely "server side". so hence writing a shortest path algorithm in database queries is feasible for small networks but not medium/ large scale ones.
* there is another approach where estimations within small percentages may be acceptable. the basic idea is to keep an index of distances between nodes. see eg Fast and Accurate Estimation of Shortest Paths in Large Graphs / Gubichev, Bedathur, Seufert, Weikum
* this (235p!) Phd thesis is especially applicable. Route Planning in Road Networks / Schultes
* some algorithms use many of these ideas and others, are highly tuned and proprietary and verging on competitive trade secrets. eg Google's. there may be some misleading media on this subject. eg The Simple, Elegant Algorithm That Makes Google Maps Possible which claims/ implies Google uses Dijkstras algorithm without any citation.

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


# Question
Title: A recursive language minus a recursively enumerable language results in a recursive language?
I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question.

Aren't all recursive languages also recursively enumerable? Does this mean the answer to the question is that a recursive language minus a recursively enumerable language results in a recursively enumerable language, but more specifically, a recursive language?

# Answer
> 3 votes
Let $L$ be an r.e. language which is not recursive (for example, $L$ can be the language of descriptions of Turing machines that halt on the empty input). Then $\Sigma^\*$ is recursive but $\Sigma^\* \setminus L$ is not recursive (exercise).

---

More generally, when faced with a question like this, try the following two approaches in parallel:

1. Try to prove the claim.
2. Try to refute the claim using a counterexample.

The two approaches can even feed each other.

---
Tags: formal-languages, turing-machines
---


# Question
Title: How does coarser lock granularity cause an decrease in time required to acquire and release locks?
I understand the principles required to program locks and I have run into the following problem:

In my Operating Systems course, as well as on Wikipedia, one of the notions associated with lock overhead is the time required to acquire and release locks. And it is also implied that coarser granularity leads to less overhead (I agree it causes less memory to be allocated and less time for initializing locks), but I do not agree that it causes less time to be spent acquiring/releasing locks.

In my view, the number of times locks are being acquired/released is dependent only on the number of times threads are trying to enter a critical section and therefore, it should be the same regardless of the granularity chosen for the locks. My lecturer said in the lecture that because there are more locks, therefore the time spent to acquire/release is higher in the case of finer granularity.

It would be great if someone could explain why does coarser granularity lead to a decrease in time required to acquire/release locks compared to finer granularity.

# Answer
Fine-grained locks need to be acquired and released more often. Coarse-grained locks don't need to be acquired or released as often. Therefore, you're both right.

For instance, suppose you're about to do a big, long operation. With a coarse-grained lock, you'd grab the lock before beginning the operation, hold it throughout, and release it at the end -- a total of one acquisition & release. With a fine-grained lock, you might grab and release the lock at multiple times, at each sub-step. Also, you might grab and release multiple locks, because the operation touches multiple resources, each with its own lock.

That said, coarse-grained locks can cause other problems. They can cause deadlock, or they can cause one thread to be stalled waiting for the other thread to perform a long operation. Therefore, they can limit your ability to take advantage of parallelism.

Ultimately, you usually need to balance these competing considerations.
> 3 votes

---
Tags: synchronization
---


# Question
Title: Converting Boolean circuit to Boolean formula in parallel
Let *t* be a fixed constant. I would like to convert a Boolean circuit *C* of depth *t* on *n* inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula *F* on the same *n* inputs, in the sense that for each input vector *x* of length *n*, we have *C*(*x*) = 1 if and only if *F*(*x*) = 1. Some restrictions on the problem: the circuit has size *m* and depth *t*, and I would like the function mapping *C* to *F* to be computable by a PRAM (say) using a number of processors polynomial in *m* and time polylogarithmic in *m*. I don't mind that the size of the resulting formula is *O*(*m**t*), I consider *t* to be a constant.

The approach I envision is to enumerate each path of length *t* from the output gate to each input gate and transform that set of paths into a trie. This trie will then be a tree of branching factor *m* and depth *t* representing a Boolean formula of size *O*(*m**t*), observing that this is a polynomial in *m* if I consider *t* to be a fixed constant. My problem then reduces to the problem of constructing a trie from a set of at most *m**t* strings, each one a string of length at most *t* over an alphabet of cardinality *m*.

Can I construct a trie of strings of length *t* over an alphabet of size *m* in parallel time polylogarithmic in *m*? More generally, can I convert a Boolean circuit of size *m* and depth *t* to a Boolean formula in parallel time polylogarithmic in *m*?

# Answer
> 2 votes
Take a look at the Tseitin transform. The Tseitin transform can be applied in parallel, working separately on each gate. Consequently, this can be implemented using one processor per gate, $O(1)$ time per gate, and the resulting formula has size $O(m)$. Here I'm not counting the time to build the final formula; the final formula is a conjunction of the clauses produced by the processors, with each processor adding $O(1)$ clauses to the final conjunction.

---
Tags: parallel-computing, circuits
---


# Question
Title: context sensitive language finite or infinite
let L be a CSL. (my understanding/ memory/ expectation is) the problem

> is L finite or infinite?

is undecidable.

* where was this 1st proved/ published?
* are there any cases in the literature of analyzing a CSL L in some "limited context" and determining whether it is finite or infinite? (also wondering about machine learning contexts.)

(brief background: the question can arise in analysis/ application of automated theorem proving. one might reduce a theorem "there exist an infinite *x*" to a CSL L which enumerates *x* and the question of whether L is finite or infinite.)

# Answer
It's a standard theorem that it's undecidable whether a given context-sensitive grammar generates the empty language or not.

From this, we can prove that it's undecidable whether a context-sensitive grammar is finite or infinite. Let $L$ be a context-sensitive language. By the standard closure properties for CSL's, if $L$ is context-sensitive, then so is $L^+$. Now if $L$ is empty, then $L^+$ is empty (and thus finite); but if $L$ is non-empty, then $L^+$ is infinite. Consequently, if it were decidable to check whether a CSL is finite or infinite, we could apply that decider to $L^+$ and learn whether $L$ was empty or not -- but the theorem mentioned above implies this is impossible.

Therefore, determining whether a given context-sensitive grammar generates a finite or infinite language is undecidable.

Footnote: You can find a proof of the standard theorem above in many places; e.g., these lecture notes from CS 373 at U Illinois. The result is also mentioned in passing on Wikipedia, which cites Hopcroft and Ullman -- a standard resource on formal languages. The same Wikipedia article also mentions some smaller classes of languages that are contained in CSL.
> 4 votes

---
Tags: formal-languages, computability, reference-request, undecidability, context-sensitive
---


title: A DFA for recognizing comments

text:
# Question
Title: A DFA for recognizing comments
The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with it but I can't figure it out. What's the problem?

FWIW, those tiny signs are stars which are necessary for C-style comment: "/\* comment \*/"
The loop in the state three is "except \*"

# Answer
> 7 votes
* There is no initial state, so there's no automaton. I suppose $1$ is the initial state.
* From state 4 you can still read several times the symbol $\*$ and accept the comment. For example, the coment `/*hello*/` is being accepted, but the comment `/*hello**/` is not. So you need $\delta(4,\*)=4$.
* Also, you need more transitions for the automaton to be a DFA. Remember that a DFA has a defined transition for all symbols from all states.
    + For example, you need transitions from $4$ with other symbols ($\delta(4,x)=3$ for $x\in\Sigma\smallsetminus\\{\*,/\\}$).
    + The same goes for $1$ and $2$, but I leave that as an exercise ;-)

# Answer
> 5 votes
In state 2 there is no transition for when you encounter a character other than `*`. The same is true in state 4 with `/`.

Also it's not entirely clear what happens in state 1 if you encounter something other than `/`, but it looks like that's because that part's intentionally cut off.

# Answer
> 3 votes
First of all, $2$ should not be a final state. As it is (assuming $1$ is starting state), `/` is accepted.

Furthermore, you can not accept comments that contain `*` because after reading `*` you can never get back into $3$ (without reading `/`). Consider this automaton instead:

<sup>\[source\]</sup>

It is straight forward to modify it to be part of a lexer.

# Answer
> 0 votes
Your DFA will not accept the comment `/*hello*world*/` as δ(4,"w") = undefined.

Also, your accepting state looks like it's in the wrong place. Right now your DFA will only accept if the last character of the input is `/` (so `/` and `/**//` would be accepting but `/**/` would not.

Assuming that it should accept on the completion of a comment, the correct DFA looks like this:

Similarly, if you want to recognize one or more comments, you would make 1 your accepting state and δ(4, /) = 1 (instead of 5)

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


# Question
Title: Shortest path with no two consecutive edges from a certain edge set
Given a graph with nodes $N$ and two sets of edges $E\_1$, $E\_2$ where no two edges from $E\_2$ can be used consecutively, find the shortest path between $n\_1, n\_2 \in N$.

Is there a smart way to approach this problem other than a brute force search?

Edit: My first attempt involved trying to construct a graph that satisfies the constraint on $E2$. However if a node $n$ is connected with edges in both $E1$ and $E2$, it is impossible to know whether edges in $E2$ will be available on $n$ because it depends on which edge was used to arrive to $n$.

# Answer
> 0 votes
I can't comment to this question, so add an answer:

---

When you use dijkstra's algorithm, in each iteration it finds a new node (name B after A: A---e---\>B). If this connecting edge (e) is member of E2, then check the last edge in the path to A. Dismiss the just found node if the last edge is member of E2. then continue the algorithm to finding another node.

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


title: Is Karnaugh Map possible for Maxterms?

text:
# Question
Title: Is Karnaugh Map possible for Maxterms?
I read about Minterms i.e. sums of products, simplification using Karnaugh Graph. Can this graph be used for Maxterms, i.e. products of sums, as well? If yes, then how?

If not, then is there some other similar way to use, for simplification of Maxterms? I know, one can always convert Maxterms to Minterms and then use K-Map. I mam looking for some direct way.

# Answer
> 2 votes
Yes you can do it directly on the K-map. In order to get a minimal product of maxterms (aka product-of-sum \[POS\], aka conjunctive-normal-form \[CNF\]), you simply circle/unify the zeros that appear in the K-map instead of the ones. (It doesn't matter how you got the K-map, it can be from any representaiton of the function, it's just a table of the function's output after all). You can also build the K-map from a (not necessarily minimal) POS by adding a zero the K-map for every maxterm (with the remaining squares being ones.) This should be said to varying extents in most textbooks, e.g.

* *Digital Fundamentals* by Thomas L. Floyd, 9th edition, pp. 221-224 has a very detailed example. (I'm guessing the latest, 11th edition has it too, but I haven't checked.)
* *The Electronics Handbook*, Second Edition edited by Jerry C. Whitake, pp. 55-57 has an example too, but this isn't as detailed.
* *Introduction to Digital Electronics* by Reid and Dueck, p. 114 also has an example.
* *Digital Logic Techniques*, 3rd Edition by John Stonham, p. 43.

That this approach is correct comes from De Morgan's laws and double negation. It's the same as if you flipped all zeros and ones in the K-map and SOP-minimized the negated function and then finally applied De Morgan to the result double-negating the function. This is explained on an example in

* *Principles of Modern Digital Design* by P.K. Lala, p. 70.

and probably other textbooks as well.

# Answer
> 1 votes
minterms & maxterms are complements. see eg Minterms, Maxterms, and K-Maps which explains the interrelationship in more detail. see also DeMorgans law used for complements.

# Answer
> 0 votes
Yes, a Karnaugh Map for maxterms is possible. I have a easy and quick method to show.

**Summary:** Take its complement, and you'll get immediately deduce the minterm expression.

**Golden Rule:** We know that the maxterms are the opposite for minterms. To draw the a maxterm expression on the Karnaugh map, all you have to do is simply deduce its minterm and draw on the Karnaugh map.

**Example**: Draw a Karnaugh Map for this maxterm expression:

As you see, this equals to: f4(x,y,z) = M (0,5)
Now, you take the opposite (or complement), which is the minterm: f4(x,y,z) = Sigmam(1,2,3,4,6,7).

Now it is easy, you're working on a minterm. The Karnaugh map for the function would be:

---
Tags: logic, digital-circuits, karnaugh-map
---


# Question
Title: Why is OPT at least the most valuable item for FPTAS Knapsack?
In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V \leq V^\*$, where $V$ is the value of the maximum valued item and $V^\*$ is the optimal solution.).

Why is that? I mean, we could have a knaspack problem with two items, one with value $10000$ and size $10000$, and one with value $1$ and size $1$, and for a knapsack capacity of $1$ clearly the optimal solution is $1$, but $V = 10000$, and $V^\* \< V$.

# Answer
> 3 votes
It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out items that are too large to fit even alone is easily possible in a polynomial-time preprocessing step.

If the sources do not mention that they are sloppy.

And in that case, every item fits into the knapsack alone, hence you can obtain the maximum item value with a trivial singleton solution.

*Nota bene:* As soon as we are talking algorithms and want to derive running times, such assumptions are not necessarily w.l.o.g. In case the running time cost of the preprocessing is dominant we should not lie it away.

---
Tags: algorithms, complexity-theory, approximation, knapsack-problems
---


title: Upper bound for #Monotone k-SAT

text:
# Question
Title: Upper bound for #Monotone k-SAT
*(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)*

Consider a collection of $n$ Boolean variables, $x\_1,\ldots,x\_n$ and a function $F$ on this collection of variables, $F(x\_1,\ldots,x\_n)$. An assignment of true and false values to each Boolean variable is called a *satisfying assignment* if $F(x\_1,\ldots,x\_n)$ is true.

I'm interested in functions $F$ that take the form $(x\_{i\_1}\vee x\_{j\_1} \vee \cdots \vee x\_{k\_1})\wedge \cdots \wedge (x\_{i\_m}\vee x\_{j\_m} \vee \cdots \vee x\_{k\_m})$ where indices are allowed to repeat, a so-called Monotone k-SAT function. Perhaps something worth noting is that not all of the clauses contain $k$ variables, but it is known that $k$ is the most number of variables in all clauses.

**Question**: What sort of bounds on the number of satisfying assignments for $F$ are known? The worst bound is $2^n$; I'm hoping there is something better.

*(Note: this builds on an original question graciously answered by Yuval Filmus here: Number of states in an AND-OR DAG)*

# Answer
A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions. This is simply the number of possible settings of the $n$ variables minus the least number of settings a single $k$-CNF clause can exclude, assuming all the variables in the clause are distinct. You only have to consider the case of a formula with a single clause because adding more clauses can never increase the number of satisfying assignments.
> 2 votes

---
Tags: complexity-theory, combinatorics, satisfiability
---


title: non LL(1) grammar but LL(1) language

text:
# Question
Title: non LL(1) grammar but LL(1) language
I'm reading a Basics of Compiler Design and on page 84 it is making the following statement:

> A language may well be LL(1) even though the grammar used to describe it is not.

Can someone give such an example? I'm not really sure how this is possible. I thought grammars generate languages, therefore if a grammar is non LL(1) then a language generated by it is also non LL(1). Apparently that is not the case.

Any help is appreciated.

# Answer
> 3 votes
If some grammar for $L$ is LL(1), then $L$ is LL(1) (by definition). But the converse is not true: the fact that a particular grammar for $L$ is *not* LL(1) says nothing at all about $L$. In order to demonstrate that $L$ is not LL(1), you would need to show that *no* grammar for the language is LL(1).

For example:

$$L \to a | La $$

is clearly not LL(1), since it is left-recursive. (This grammar is LR(1).)

$$L \to a | aL$$ (which generates the same language) is also not LL(1), since it requires left-factoring. (This grammar is LL(2).)

But there is a simple LL(1) grammar for this language:

$$L \to a L'$$ $$L' \to \epsilon | aL'$$

So we can see that $L$ (the set of non-empty words all of whose symbols are $a$) is LR(1), LL(2) and LL(1).

# Answer
> 5 votes
Well a language is XX iff there *exists* an XX grammar for it. There might be other grammars for an XX language. For instance you might have a context-free grammar for what is actually a regular language.

Read the book. It contains techniques (with examples!) that show how some non-LL(1) grammars can be transformed into LL(1) grammars. The techniques are called *elimination of left recursion* and *factorization*.

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


# Question
Title: Find maximum in array without comparisons between elements
Suppose $A$ is an array of integers, $|A|=n$, $A=\\{a\_i|1\leq a\_i\leq N, i=1\ldots n\\}$.

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:

* $\cal{F}$ should not compare any $a\_i$ with any $a\_j$ ever.
* $\cal{F}$ also should not add, subtract or exploit some fancy facts about integers
* $\cal{F}$ may, however, compare any $a\_i$ with some predetermined constant number, and this number may depend on $N$

Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

***I propose this:***

compare all $a\_i$ with $N/2$, let $L=\\{a\_i\in A|a\_i\<\frac{N}{2}\\}$, $U=\\{a\_i\in A|a\_i\geq\frac{N}{2}\\}$.

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

***Two questions:***

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?

---

I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.

# Answer
```
a) am I correct?

```

No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array.

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is `O(nlogn)`. However, quicksort will take `O(nlogn)` for the average case, and `O(n)` for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take `O(n)` time complexity.

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array.

```
b) is it possible to do better?

```

You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take `O(nlogn)` since building maxheap takes `O(n)` and max-heapifying takes `O(logn)`. It takes only `O(1)` to find a maximum element.
> -1 votes

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


# Question
Title: Show that if S is an arithmetic progression, then A can be recognized by a DFA
A set S of nonnegative integers is called an arithmetic progresion if there exist some integers n and p such that

S = {n + ip : i ≥ 0}

Let A ⊆ {a}∗ and consider S = {| x |: x ∈ A}.

(1) Show that if S is an arithmetic progression, then A can be recognized by a

DFA

(2) Show that if A can be recognized by a DFA, then S is the union of a ﬁnite number of arithmetic

# Answer
> 2 votes
Consider, for example, the series $\langle\\,3, 7, 11, 15, 19, \dotsc\\,\rangle$. That's an arithmetic progression $n+ip$ with $n=3, p=4$. You're asked for the language over $\\{a\\}$ consisting of all strings with lengths in that series, namely $$ L = \\{aaa, aaaaaaa, aaaaaaaaaaa, aaaaaaaaaaaaaaa, \dotsc\\} $$ You're asked for a DFA that will accept all and only those strings.

**Hint**: It'll consist of a chain of states that lead to a final state after reading three $a$'s and then continue with a loop that will lead you back to that final state after seeing four more $a$'s.

With this in mind, you might be able to figure out question (2). If you've seen the Pumping Lemma for regular languages, its proof will give you a hint.

---
Tags: finite-automata
---


title: Show L1 /L2 is regular

text:
# Question
Title: Show L1 /L2 is regular
> Let $L\_1$ and $L\_2$ be two languages over an alphabet $\Sigma$. The quotient of $L\_1$ and $L\_2$ is the language $L\_1/L\_2 = \\{x : \exists y \in L\_2, xy \in L\_1\\}$
>
> Show that if $L\_1$ is regular and $L\_2$ is any language, then $L\_1/L\_2$ is regular.

I've looked up online how to do this but it not very helpful. So far I know that $L\_1$ and $L\_2 \in \Sigma^\*$ and that $L\_1 = \\{xy \mid x \in \Sigma^\* \text{ and } y \in \Sigma^\*\\}$ and we can say it is regular by concatenation and $L\_2 \in \Sigma^\*$ which is any language.

From here, we can say that in $L\_1$, $x$ has an accept state before going to the DFA for $y$ and $L\_1 / L\_2$ would just be eliminating the DFA for $y$, leaving you with just $x$, which still has an accept state, which makes it regular. I don't know how to put this in words and not pictures.

# Answer
Let $A$ be a DFA accepting $L\_1$, and let $Q$ be its set of states. Denote by $L\_A(q)$ the set of words which cause $A$ to move from its initial state to state $q$. For each state $q$ and word $w$, one of the following holds (exercise):

1. For every $x \in L\_A(q)$, $xw \in L\_1$.
2. For every $x \in L\_A(q)$, $xw \notin L\_1$.

We now modify $A$ by determining its accepting states as follows. A state $q$ is accepting if for some word $w \in L\_2$, $xw \in L\_1$ for all $x \in L\_A(q)$. It is not too hard to show that the modified automaton accepts $L\_1/L\_2$ (exercise).
> 2 votes

---
Tags: regular-languages
---


# Question
Title: Minimum length of string using chars appearing in a given string but not a substring of that string
Suppose we're given a string like `"aabaccbbca"`, and want to find a short string that's not a substring of this string. However, we're limited to using the characters that appear in the string: in this case we can use `'a'`s, `'b'`s, and `'c'`s, but nothing else.

In that example case, there's no length-0, length-1, or length-2 solutions. There's lots of length-3 solutions. Actually, finding the minimum length is a lot more interesting than finding a specific solution.

So my question is: how can we efficiently compute the minimum length for which solutions exist to this 'find string with same alphabet that doesn't appear as a substring' problem?

Examples:

```
 minLengthMissingSubstring("") == 1
 minLengthMissingSubstring("a") == 2
 minLengthMissingSubstring("abc") == 2
 minLengthMissingSubstring("aabaccbbca") == 3
 minLengthMissingSubstring("abbaccbbca") == 2
 minLengthMissingSubstring(
    "0001002003004011012013014021022" +
    "0230240310320330340410420430441" +
    "1121131141221231241321331341421" +
    "22423323424324433343444431442223") == 4

```

# Answer
> 3 votes
# $O(n \log\_m n)$ solution, using a trie and a length cutoff

Relevant wikipedia articles: De Bruijn sequence, Trie

With an alphabet size of $m$, there are $m^t$ substrings of length $t$ that need to appear in a string in order to push the minimum missing substring length (our output) past $t$. But each character we add to a string can only eliminate one additional substring of length $t$. If our string is shorter than $m^t$, we know there must be a missing string of length $t$. This gives a bound on the length of the substrings we need to search in terms of the input string's size.

We know the input size $n$ and we know the alphabet size $m$, but we don't know our output value $t$. However, we know that $t$ must satisfy $m^t \leq n$. Re-arranging, we find that $t \leq \log\_m n$. So we can use $t\_{\text{cutoff}} = \lceil\log\_m n\rceil$.

To make it easy to look for missing strings, we're going to insert every substring, up to the cutoff length, into a trie:

```
def buildTrie(text, cutoff):
    root = TrieNode()
    trail = [root]
    for c in text:
        newTrail = [root]
        for t in trail:
            t[c] = t[c] or TrieNode()
            newTrail.add(t[c])
        trail = newTrail[:min(len(newTrail), cutoff - 1)]
    return root

```

The above function takes $O(\text{len}(\text{text}) \cdot \text{cutoff})$ time to finish, which in our case is $O(n \log\_m n)$.

With our truncated trie in hand, we search through it for holes corresponding to missing substrings:

```
def firstLevelWithHole(trieNode, alphabet):
    if trieNode is None: return 0
    return 1 + min(firstLevelWithHole(trieNode[c], alphabet) for c in alphabet)

```

This search scans the whole trie. However, because the trie is cutoff at level $\log\_m n$ and has fan-out at most $m$, we've done only $O(m^{\log\_m n}) = O(n)$ work.

So our overall algorithm is:

```
def minMissingStringLength(text):
    alphabet = new Set(text)
    if len(alphabet) <= 1: return len(text) + 1
    cutoff = math.ceil(math.log(len(text), len(alphabet)))
    trie = buildTrie(text, cutoff)
    return firstLevelWithHole(trie);

```

And it takes $O(n \log\_m n)$ time and $O(n)$ space.

**Notes**

* The algorithm is easily tweaked to return a specific missing substring, instead of just the length.
* It's probably possible to reduce this to $O(n t)$ time by creating the trie in short-substring-first order, and scanning for holes before starting the next level.
* For truly huge alphabets, the dictionary lookups start costing $O(\lg m)$. I've omitted this cost from the analysis. Also you would want to modify the hole-finding to short-circuit instead of evaluating the whole tree, because it could add an $\Omega(m)$ cost otherwise.

---
Tags: algorithms, strings
---


# Question
Title: Theoretical machines which are more powerful than Turing machines
Are there any theoretical machines which exceed Turing machines capability in at least some areas?

# Answer
The Church–Turing thesis (in one formulation) states that everything that can be physically computable can also be computed on a Turing machine. Assuming you believe this theses, and given that you're interested in functions which such machines could compute (and not in, say, interactive computation), then no hypercomputation is possible.

The Church–Turing thesis only concerns itself with what is computable, but not with the efficiency of computation. It is known that Turing machines are not so efficient, though they polynomially simulate classical computers. Quantum computers are believed to be exponentially more efficient than Turing machines. In this sense, you can beat Turing machines (if you could only build a scalable quantum computer).

Scott Aaronson probably has more to say about this — I'll let you look this up on your own.
> 31 votes

# Answer
Yes, there are *theoretical* machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is hypercomputation.
> 51 votes

# Answer
The Church–Turing thesis doesn't need to be taken as an article of faith; it probably makes more sense to regard it as stating a description, a *definition*, of what we mean by the term "computation", and it is quite a narrow notion of computation, too: computation by a single processor executing steps strictly sequentially without external interference. Certain aspects of computation we need to reason about aren't covered by this notion, and many additional pieces of mathematical theory have been developed within computer science to address such concerns.

So the Church–Turing thesis is not so much a defining characteristic of our universe as it is a defining characteristic of a particular way of doing certain things in our universe.

In this respect, it can be likened to Euclidean geometry. Is our universe inherently Euclidean? Why are our methods of measuring land limited by its principles? Can't we have hypergeometry that allows more powerful land measurement? The answer is: we can and we do, but we don't always call the results "land measurement" or "geometry".

Similarly, our theory and practice regarding computation extend beyond what Turing machines can describe (e.g. there are process calculi for describing concurrent systems), but we don't necessarily call those extensions "computation".
> 14 votes

# Answer
One theoretical weakness of a Turing machine is its predictability. An all powerful and omniscient opponent could exploit this weakness when playing some game against the Turing machine. So if a theoretical machine had access to a random source which its opponent could not predict (and could conceal its internal state from its opponent), then this theoretical machine would be more powerful than a Turing machine.

The problem with this type of theoretical machine in real life is not whether the random source is perfectly random or not (assuming it to be perfectly random is a harmless idealization), but that we can never be sure whether we were successful in concealing our internal state from our opponent. So in the concrete case, one can never be sure whether it is valid to idealize the current instance of a situation by such a machine. This is only slightly better than the situation for most types of hypercomputation, where it is unclear to me which idealized situations should be modeled by those (I once replied: So I need some type of all-knowing miracle machine to solve "RE", I didn't know that such machines exists.)

I was recently surprised to find out that one can consistently accept the existence of Turing machines, and reject the existence of Turing machines with access to an oracle for deciding the halting problem problem of a Turing machine. This is because the oracle can lie (but one cannot prove that it lies) and claim that a non-halting computation would actually halt, and then taking forever while answering with an infinite number, when asked for a bound on the number of steps. (I realized this after writing a technical justification for the excuse: Then I might justify my doubts about $\Pi\_2^0$ sentences by explaining that I'm unsure about how to separate finite inputs from infinite inputs, and hence am unsure whether quantification over the inputs is well defined. That excuse itself arose from a conversation with another Thomas, namely Thomas Chust.)
> 5 votes

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


title: Show language is not regular

text:
# Question
Title: Show language is not regular
Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma:

$$\text{(1) L1} = {a^n b^k c^{n+k} : n \>= 0; k \>= 0}$$

$$\text{(2) L2} = {a^n b^k : n \ne k}$$

So far for

1. What I tried: Assume that L is regular. By P.L, there exists a P such that $w = a^pb^pc^{2p}$ there is $w\_i = xy^iz , \mid y \mid \ge 1 , \mid xy \mid \le p $. We can imply $y = a^k$ and assuming k = 1 $w\_0 = xy^0z = xz = a^{p-1}b^pc^{2p}$ which is not an element in L. Therefore there a contradiction and it is not regular. I don't know what to do for the closure properties
2. Assume that L is regular. By P.L, there exists a P such that $w = a^pb^p$ from here im lost since it says $n \ne k$ for 2) can we say that $ w \notin L $ since $n = p = k$ thus it is a contradiction?

# Answer
For these hints, I'm assuming that you know (and are allowed to use) the fact that $\\{a^nb^n\mid n\ge 0\\}$ is not regular.

For (1), if $L\_1$ was regular, then since regular languages are closed under intersection, we'd have $L\_1\cap b^\*c^\*$ was regular. What's that language?

For (2), if $L\_2$ was regular, then since regular languages are closed under complementation, we'd have $\overline{L\_2}$ was regular, and so $\overline{L\_2}\cap a^\*b^\*$ was regular. What's that language?
> 2 votes

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


# Question
Title: What's the difference between the concatenation and union of symbols within a language
I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression

> (a + b)\* (abba\* + (ab)\*ba)

Can someone clarify to what union is compared to concatenation? Looking at

> (a + b)\*

Is it { $\epsilon$, a, b, ab, ba, aa, aab, bbb...)? I just want to make sure, for union, that I can have any combination of a and b in whichever order.

Can I also have an example of what a word from this language may be? From what I gathered

> aaababbaabbaababba
>
> abbaba
>
> bba
>
> ba

would all be valid words in the given language, correct?

# Answer
Simply put,

the kleene star of concatenation gives $$(ab)^\* = \\{\epsilon, ab, abab, ababab, ...\\} $$

while the kleene star of union gives $$(a+b)^\* =\\{\epsilon,a,b,aa,ab,ba,bb,\ldots\\}$$

so you got it correctly, and indeed all the words you write belong to the language.

---

Recall that for any two sets $L,K$ we have
$LK = \\{xy \mid x\in L, y\in K\\}$,
$L+K = L \cup K$,
$L^\* = \\{\epsilon\\} \cup L \cup L^2 \cdots$.

and recall that the regular expression "a" corresponds to the set $\\{a\\}$ and operations between regular expressions correspond to the above operations on sets.
> 7 votes

---
Tags: formal-languages, regular-languages, notation
---


# Question
Title: Why do ACLs (access control lists) have better persistence than capabilities?
Although I understand the principles on which both ACLs and Capabilities operate, I do not see why on system restart it would be favourable to store privileges by using ACLs, instead of capabilities lists as it is suggested in the Operating systems course I am taking. In other words, why do ACLs have better persistence than capabilities?

# Answer
> 2 votes
There's a lot of confusion and regrettable writing out there surrounding the comparison between ACLs and capabilities. Often, when books make a comparison, they are referring to one particular type of ACL system vs one particular type of capability system, but the difference isn't always fundamental. So, if you see some comparison like this, I wouldn't worry about it too much.

In particular, capabilities can certainly have equal persistence to ACLs. As an extreme example: If you have a persistent store and all applications are persistent (so that when the machine reboots, all applications are relaunched with the same state as before the crash), then capabilities will be persistent. You can achieve the same level of persistence. Historically, people who have built capability systems in the past might not have built them that way (usually), but that isn't always a guide to what is or isn't fundamental.

So, I would take issue with the book's claim that ACLs have better persistence than capabilities. That's not necessarily true; it'll depend on specifically how the ACLs and capabilities are implemented by the system and used by applications.

(Also note that so-called "POSIX capabilities" are a bit of a misnomer and it's not clear we should really call them capabilities.)

I do realize that this might or might not help you if you're taking a course, as depending on the instructor, the instructor might expect you to go by what the book says and might not appreciate other perspectives (or, more benignly, want you to understand things from the textbook's perspective before taking a broader view).

---
Tags: operating-systems, security
---


title: What defines a tool as a "compiler"

text:
# Question
Title: What defines a tool as a "compiler"
I've been trying to figure out what technically makes a tool or program a *compiler*.

For example, I know that gcc will compile source code to object files or assembly, hence transforming a programming language to a different form by breaking it down into "words" with some lexer and reading the "grammar" of the words with some parser, and finally compiling it.

But is the term *compiler* limited to transforming specifically programming languages?

For example, there's a tool called doxygen that will read all of the documentation from source code files, break them down, and generate output based on the documentation. Is this considered to be a *compiler*?

# Answer
A compiler translates code written in one programming language into code in another language -- normally, with the semantics of the output code being the same as the input code (or with a strong relationship).

Personally, if you asked me to use the word strictly, I wouldn't call Doxygen a compiler. The output isn't executable code, and doesn't have anything like the same semantics as the input source code.

See also Wikipedia's definition/explanation.

That said, there are many situations where we use a word loosely, when from context it will be understood what we're referring to -- so I'm not sure how useful it will be to look for a super-precise definition of the word. If the specific definition is important in your writing, then it might be best to define how you plan to use the term.
> 9 votes

# Answer
Say you have two (programming) languages $A$ and $B$. For the sake of simplicity, let the "effect" (output, side effects, ...) of a program be given by a language-specific functions $\operatorname{effect}$. Then, a function $c$ is a compiler from $A$ to $B$ if (and only if)

$\qquad \operatorname{effect}\_A(p) = \operatorname{effect}\_B(c(p))$

for all $p \in A$.

Note how this is more general than what D.W. proposes: I do not distinguish types of languages; I only require that languages have semantics, i.e. they are designed to compute something. I would call an algorithm that translates regular expressions to finite automata (or vice versa) a compiler, too.

*Site note:* the existence of compilers between any two Turing-complete languages has been established in computability theory; admissible numberings can be computably converted into one another.
> 4 votes

---
Tags: terminology, compilers
---


# Question
Title: How to find longest recurring pattern from lage string data set?
I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example

TYUF**RIETEY**M0SQZLHBCTN0W1KA9HELAT4LTQ14W7ZW484GSK1XTNOBJ2R6AMGW9KU36G7ITMPF315Y7ESYPR1XE2C1953J0DXUNBJLNTDG7IHS63854SGSS7YDEFJYSFP0DLL54GK6NUZ5UU5F**RIETEY**CPNGHIJOX23QOVSCBYHKE7H**RIETEY**V0H49I5SX9CW967CDGKX3TYCVNVBNCFG**GD**GDGDDFIIPGDSDV**GD**DSRGDGVCZAQRIOPKLMVFGCD**GD**TYGSDCB**GD**USLVAQEFC**GD**G**RIETEY**DGDFG

In above character set there is two substring one is GD and other is RIETEY algorithm able to identify RIETEY because it is longest the substring, also pattern must occur at least twice to be considered a recurrence and patterns will not overlap.

I found a algorithm but it only work for less that 100,000 characters

any suggestion for this problem ?

# Answer
This problem is well-studied; it's aptly called *longest repeated substring problem*.

It can be solved in linear time by creating a suffix tree with Ukkonen's algorithm; the longest repeat corresponds to the labelling of the longest path from the root to an inner node which you find using breadth-first search.

This does not exclude overlapping substrings. Keep track of the smallest $m$ and largest $M$ starting index of sequences nodes represent while creating the tree; a node at depth $n$ (counted in symbols on the path) represents a non-overlapping repeat if and only if $M - m \geq n$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, strings, longest-common-substring
---


# Question
Title: Prove that the language of squares is not regular using homomorphism
If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular.

Assume that the language $L=\\{yy:y \in \\{0,1\\}^\*\\}$ is given. Can you provide a homomorphism for $L$ like $h$ that $h(L)$ is not regular?

Note : I don't want a simple homomorphism. I want a good homomorphism that $h(L)$ is obviously not regular. So there should be no need to use pumping lemma to prove that $h(L)$ is not regular. But you can use the pigeonhole principle.

# Answer
> 3 votes
As illustrated by other answer and comments there seems to be no easy way just using morphisms. Still it is a good observation that simple closure properties can be of help. In your case I would suggest intersection with regular languages as a tool: $L\cap 0^\*10^\*1 = \\{0^n10^n1 \mid n\ge 0\\}$ whch some recognize immediately as non-regular.

Alternatively one could include morphisms, inverse morphisms and intersection with regular languages (or, equivalently, finite state transductions). With these regularity preserving operations $L$ can be transformed in to $ \\{a^nb^n \mid n\ge 0\\}$, mother of all non-regular examples.

# Answer
> 2 votes
You can not prove this using homomorphisms only. There are exactly $2^2=4$ functions $\\{0,1\\} \rightarrow \\{0,1\\}$. All larger co-domains can be ignored by restricting the function to its image.

These functions are:

1. $h\_0 = \\{0 \mapsto 1, 1 \mapsto 1\\}$: $h(L) = \\{(11)^{n}|n\geq 0 \\}$ which is regular
2. $h\_1 = \\{0 \mapsto 1, 1 \mapsto 0\\}$: $h(L) = L$
3. $h\_2 = \\{0 \mapsto 0, 1 \mapsto 1\\}$: $h(L) = L$
4. $h\_3 = \\{0 \mapsto 0, 1 \mapsto 0\\}$: $h(L) = \\{(00)^{n}|n\geq 0 \\}$ which is regular

So, morphism do improve your prove in any way.

> Can you provide a homomorphism for L like h that h(L) is not regular?

The answer to this question is "yes", because $L$ is not regular and $h\_1$ and $h\_2$ map $L$ to $L$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Proof that whether a regular language is finite is decidable
I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states *n* in the given FSM. When you generate all strings from length *0* to *n*, if the machine accepts any of them then the language is non-empty. We don't have to check words with length \> *n* because of the pumping lemma. The question claims that you can solve the decision problem for finiteness in a similar way.

I know intuitively that a regular language is finite if its finite, well-formed regular expression does not contain a Kleene star, but I don't know how to convert this notion around. My thought is that we have to know if there are any words in the language whose length is greather than *n*, but that requires checking all words.

Then I thought: Have the machine count the number of states n in the FSM. Generate all of the strings of length *0* to *n*. Then, check every word to see if the only possible way to pump this word xyz is to make *y≡λ*. If every word pumps only according to this condition, then the language is finite. However, this feels somehow incomplete.

Could someone give me a hint or push me in the right direction? Thanks.

# Answer
> 1 votes
Show that an NFA accepts an infinite language if and only if there is a (directed) path from the initial to an accepting state which contains at least one state more than once.

# Answer
> 2 votes
If $L$ is infinite, it contains strings of unbounded length. Think about the sequence of states visited by the automaton when these strings are accepted. This will give you a condition of the form "$M$ accepts an infinite language implies $X$". Now check that it's actually "if and only if $X$."

# Answer
> 1 votes
How about checking all the strings of length $n$ to **2**$n$? Would that be helpful to derive the required conclusion?

(In a sense, this is rephrasing your solution, right?)

---
Tags: computability, finite-automata, pumping-lemma, decision-problem
---


# Question
Title: How to find loop invariant from weakest precondition?
Consider this code:

Precondition:

Postcondition: `rv == i <==> ∃i, 0 ≤ i ≤ a.length-1, a[i] == key`

`function Find(Array<int> a, int key) returns (int i) {
 i = a.length -1;
 while i ≥ 0 {
 if a[i] == key {return;}
 i = i - 1
 }
 return -1;
}`

Looking at this code, it's basically searching for a key starting from the end of the array. What I am trying to find is a loop invariant using the Weakest Precondition, and prove it. However, I'm unsure if my weakest precondition is correct.I think the weakest precondition (and precondition) is nothing because nothing seems to have to be true before calling this function, maybe except `a!=null`. So if I have no weakest precondition or `a != null`(assuming this is the wp) how can I get a loop invariant? I can't see how you can derive a loop invariant from this. Aside from all this, I think the loop invariant is `∀i,j, j > i ∧ a[j] ≠ key` but I didn't use the weakest precondition to come up with this loop invariant at all. Any ideas on what I am doing wrong here?

# Answer
I'm only familiar with elementary hoare logic, which does not account for returns/exits, which must be mimicked by booleans. So let's rewrite your program to do just that. In fact, it becomes easier to understand once we do so!

```
i ≔ N - 1 ;
found ≔ a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;

```

Where we define

$$ N : a.length $$

Notice that we have 0 ≤ i - 1 instead of 0 ≤ i since after the decrement i ≔ i - 1 the look-up a\[i\] in the next statement might not be well-defined. So the loop guard ensures that the decrement is still non-negative and so the look-up is well defined. In particular, look at case i ≈ 1; then 0 ≤ 0 ≈ 1 - 1 ≈ i - 1 and the loop decreases i to 0 and the look-up is defined; afterwards the test 0 ≤ 0 - 1 fails and the loop terminates.

Now your postcondition speaks of the return value, which is essentially just i, so let's simplify that to obtain

$$ R : 0 ≤ i \< N ⇒ a\[i\] ≈ key $$

Now the postcondition ought to follow from the negation of the loop guard and the loop invariant: so let's take the invariant to be

$$P : i \< N ∧ (found ≡ a\[i\] ≈ key) % \text{ (we always have i \< N and found is true iff a\[i\] ≈ key)} $$

then after the loop we have the post condition can be seen:

```
  after-loop we have the loop guard fails and the invaraint still holds
≡⟨ foramlise ⟩
  (found ∨ i-1 < 0) ∧ (i < N ∧ (found ≡ a[i] ≈ key))
⇒⟨ substitution ⟩
  (a[i] ≈ key ∨ i-1 < 0) ∧ i < N
⇒⟨ weakening: A ∨ B ⇒ A ∨ B ∨ C ⟩
  (a[i] ≈ key ∨ i-1 < 0 ∨ i < 0) ∧ i < N
≡⟨ arithmetic ⟩
  (a[i] ≈ key ∨ i < 0) ∧ i < N
≡⟨ implication ⟩
  (0 ≤ i ⇒ a[i] ≈ key) ∧ i < N
⇒⟨ weakening ⟩
  0 ≤ i < N ⇒ a[i] ≈ key

```

and that's the post-condition!

For ease of reference, let the guard be denoted by B; i.e.,

$$ B : ¬ found ∧ 0 ≤ i - 1 $$

We still haven't actually proved that P is an invaraint: ie that it does not vary with the changes that occur in the loop body and that it is initally true i.e. we need to show

$$ \\{ ? \\} i ≔ N - 1 ; found ≔ a\[i\] ≈ key \\{P\\} $$ and $$ \\{P ∧ B\\} i ≔ i - 1 ; found ≔ a\[i\] ≈ key \\{P\\} $$

Initialisation is seen as follows: the wp for assignment tells us: $$wp(Q , v ≔ e) = e \text{ well-defined } ∧ Q\[e / v\]$$, so applying twice means we need to have the following as pre-condition:

```
  wp(P , i ≔ N - 1 ; found ≔ a[i] ≈ key)
≡⟨ sequence rule ⟩
  wp( wp(P , found ≔ a[i] ≈ key) , i ≔ N - 1)
≡⟨ assignment rule ⟩
  wp( a[i] well-defined ∧ P[ a[i] ≈ key / found ] , i ≔ N - 1)
≡⟨ definitions ⟩
  wp( 0 ≤ i < N ∧ i < N ∧ (a[i] ≈ key ≡ a[i] ≈ key) , i ≔ N - 1)
≡⟨ equivalence ⟩
  wp( 0 ≤ i < N , i ≔ N - 1)
≡⟨ assignment rule ⟩
  0 ≤ N-1 < N
≡⟨ arithmetic ⟩
  1 ≤ N

```

So the precondition is that the array is non-empty and in-particular is non-null (the well-definedness condition that you mentioned).

For the invariance part we need to show

```
   {P ∧ B}  i ≔ i - 1 ; found ≔ a[i] ≈ key {P}
≡⟨ assignment rule ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N ∧ (found ≔ a[i] ≈ key ≡ a[i] ≈ key)}
≡⟨ reflexivitivy of equivalence ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N }
≡⟨ assignment rule ⟩
   P ∧ B ⇒ 0 ≤ i - 1 < N
≡⟨ definitions ⟩
   true

```

Sweet!

So the program now has annotations:

```
{ 1 ≤ N } // array is non-empty
i ≔ N - 1 ;
found ≔ a[i] ≈ key;
{invariant P }
while !found ∧ 0 ≤ i - 1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;
{ R }

```

We've only shown "partial correctness", for complete correctness we must prove termination. In particular, we need to find a bound function bf that is initially positive and is decreased by the loop body: want bf such that for any constant t,

```
{ bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }

```

Since during the loop body we always have P ∧ B and so namely 0 ≤ i - 1, let's take the bound to be

$$ bf : i $$

Now since $B ⇒ 0 ≤ i-1 ⇒ 1 \< i ⇒ 0 \< bf$ we have that bf is initially positive. (One might be tempted to try N-i as bound but that fails since the loop decreases i which means that N-i increases!) It remains to check that it is decreasing: for any t, we have

```
  { bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }
≡⟨ assignment rule ; bf does not mention varaible `found` ⟩
  { bf = t }   i ≔ i - 1 { bf < t }
≡⟨ assigment rule ⟩
  bf = t ⇒ bf[ i-1 / i] < t
≡⟨ definitions ⟩
  i = t ⇒ i - 1 < t
≡⟨ arithmetic ⟩
  true

```

Alright! That was pretty fun!

One final note, if you write this, say in Python, or another language that supports parallel assignment, you can make the program even more succinct!

```
i, found ≔ N - 1 , a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i, found ≔ i - 1, a[i] ≈ key

```

Enjoy!
> 1 votes

---
Tags: correctness-proof, loop-invariants, hoare-logic
---


# Question
Title: Is the union of a non-regular and a regular language regular?
I am studying Automata and stuck in a question that says: Is the following a regular set {a^p, where p is prime} U {even-length strings}?

As we see here this language consists of two sub-languages. The left side one is infinite, and by using prove by pumping lemma, we will wind up that it is not regular. However, the right side one is also infinite but we can build the fsa for it and the regular expression is ((0+1)(0+1))\*. So, it regular language.

What I stuck in is that When we Union regular language with non-regular language what is the the final result will be????

From the OR truth table it says to return TRUE value, either of them TRUE or both.

# Answer
There is no simple rule.

Consider the languages

* $L\_1 = \\{ a^n b^n \mid n \geq 0\\}$,
* $L\_2 = \\{ b^n \mid n \geq 0 \\}$, and
* $L\_3 = \\{ a^n b^m \mid n,m \geq 0 \\}$.

Clearly, $L\_2$ and $L\_3$ are regular while $L\_1$ is not. Furthermore,

* $L\_1 \cup L\_2$ is not regular but
* $L\_1 \cup L\_3$ is.

Therefore, you will have to look more closely at the language at hand and maybe try to proof both claims. Our reference material can help you get started; feel free to post any *specific* questions about your attempts as new questions.
> 1 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Finding a good loop invariant for a powering procedure
Consider the following algorithm for computing integer powers:

```
Procedure power(integer x, integer n)
    power := 1
    for i := 1 to n
        power := power * x
    return power

```

Can we say that the loop invariant is $power \leq x^n$ ?
Before the loop $power$ is initialized to $1$ so its equal to $1 \leq x^n$.

How do we prove maintenance of the invariant?

# Answer
No, you can't say that $power \leq x^n$ is a loop invariant, since it is not maintained by the loop. For example, if $x \> 1$ and at the current iteration $power = x^n$, then the invariant is satisfied at the beginning of the loop but not at the end of the loop.

Also, this loop invariant doesn't help you prove that at the end $power = x^n$, which is presumably your end goal.

Try to think of an invariant which describes the value of $power$ in terms of $x$ and $i$.
> 6 votes

# Answer
Let's rewrite your code using a while-loop so that everything is explicit.

```
{ 1 ≤ n }
i ≔ 0; p ≔ 1;
while i < n:
  i  ≔ i + 1; p  ≔ p * x
{ p ≈ xⁿ }

```

Note that the initialization sets i to 0 instead of 1!

Now after the loop is finished we will know that necessairly n \< i and thattogether with whatever the invaraint is, call it I, we can establish the post-condition:

```
  n ≤ i ∧ I ⇒ p ≈ xⁿ
⇐⟨ arthimetic ; assuming i ≤ n ⟩
  n ≤ i ≤ n ∧ I ⇒ p * xⁿ⁻ⁱ ≈ xⁿ
⇐⟨ one possible solution ⟩
  I ≡ (i ≤ n ∧ p * xⁿ⁻ⁱ ≈ xⁿ)

```

Half of this is the invariant as mentioned in other answers, but ours is different in that it is particular to the while-loop setting with i begun at 0. Also, this is the full invariant, while others only mentioned half of it. The p * xⁿ⁻ⁱ ≈ xⁿ part can be simplified to p ≈ xⁱ but notice that we "calculated" I from what we know about the post-condition and the loop-guard! Moreover, the formulation found above leads to a nifty intutive interpretation:

```
    (product so far) * (product remaining) ≈ total product

```

Anyhow, we've chosen as invariant

```
I : i ≤ n ∧ p ≈ xⁱ

```

For it to be an invaraint, it must be initaly true before the loop begins:

```
  { 1 ≤ n } i ≔ 1; p ≔ x { I }
≡⟨ assignment rule ⟩
  { 1 ≤ n } i ≔ 1 { I[ p / x] }
≡⟨ substitution ⟩
  { 1 ≤ n } i ≔ 1 { i ≤ n ∧ x ≈ xⁱ }
≡⟨ assignment rule ⟩
  1 ≤ n ⇒ 1 ≤ n ∧ x ≈ x¹ }
≡⟨ arithmetic ⟩
  true

```

Also it must be maintained by the loop body,

```
   {I ∧ i < n} i  ≔ i + 1; p  ≔ p * x {I}
 ≡⟨ assignment rule, twice ⟩
   I ∧ i < n ⇒ I[ p * x / p] [i+1 / i]
 ≡⟨ definitions and substitution ⟩
   i ≤ n ∧ p ≈ xⁱ  ∧ i < n ⇒ i+1 ≤ n ∧ p * x ≈ xⁱ⁺¹
 ≡⟨ arithmetic: i < n ⇒ i+1 ≤ n and p ≈ xⁱ ⇒ p*x ≈ xⁱ⁺¹ ⟩
   true

```

Sweet! However, we've only proven "partial correctness". To show total correctness we need to prove that the loop termiantes. That is we need a bound function bf that is intially positive and is decreased by the loop-body. Since the loop guard is i \< n we may choose

```
  bf : n - i

```

and the loop guard ensures that it is initally positive: i \< n ⇒ 0 \< n - i ⇒ 0 \< bf It remains to show that the loop-body decreases it: for any t, we must show

```
   { bf = t } i  ≔ i + 1; p  ≔ p * x { bf < t }
 ≡⟨ assignment rule, twice ⟩
   bf = t ⇒ (bf < t)[ p*x / p] [i+1 / i]
 ≡⟨ defintions and substitution ⟩
   n - i = t ⇒ n - (i + 1) < t
 ≡⟨ arithmetic ⟩
   n - i = t ⇒ n - i - 1 < t
 ≡⟨ arithemtic ⟩
   true

```

Sweet; that was fun!

Best of luck!
> 1 votes

# Answer
$$power = x^i $$is the invariant
> 0 votes

---
Tags: algorithms, correctness-proof, loop-invariants, program-correctness
---


title: How do I describe a DFA?

text:
# Question
Title: How do I describe a DFA?
Consider the alphabet E = ${\[abc\] : a, b, c \in 0,1,...,9)} $ Example \[234\], \[567\], \[897\] are symbols of the alphabet. For a string $w \in $ let n(w) denote the number represented by $ w $: Example for symbol \[345\], n(\[345\]) = 345.

1) Describe a DFA for the language of strings of the form $\[x\_0y\_0z\_0\]\[x\_1y\_1z\_1\] \[x\_ny\_nz\_n\]$ such that

$n(x\_n... x\_1x\_0) + n(y\_n... y\_1y\_0) = n(z\_n... z\_1z\_0)$

This language corresponds of reading the numbers from right to left and position by position; this is how we add numbers by hand.Example $\[819\]\[606\]\[213\]$ is in the language because 268 + 101 =369.

How can we describe something like this? $M = (Q, E, d, q\_0, F)$

where Q : ?

E = ${\[abc\] : a, b, c \in 0,1,...,9)} $

d: ?

$q\_0 = $

F: ?

# Answer
> 1 votes
Notice that it's not unreasonable to slightly extend this problem to an arbitrary number of triples. For example, the single triplet \[123\] is a reasonable candidate to be in your language, since $1+2=3$. Similarly, \[280\]\[135\] is another reasonable candidate, since $12+38=50$. With that in mind, I'll extend the language to all strings of an arbitrary number (including zero) of triples that satisfy the summation requirement. I'll also decide that we'll accept a sequence of triplets only if they represent a sum without a final carry, so we wouldn't accept the string \[000\]\[000\]\[190\] since $100+900=1000$ and there's a final carry out (though \[000\]\[000\]\[190\]\[001\] would be accepted).

The fundamental idea is a very common one: "remember" the current state of the problem by using one state in the DFA for each possible configuration. Here's what we might do:

1. Label the start state $start$. We haven't read any input yet. This will also be the unique final state.
2. Let state $t$ remember that we've seen the first \[, so we have the move $\delta(start, \[)=t$.
3. Next, construct ten states $p\_0, p\_1, \dotsc,p\_9$ to remember the first digit. We'll have the moves $\delta(t,i)=p\_i$, i.e., from $t$ we'll be in state $p\_i$ after having seen input $i$.
4. Now make twenty more states, $q\_0, \dotsc,q\_9$ and $c\_0,\dotsc,c\_9$. The $q$'s will record the sum of the first two inputs if there's no carry and the $c$'s will record the sum if there is a carry. In other words $$ \delta(p\_i,j) =\begin{cases} q\_{i+j} &\text{if } i+j\le 9\\ c\_{(i+j)\bmod{10}} &\text{if } i+j\ge 10 \end{cases} $$
5. Then make two states, $a,b$ to note whether the third input is the sum of the first two and wehther or not we've generated a carry. From state $q\_k$ (sum is $k$ with no carry) we'll pass to state $a$ if the third input is the digit $k$. Similarly, we'll have $\delta(c\_k,k)=b$ meaning that we've just seen the appropriate third digit and we had a carry.
6. Now we've read the first triplet and we're expecting to see a \]. In state $a$ we know we've completed the first triplet and don't have to adjust any subsequent triplet, so $\delta(a,\]) = start$, i.e., we loop back to the start and accept if there's no further input. On the other hand, if we're in state $b$ then we have a correct digit sum, but we also have a carry, so we can't yet accept when we see a \], instead we need to read another triplet. We'll process the \], read a \[ and duplicate the whole process again, this time adjusting for the carry. We'll then have $\delta(b, \])=u$ and $\delta(u,\[)=v$.
7. Starting anew from state $v$, we construct 34 new states exactly as we did in steps (1) - (6). The only difference is that the transitions from the new states corresponding to the original $p$ states (call them $p'\_i$) in step (4) we'll compensate for the previous carry in and have $$ \delta(p\_i,j) =\begin{cases} q\_{i+j+1} &\text{if } i+j+1\le 9\\ c\_{(i+j+1)\bmod{10}} &\text{if } i+j+1\ge 10 \end{cases} $$ The final difference with these new states is that if we get to the new state, $b'$ corresponding to the original $b$, then on seeing \], we go back to state $start'$ and start again.

---

In high-level terms, we have two nearly-identical functions to check whether a triplet $t$ is valid:

* $N(t)$ which checks whether $t$ is valid, assuming no carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.
* $C(t)$ which checks whether $t$ is valid, assuming a carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.

Then, we would have the following pseudocode

```
c = 0
while there's a triplet t to process
   get t
   if c = 0
      c = N(t)
   else
      c = C(t)
end loop
if c = 0
   accept
else
   reject

```

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


# Question
Title: Trouble finding loop invariant for this while loop
I'm having trouble coming up with an invariant for proving partial correctness of this function.

```
def f(A):
    # Pre: A is a list of integers
    # Post: Returns true if and only if there is an even number of positive
    # numbers in A

    even = True
    i = 0
    while i < A.length:
        if A[i] > 0:
            even = not even
        i = i + 1
    return even

```

So far, I have something like:

```
i <= A.length and (even == True or even == False)

```

However, I don't really know whether this is correct or, if it is even, if I can prove that it is inductive. I don't really know how to start the proof and was just looking for some help to point me in the right direction.

Thanks.

# Answer
Unfortunately, you can't prove partial correctness of your algorithm because it is incorrect.

EDIT: The algorithm provided is indeed correct.

Aditionally, you can't prove that an algorithm is "inductive". You can prove its correctness by using loop invariants,which are quite similar to mathematical inductions.

We must show three things about a loop invariant:

# **Initialization:**

Before you start the loop,check if your initialization is correct.

You want to check if there is an even number of positive numbers in your list A. You set up the variable i to equal 0, therefore your loop begins at the first index of your list.

The variable even is set to True. If it were set to false, and you had 0 positive integers, it would return false, which is incorrect. Therefore, initialization is correct.

You can see initialization as your base case.

# **Maintenance:**

If your invariant holds from iteration to iteration.

The body of your while loop checks if an integer in index i of your array A is positive. If that condition is true, it sets the boolean variable "even" to "not even".

Since it flips the value of even equal to the amount of positive integers in your list,the maintenance is correct.

# **Termination:**

What happens when the loop is over?

The last step increments the variable i by 1. When the loop ends, i \< A.length, which is correct.

The algorithm will return either True or False based on the amount of positive integers. Since initialization and maintenance are correct, the algorithm is correct.
> 2 votes

# Answer
Let's rewrite your code so that everything is explicit.

```
{ 0 ≤ n }
e ≔ true; i ≔ 0;
while i < n:
  if a[i] > 0 then e ≔ ¬ e;
  i  ≔ i + 1;
{ e ≈ even (# j : 0..n-1 • a[j] > 0) }

```

where we have used n in place of a.length and the notation `(# x • p)` returns the number of items x that satisfy p: formally

```
(# x : a..b • px) = 0                                             ; if a > b
(# x : a..b • px) = (IF p(b) THEN 1 ELSE 0) + (# x : a..b-1 • px) ; if a ≤ b

```

Now after the loop is finished we will know that necessarily n ≤ i and that together with whatever the invariant is, call it P, we can establish the post-condition:

```
  n ≤ i ∧ P ⇒ e ≈ even (# j : 0..n-1 • a[j] > 0)
⇐⟨ arithmetic ; assuming i ≤ n ⟩
  n ≤ i ≤ n ∧ P ⇒ e ≈ even (# j : 0..i-1 • a[j] > 0)
⇐⟨ one possible solution ⟩
  P ≡ (i ≤ n ∧ e ≈ even (# j : 0..i-1 • a[j] > 0) )

```

Notice that we "calculated" P from what we know about the post-condition and the loop-guard! Moreover, the formulation found above leads to a nifty intuitive interpretation:

```
e if true precisely when we've encountered an even number of positive integers so far

```

Anyhow, we've chosen as invariant

```
P : i ≤ n ∧ e ≈ even (# j : 0..i-1 • a[j] > 0)

```

For it to be an invaraint, it must be initaly true before the loop begins:

```
  { 0 ≤ n } e ≔ true; i ≔ 0 { P }
≡⟨ assignment rule, twice ⟩
  0 ≤ n ⇒ P [ i / 0] [true / e]
≡⟨ definitions ⟩
  0 ≤ n ⇒ 0 ≤ n ∧ e ≈ even (# j : 0..0-1 • a[j] > 0)
≡⟨ there are no i with 0 ≤ i ≤ -1 so the count is 0 ⟩
  0 ≤ n ⇒ 0 ≤ n ∧ e ≈ even 0
≡⟨ arithmetic ; 0 is even ⟩
  true

```

Also it must be maintained by the loop body,

```
 {P ∧ i < n} if a[i] > 0 then e ≔ ¬ e; i  ≔ i + 1; {P}
≡⟨ assignment rule ⟩
 {P ∧ i < n} if a[i] > 0 then e ≔ ¬ e {P [i+1 / i] }

```

Now there are two cases to consider depending on wheather a\[i\] \> 0 holds or not.

**Easy case.** assume it does not hold, `a[i] ≤ 0`, then we must prove `P [i+1 / i]` assuming `P ∧ i < n`:

```
   P [i+1 / i]
 ≡⟨ definition ⟩
   i+1 ≤ n ∧ e ≈ even (# j : 0..i+1-1 • a[j] > 0)
 ≡⟨ assumption i < n yields i+1 ≤ n ⟩
   e ≈ even (# j : 0..i+1-1 • a[j] > 0)
 ≡⟨ definition of count quantifier ⟩
   e ≈ even ( (IF a[i] > 0 THEN 1 ELSE 0) + (# j : 0..i-1 • a[j] > 0))
 ≡⟨ arithmetic: even (m + n) ≡ even m ≡ even n ⟩
   e ≈ ( even (IF a[i] > 0 THEN 1 ELSE 0) ≡ even (# j : 0..i-1 • a[j] > 0) )
 ≡⟨ assumption P yields e ≈ even (# j : 0..i-1 • a[j] > 0) ⟩
   e ≈ ( even (IF a[i] > 0 THEN 1 ELSE 0) ≡ e )
 ≡⟨ case assumption a[i] ≤ 0 ⟩
   e ≈ ( even 0 ≡ e )
 ≡⟨ 0 is an even number and (true ≡ p) ≈ p ⟩
   e ≈ e
 ≡⟨ reflexitivity ⟩
   true

```

Sweet! One more case to go!

**Hard case** assume it does hold, `a[i] > 0`, then we must prove `P [i+1 / i] [¬ e / e]` assuming `P ∧ i < n`:

```
   P [i+1 / i] [¬ e / e]
 ≡⟨ definitions ⟩
   i+1 ≤ n ∧ ¬ e ≈ even (# j : 0..i+1-1 • a[j] > 0)
 ≡⟨ assumption i < n yields i+1 ≤ n ⟩
   ¬ e ≈ even (# j : 0..i+1-1 • a[j] > 0)
 ≡⟨ definition of count quantifier ⟩
   ¬ e ≈ even ( (IF a[i] > 0 THEN 1 ELSE 0) + (# j : 0..i-1 • a[j] > 0) )
 ≡⟨ case assumption a[i] > 0 ⟩
   ¬ e ≈ even (1 + (# j : 0..i-1 • a[j] > 0) )
 ≡⟨ arithmetic: even (m + n) ≡ even m ≡ even n ⟩
   ¬ e ≈ (even 1 ≡ even (# j : 0..i-1 • a[j] > 0))
 ≡⟨ assumption P yields e ≈ even (# j : 0..i-1 • a[j] > 0) ⟩
   ¬ e ≈ (even 1 ≡ e)
 ≡⟨ 1 is not even and (false ≡ p) ≈ ¬ p ⟩
   ¬ e ≈ ¬ e
 ≡⟨ reflexitivity ⟩
   true

```

Sweet! However, we've only proven "partial correctness". To show total correctness we need to prove that the loop termiantes. That is we need a bound function bf that is intially positive and is decreased by the loop-body. Since the loop guard is i \< n we may choose

```
     bf : n - i

```

and the loop guard ensures that it is initally positive:

```
  i < n ⇒ 0 < n - i ⇒ 0 < bf

```

It remains to show that the loop-body decreases it: for any t, we must show

```
   { bf = t } if a[i] > 0 then e ≔ ¬ e; i  ≔ i + 1; { bf < t }
 ≡⟨ assignment rule ; definitions ⟩
   { n - i = t } if a[i] > 0 then e ≔ ¬ e; i  ≔ i + 1; { n - (i + 1) < t }
 ≡⟨ conditional rule; but post-condition makes no use of e so can be ignored ⟩
    n - i = t ⇒ n - i -1 < t
 ≡⟨ arithmetic ⟩
    true

```

Sweet; that was fun!

Best of luck!
> 1 votes

---
Tags: algorithms, correctness-proof, loop-invariants
---


# Question
Title: How to choose symbols to replace for this left-most derivation?
I have a context free grammar such as the following:

$E→E+T | T$
$T→T×F | F$
$F→(E) | a$

Using the left-most derivation, the following can be derived:

$E⇒E+T⇒T+T⇒F+T⇒a+T$
$⇒a+F⇒a+(E)⇒a+(T)$
$⇒a+(T×F)⇒a+(F×F)$
$⇒a+(a×F)=a+(a×a)$

I know what the left most derivation is and I know what the grammar notation means but what I am trying to understand is how should I substitute the symbols in correct order? For example:

I start with:

$E⇒E+T$

I substitute 'E' first on the left and it becomes:

$⇒T+T$

Then I need to substitute $T$ on the left and it becomes:

$⇒F+T$

Why $T×F$ wasn't chosen to replace $T$ and why $F$ in this case?

Also, in the very next step $F$ was replaced by $a$ and why it wasn't replaced by $(E)$?

# Answer
The term "left-derivation" only pertains to choosing the left-most non-terminal in the sentential form.

It does not force you to choose the left-most rule; that would be silly since the rules are a *set*, i.e. they are unordered. Also, you couldn't derive that word at all then, now wouldn't you?

Also, keep in mind that there is no "choosing" going on. This is not a parsing algorithm; grammars only give you a *declarative* definition of languages. There *exists* a derivation that results in that word, and the one you have is an example.

Note that there are ambiguous grammars, that is grammars that have multiple left-most derivations for some words.

If you are really asking about how to find syntax trees algorithmically, take your pick; there are a lot, and then some.
> 1 votes

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