# Question
Title: The set of all words containing more 1's than 2s
I'm currently working through some regular expression questions and I've got a solution for one of the problems that I'm not certain is correct.

The question has this preface.

We only consider languages over the alphabet $\\{0, 1, 2\\}$.

We also view words over this alphabet as ternary numbers. For the language below give either a regular expression that describes it or a proof that the language is not regular. Note that e.g. the set of integers $\\{4, 7, 11\\}$ (in decimal notation) becomes in this view the language $\\{11, 21,102\\}$.

The question - The set of all words that contain more 1s than 2s.

Would the regular expression (11)2 suffice for this?

# Answer
> 1 votes
No. The regular expression $(11)2$ describes the language $\\{ 112 \\}$, which is clearly not the language of all strings with this property.

*Hint*: Can you really count character occurrences using the regular operators?

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


# Question
Title: Proving that REG is reverse-closed against inverse homomorphism
prove/disprove

If inverse homomorphism of languages is regular then languages is also regular?

Let $h$ be a homomorphism , if $h^{-1}(L)$ is regular then $L$ is also regular?

# Answer
We can consider a single letter alphabet here, so words over $\\{a\\}$.

Recall that $h^{-1}(L) = \\{ w \mid h(w) \in L \\}$. Consider *any* language $L\subseteq \\{a\\}^\*$ that contains $\varepsilon$.

Let $h(a) = \varepsilon$. Then $h(w)=\varepsilon$ for every word $w$. Thus $h^{-1}(L) = a^\*$, which is regular ... for every $L\ni \varepsilon$.
> 3 votes

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


# Question
Title: The trick used in the proof of the doubly exponential complexity of Presburger arithmetics
I posted this on MathUnderflow but got no answers, so thought I'd try it here,

I am reading Rabin and Fischer's old paper \[will post a link when possible\] where among other things, the doubly exponential complexity of Presburger arithmetics is proven.

The proof relies on the existence of a formula $I\_{n}(x)$ informally asserting "$x \< 2^{2^{kx+1}}$" with $|I\_{n}| \in O(n)$. Though the construction of this formula is not given in the paper, which was a surprise to me considering that it is presumably highly nontrivial, given that bound and the fact that we only have addition at our disposal!¹

I later learned that the construction of this formula relies on a "trick", previously discovered by Fischer, and independently by Volker Strassen, but I have not managed to track down a paper describing this trick in detail!

So if anyone knows about the paper I am talking about and can either point me in its direction or even describe the trick to me...

This post from Lipton's blog contains a link to the paper as well as mentions \[and provides a rough, unfortunately insufficient for me, sketch of\] said trick, BTW.

¹ I know that this is a vague description. Though, a sufficiently detailed description would be way too long for a SX post, so I just hope that someone that already knows about the paper in question - and thus can make do with that brief sketch - bumps into this and is able to help me.

# Answer
Martin's comment (and Yuval's follow up) gives the reference which explains the construction in some detail.

I'll elaborate a bit because I think it's a gorgeous proof: basically it's performing the "usual" proof of undecidability of PA (arithmetic with addition and multiplication), but *relativized to $2^{2^{c\cdot n}}$*! That is, there is a (short) formula which expresses multiplication up to that number, i.e. a formula $M\_n(x,y,z)$ such that $$M\_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x\< 2^{2^n} $$

Now you build $M\_n$ by induction on $n$, with a crucial trick that is reminiscent of the Karatsuba algorithm for multiplying binary numbers or certain tricks for matrix multiplication:

In the definition for $M\_{n+1}(x,y,z)$ you end up with a conjunction of the form $$M\_{n}(x\_1,y\_1,z\_1)\wedge M\_{n}(x\_2,y\_2,z\_2)\wedge M\_{n}(x\_3,y\_3,z\_3)$$

But you can replace this with $$ \forall u v w,(u=x\_1\wedge v=y\_1\wedge w=z\_1)\vee(u=x\_2\wedge v=y\_2\wedge w=z\_2)\vee(u=x\_3\wedge v=y\_3\wedge w=z\_3)\Rightarrow M\_n(u,v,w)$$

This trick allows a linear increase in size instead of an exponential one (as a function of $n$).

There's a couple of other tricks involved, but this is the main one. The internals of the recursion are important, of course, but the similarity to the Karatsuba trick is really quite striking.
> 7 votes

---
Tags: complexity-theory, reference-request, logic
---


# Question
Title: Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?
It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of langauges, than any Turing machine), does there exist a Turing machine $T$ which can always compute $M$ such that $T(M, x) = M(x)$?

# Answer
> 1 votes
Pick any model of computation, say a class of Arbitrary Automata $\mathcal{A}$, so that $F\_{\mathcal{A}} \subseteq \mathrm{RE}$, i.e. this model is sub-Turing-complete.

Since TMs are an admissible numbering and $\mathcal{A}$ is a numbering of some set of (semi-)computable functions, for every $A \in \mathcal{A}$ there is a Turing machine $f(A)$ with $F\_A = F\_{f(A)}$ -- and we know that this compiler $f$ is computable.

By the existence of a universal Turing machine $U$, we get that $U(\langle f(A) \rangle, x) = A(x)$ for all $x$. Applying the s-m-n theorem gives us a TM $T$ with $T(\langle A \rangle, x) = U(\langle f(A) \rangle, x) = A(x)$.

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


title: CRC error detection

text:
# Question
Title: CRC error detection
I know that to find an error in signal we have to divide given signal with given polynomial and if 0 remains there is no error. But if I have received signal: 0000 0101 0101 0000 1010 0101 and polynomial 10001000000100001(CRC-CCITT) how do I Xor them:

1010101000010100101 (signal without zeroes)

XOR

10001000000100001

Or

000001010101000010100101 (original signal)

XOR

10001000000100001

Also do I remove beginning 0 from signal or leave them ? Thanks in advance

# Answer
Signal with zeroes is same as signal without zeros, just pruning thoese zeroes out gives the original data.

Those zeroes doesn't contribute anything to the data(sometimes called as dummy bits).

1010101000010100101
10001000000100001 $ \hspace{0.7cm} $XOR
$-----------$
0010001000010100001
$ \hspace{0.15cm} $ 10001000000100001 $ \hspace{0.35cm} $ XOR
$-----------$
0110011000010100011
$ \hspace{0.36cm} $ 10001000000100001 $ \hspace{0.15cm} $ XOR
$-----------$
0100010000010000010 $ \hspace{0.15cm} $ **ERROR**
$-----------$
> 0 votes

---
Tags: coding-theory, polynomials, error-correcting-codes, crc
---


# Question
Title: Confused about how to exactly determine the complexity of an Algorithm
Let's take this algorithm as an example.

$PATH$ = {$G$, s, t | $G$ is a directed graph that has a directed path from s to t }.

Prove that $PATH \in P $.

Ok, I know the basic algorithm is to start from node s, place a mark on it, and then look over the rest of the edges and place a mark from node s to node x if there exists a edge from node s to node x. If you place a mark on node t, then accept; otherwise, keep doing this until you run out of nodes, which implies you reject.

I'm getting caught up in implementation details, really. I can most likely envision a turning machine that can do this in polynomial time, but I don't know if this is the right way to go about it,per say. In Sipser, it seems like a very "hand wavy proof." When I encounter an algorithm should I first figure out a way to implement it on a reasonable Turing machine? Or is there a better way to do this. Thank you.

# Answer
> 1 votes
To prove that an algorithm is in $P$ you basically have two options:

1. Show how to solve it using a number of operations that is polynomial in the size of the input. This means you have to specify a Turing machine to do it, and prove that each of the operations takes a polynomial amount of time. Alternatively, you would prove that the turing machine spends a polynomial amount of steps in any non-accept/reject state.
2. Show that your problem can be reformulated as a already-known problem previously proven to be in $P$. Here you have to prove that the reformulation is correct and that it takes polynomial time.

# Answer
> 0 votes
In your case, it should be simple.

You calculate the set of all nodes that can be reached from s. You start with { s }. How many operations does it take at most to add another node to the set or to find that no more nodes can be added? How often will you add another node to the set? With that information, the problem is easily solved.

---
Tags: algorithms, turing-machines
---


# Question
Title: Given a binary matrix, how to find the starting coordinates of a sub matrix?
Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from where the matrix was cropped from.

I encoded some lines at regular intervals. The *position of the* lines follow the equation $y = x^2$. This way when I find the difference between the distance of two lines i.e. $dy/dx = 2x$, I can calculate the value of x and y. This gives me the position of the pixel at that point. So I can subtract the offset and find the starting coordinates.

The multiple lines are for redundancy sake and colours for illustration.

In this way, I can find the coordinates of cropped images of a reasonable size. My question is, "Is there a proper way of doing it?" Also this technique does not work for lossy file compression techniques like jpeg, does a method exist that is more robust?

I have been reading into Space filling curves but I have no idea how to solve this problem using them.

EDIT: I found a thing called m-sequence. I will add it for future reference.

# Answer
Here is one approach. It won't survive JPEG compression, though, so probably you can do better.

Let $m$ be an integer large enough that $2^m$ is significantly larger than both the width and height of the matrix. Choose a maximum-period $m$-bit LFSR; this generates a sequence of bits of length $2^m-1$, say $s\_1,s\_2,s\_3,\dots,s\_{2^m-1}$, where each $s\_i \in \\{0,1\\}$.

Now, construct the original matrix as follows: at coordinate $(i,j)$, the value will be $s\_i \oplus s\_j$.

Given a submatrix, we can find coordinates as follows. First note that given a consecutive range of the sequence $s$ of length at least $$, we can find where in the sequence it was taken from. In other words, given $s\_i,s\_{i+1},\dots,s\_{i+m-1}$, we can recover the value of $i$. (How? Simply trying all possible values of $i$ will work; one property of LFSR sequences is that the map $i \mapsto (s\_i,s\_{i+1},\dots,s\_{i+m-1})$ is bijective, so $i$ will be uniquely determined.)

Now given the submatrix, we'll try to find the coordinates of its upper-left corner, say $(i,j)$. We'll start by looking at the first row of the submatrix, and examine the sequence of values that appear in its grid. This either takes the form $s\_i,s\_{i+1},s\_{i+2},\dots$ or $s\_i \oplus 1, s\_{i+1} \oplus 1, \dots$ according to whether $s\_j=0$ or $s\_j=1$. We can try both possibilities for $s\_j$, and get two candidates for $i$. Then we look at the first column of the submatrix, and obtain two candidates for $j$ in the same way. This gives us two candidates for $(i,j)$, we can check which one is correct by looking at a few other positions in the submatrix.

Then, you can recover the coordinates of its lower-right corner in the same way.

All in all, this will enable you to recover the coordinates of the submatrix, as long as the submatrix is at least $m$ pixels wide and $m$ pixels high.

---

There are other ways as well. For instance, one very simple approach is to fill in the original matrix randomly, and remember how you filled it in. Then given a submatrix it is straightforward to find where it came from (e.g., by checking all possibilities; this can be sped up by precomputing a hash table).

---

In practice, if you plan to print out the original matrix and then take a scan or photo of it, then you might want a different approach that is more robust to the kind of transformations that will typically occur during printing and scanning. That will lead to a very different kind of problem. So if you want to know about how to do that, you should probably ask a separate question focused on those considerations.
> 1 votes

---
Tags: computer-vision, matrices, encoding-scheme
---


# Question
Title: If accepted by dpda and npda,then it is regular. Is it correct?
If accepted by dpda and npda,then it is regular. Is it correct?.I had confusion that some where I studied that a regular language is exactly should accepted by finite automata.....

# Answer
If it's accepted by a DPDA, then clearly it is also accepted by a NPDA with exactly one possible transition for each configuration.

However, there are languages accepted by DPDA's not accepted by any DFA. The canonical example of a non-regular languages $L = \\{a^n b^n \mid n \geq 0\\}$ is accepted by a DPDA by empty stack (an easy exercise should be to design such a DPDA).

You're right that every finite state automata accepts a language that is regular. However, PDA's are not finite state in the larger sense of state that includes not only the internal state $q\_0$, but the contents of the stack. The stack is unbounded in size, hence PDAs are not finite state.
> 2 votes

# Answer
If it is a regular language, then you can make a push down automata (finite automata as well) for accepting it. Non- deterministic Push down automatas accept Context Free Languages, and regular languages is a subset of context free languages. In other words, "Every regular language is a CFL, but converse is not true."
> 0 votes

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


title: Notation: SPACE(n) vs SPACE(O(n))

text:
# Question
Title: Notation: SPACE(n) vs SPACE(O(n))
I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not preferred in this case? In particular, I'm writing a project in which I need to distinguish between problems solvable in space $c\_1\cdot n$ and problems solvable in space $c\_2\cdot n$ for $c\_2\>c\_1$.

1. Which notation should I use? $SPACE(n)$ or $SPACE(O(n))$?
2. And how to distinguish between space $c\_1\cdot n$ and $c\_2\cdot n$ without confusion?

# Answer
> 14 votes
It depends on what definitions you use. Sipser \[1\] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of length $n$. Papadimitriou \[2\], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the work tapes.

However, the space analogue of the linear speedup theorem implies that, actually, these two definitions are equivalent, so you should pick whichever one is most convenient for you. Since you want to distinguish between machines that use up to $c\_1n$ work space and those that use up to $c\_2n$, the Papadimitriou-style definition seems more appropriate to your needs. Make sure you clearly and explicitly define $\mathrm{SPACE}(f(n))$ before using it. But do be aware that anything you can do with $n$ worktape cells using a $k$-symbol alphabet, I can do with $n/2$ cells by using an alphabet of size about $k^2$. Unless you're using a fixed tape alphabet, $\mathrm{SPACE}(c\_1n)$ and $\mathrm{SPACE}(c\_2n)$ are the same complexity class, even with the Papadimitriou-style definition.

---

**References**

1. Michael Sipser, *Introduction to the Theory of Computation*. Cengage Learning, 3rd edition, 2013. (Earlier editions almost certainly use the same definition.)
2. Christos H. Papadimitirou, *Computational Complexity*. Addison Wesley Longman, 1994.

**Acknowledgments**
Thanks to The Vee for pointing out an error in an earlier version of this answer.

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


# Question
Title: Do approximation results for CSPs hold even when domains are of finite but different size?
We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and Universal Algebra", a definition is given in Definition 2.1. Further, it is claimed this is a "standard formal definition of an instance of the CSP over a finite domain".

In particular, the definition says a CSP problem is a triple $(V,D,\mathcal{C})$, where $D$ is a finite domain. In other words, every variable takes a value from the same domain. Tracing back some earlier references from the survey, many papers define $D$ in the same way (i.e., it's the same for each variable).

I'm interested in a definition where each variable $x\_i$ has a finite domain $D\_i$ of size at most $k$, for some constant $k$. Surely when CSPs are defined like this, it's still NP-complete to decide whether there's a satisfying assingment, and NP-hard to maximize the number of constraints satisfied.

But: can one safely assume approximation results still hold for this definition? More generally, are there approxation results (or other algorithmic results) that break down when domains are of size at most $k$ instead of exactly the same for each variable? It feels strange the "standard formal definition" is not allowing this, so it makes me wonder if there's a reason for this limitation of generality.

# Answer
This is known as *multi-sorted* CSPs (a *sort* in logic is a type of variable). See An Algebraic Approach to Multi-sorted Constraints by Bulatov and Jeavons, for example.
> 1 votes

---
Tags: approximation, constraint-satisfaction
---


# Question
Title: Why is CAN protocol preferred to be used in automotive application?
Is it only because of the fact that it is asynchronous and can be used for long distance message transfer. An example of where other protocols will fail would help. Thanks.

# Answer
Historical reasons, for the most part. Automotive systems started using CAN because nothing else was good, and now they've all standardised on it. Having said that, CAN has one particular feature which makes it ideal for this class of applications.

CAN dates from around the same time as Ethernet (Ethernet was commercialised in 1980, CAN in 1983 IIRC), and solves the same problem: attaching a moderate number of devices to a single bus.

When two Ethernet devices want to transmit at the same time, they both back off for a random amount of time, and the time increases as the number of tries increases. Neither sender proceeds immediately. This is the famous CSMA/CD protocol.

As any network engineer knows, this has a bunch of unfortunate implications, one of which is that the effective maximum capacity of a shared Ethernet wire is around 30% of the theoretical capacity. (Obviously point-to-point full duplex Ethernet connections can get much closer, because there is no contention.)

With CAN, messages have a priority, and the priority is in the frame header. If two devices want to transmit at the same time, only the lower-priority message backs off. Not only does this increase the practical capacity of the bus, the designer gets something that's much closer to a real-time guarantee. That is valuable in the world of metal, speed, and danger.

The difference doesn't matter so much these days, since networks are much faster than they were in 1983, so even 30% utilisation is still a lot of bandwidth. But still, a near-guarantee is a near-guarantee.
> 4 votes

# Answer
A few reasons :

* CAN was developed by BOSCH, which have a lot of influence in automotive equipment (engine control, braking, body, gearbox control...). BOSCH ensured that CAN killed competitors like the VAN protocol. (CAN was patented, and BOSCH sells CAN controller IPs)
* CAN is much cheaper than Ethernet.
* There were no suitable industrial bus at the time, using physical layers like RS-485 : Modbus, Profibus...

Now several other busses are used in automotive applications :

* LIN : Slower, cheaper than CAN. For very simple devices.
* FlexRay : Faster than CAN, deterministic. For advanced real time functions like dynamic suspension.
* Ethernet : The future, particularly in a 2 wires implementation. For a few advanced applications, including steer-by-wire, video...

Anyway, CAN is here to stay as it offer a good balance between performance and cost of implementation.
> 5 votes

# Answer
I think below few are the valid reason for prefer CAN wrt other protocol.

1. Cost - It has very low cost to implement 1 pair of twisted pair is fair enough.
2. Asynchronous - Since its asynchronous communication.
3. Arbitration/Collision avoidance - Having super control on arbitration and collision avoidance.
> 0 votes

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


title: Processor Scheduling (SJF / FCFS)

text:
# Question
Title: Processor Scheduling (SJF / FCFS)
So I know that scheduling has been covered in other articles, but because my provided values are different and decimals are used, I am having difficulty wrapping my head around it. I have reviewed all of the other posts already but would like clarification on my specific values if possible.

1. What is the average turnaround time for these processes with the FCFS scheduling algorithm?
2. What is the average turnaround time for these processes with the nonpreemptive SJF scheduling algorithm?
3. The SJF algorithm is supposed to improve performance, but notice that we chose to run process $P\_1$ at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 2 units and then nonpreemptive SJF scheduling is used. Remember that processes $P\_1$ and $P\_2$ are waiting during this idle time, so their waiting time may increase.
4. What is the average turnaround time for these processes with the preemptive SJF scheduling algorithm?

The values (including a make-shift Gantt chart) are as follows:

**1. FCFS**

\begin{array} {|r|r|} \hline P\_1 &P\_2 &P\_3 \\ \hline 0-5 &5-8 &8-9 \\ \hline \end{array}

Completion times: $P\_1=5, P\_2=8,P\_3=9$
Turnaround Time = 5.866667

**2. Non-PreEmptive SJF**

\begin{array} {|r|r|} \hline P\_1 &P\_3 &P\_2 \\ \hline 0-5 &5-6 &6-9 \\ \hline \end{array}

Completion times: $P\_1=5, P\_2=9, P\_3=6$
Tunaround Time = 5.2

**3. Future-Knowledge (Non-PreEmptive SJF with Idle time)**

\begin{array} {|r|r|} \hline \- &P\_2 &P\_3 &P\_1 \\ \hline 0-2 &2-5 &5-6 &6-11 \\ \hline \end{array}

Completion times: $P\_1=11,P\_2=5,P\_3=6$
Turnaround Time = 6.2

**4. PreEmptive SJF (SRTF)**

\begin{array} {|r|r|} \hline P\_1 &P\_2 &P\_2 &P\_3 &P\_1 \\ \hline 0-0.4 &0.4-3 &3-3.4 &3.4-4.4 &4.4-9 \\ \hline \end{array}

Completion times: $P\_1=9,P\_2=4.4,P\_3=3.4$
Turnaround Time = 4.133333333

Hopefully these values are correct. If they are not, could you please explain the process so that I can understand how to properly calculate it myself? Thank you in advance for any assistance!

# Answer
**1. FCFS**

Turnaround Time T T = 5.866 is correct.

**2. Non-PreEmptive SJF**

T T = 5.2 is correct.

**3. Future-Knowledge (Non-PreEmptive SJF with Idle time)**

T T = 6.2, I'm not sure about this.

We never get a future knowledge of how big the next process will be.

**4. PreEmptive SJF (SRTF)**

Here, your scheduling is wrong.

$P\_2$ arrives at time 1.4, how can you schedule it at time 0.4?

Refer below scheduling:

\begin{array} {|r|r|} \hline P\_1 &P\_2 &P\_3 &P\_2 &P\_1 \\ \hline 0-1.4 &1.4-3 &3-4 &4-5.4 &5.4-9 \\ \hline \end{array}

T T ($P\_1$) = 9 - 0=9
T T ($P\_1$) = 5.4 - 1.4=4
T T ($P\_1$) = 4 - 3 =1
Avg T T = 4.6

Dont you see the improved TT of one over other.

**FCFS = 5.8 \> NON-PRE SJF = 5.2 \> PRE SJF =4.6**
> 1 votes

---
Tags: process-scheduling
---


# Question
Title: Given 2 sets of n points: minimize sum of traveled distances
I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum\_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean distance.

I am aware that this transportation problem is a special case of the earth mover distance problem, but since its unweighted (and over points) I am wondering if there is a more efficient algorithm than the cubic time hungarian method for it?

# Answer
> 4 votes
As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances.

There have been several improvements since the Hungarian Algorithm, at least in terms of asymptotic bounds. Depending on the exact size of the graph, any of several algorithms may be the best. A table in the paper by Cohen, et al gives details. Edmonds and Karp's algorithm is $O(nm + n^2 log n)$, and is still the best bound that doesn't depend on the maximum weight in the graph. Cohen's algorithm appears to be the best for sparse graphs, which is not your situation. I think the best for your dense graph would be Sankowski's $\tilde{O} (W n^\omega)$, since it doesn't depend on $m$.

I do not know if there are ways to exploit this problem's specific weight structure (Euclidean distances) for further improvements.

Sources:

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{(10/7)} log W)$ Time. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
https://arxiv.org/abs/1605.01717v3 (preprint)

J. Edmonds and R.M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19(2):248–264, 1972.

Piotr Sankowski. Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, chapter Weighted Bipartite Matching in Matrix Multiplication Time, pages 274–285. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
http://link.springer.com/chapter/10.1007%2F11786986\_25

---
Tags: algorithms, optimization, computational-geometry, linear-programming, bipartite-matching
---


# Question
Title: What is the meaning and significance of a Turing machine taking a description of itself as input?
Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on input $\langle M, \langle M\rangle\rangle$.

My question is: What is the significance of giving a description of Turing machine as input as in $\langle M,\langle M\rangle\rangle$?

What is the logical reason behind giving the description of a Turing machine as input to $D$?

# Answer
> 3 votes
We can then think of the machine description $\langle M \rangle$ as the source code of $M$. If we do this, then the Halting Problem is really concerned with the decision problem

*Given the source code of a program and an input string, will the program halt if fed the string as input?*

There are many programs that take program code as input. A compiler is a well-known example; a specialized text editor is another.

If the Halting Problem were decidable, there would be a predictor program that could correctly predict the behaviour of *any* given program, given its source code. We could then modify the predictor program such that it would always behave differently from the program that it was analyzing. But then we could of course feed this modified predictor program its own source code and predict how it would react. And the conclusion would be that its behaviour would be different from its own behaviour -- and this is of course a contradiction.

# Answer
> 1 votes
One goal is to be able to process some machines by other machines, like one program processes another program. One doctor may operate on another human. The point of doing this in Turing Halting is to prove that there is no halting machine. The point of feeding a machine to a Halting machine is to check if your machine ever (always?) stops. Turing made a mental experiment where assuming that Halting machine exists, demonstrates that this leads to a contradiction and, thus, no Halting machine may exist.

You see, there can be many reasons you may want submit one machine as input to another. Turing argued that whatever what can he computed can be computed by Turing Machines and, checking the limits of Turing machines, he checked the limits of computation -- what can be ever computed and what cannot. And feeding one machine to the other plays important role in the evaluation of what is computable.

# Answer
> 0 votes
Some intuition can be found by considering the case of universal turing machine. This machine can simulate another turing machine for some arbitrary input. For this the universal turing machine takes as an input : The encoding of the turing machine and the input which has to be simulated on the machine which is fed as an input. The universal turing machine can be used to prove the halting problem.

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


# Question
Title: Why must uncommitted transactions be undone in backwards order?
I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards.

Is there any reason for doing this backwards? Can anyone give a simple example of a log where forward undos would give wrong results?

# Answer
> 36 votes
Original transactions:

1. Insert record $r$.
2. Update some field $f$ of $r$.

Forward undo:

1. Delete record $r$.
2. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.

# Answer
> 12 votes
To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist.

However, consider a situation where deletion of a record actually will fail:

1. Insert Order O.
2. Insert Orderline L.

Let's assume, not unrealistically, that every OrderLine *must* be related to an Order.

Now rolling back the transaction starting with deleting the Order will fail because that would violate our business rule.

So after

1. Delete Order O. (FAIL)
2. Delete Ordeline L. (SUCCESS)

We may end up with an existing Order (without an Orderline).

Of course, in this case we could use a cascading delete, but that would mean step 2 would fail (without impact). Worse, it may be unwanted behaviour to implement cascading deletes on orders.

# Answer
> 7 votes
Let's go by analogy: say you're going out for dinner.

1. Put socks on.
2. Put shoes on.
3. Stand up.
4. Walk to door.

Then you get a phone call. Dinner plans cancelled.

1. Take socks off.
2. Take shoes off.
3. Sit down.
4. Walk away from door.

Something goes wrong in there. You may trip and hurt yourself. Or more likely, you'll realize that some actions can't be undone until later actions are undone first.

Undoing the last thing you were doing gets you back to where you were when the next to last step occurred. Then you undo that step and repeat, moving back until nothing is left. On the other hand reversing the first step may not be possible given the states following the later steps.

mathematically speaking: the actions may not commute, so whenever it matters which step you do first or second, the order in which you undo steps will matter.

# Answer
> 4 votes
This is right because transactions are built on top of each other and the outcome of a transaction is very much dependent on the situation before it was committed.

Let's look at financial transactions:

(at the beginning, before transactions `a` owes me 100 USD)

1. `a` owes me 100 USD (now total debt 200)
2. `a` receives 10% discount on what he owes me. (now total debt 180)

Let's say I want to cancel the two transactions.

If we cancel the first first, we will end up with:

1. lower debt 100 (now have debt 80)
2. cancel 10% discount (now have debt 80/0.9 = 88)

This is wrong, we need to get back to debt of 100. That will be right if we cancel the transactions in reverse order.

1. cancel discount - now debt is 200
2. lower 100 debt - now debt is 100

# Answer
> 2 votes
Assume there is a table T with one column only.

Assume that the "undo log" is a database file containing uncommitted transactions, and that the "redo log" is a database file containing both uncommitted and committed transactions that have not been yet applied to the datafiles.

`At 8:00 A.M., Transaction 100 inserts rows with values 101, 102 and 103
 into table T.
At 8:10 A.M., Transaction 100 is committed and the commit for
 transaction 100 completes.
At 8:15 A.M., Transaction 200 updates row 101 to 201, 102 to 202
 and 103 to 203.
At 8:20 A.M., Transaction 200 has not been committed and remains
 in the undo log of the database.
At 8:25 A.M., Transaction 300 increments each row by 50,
 changing row 201 to 251, 202 to 252, and 203 to 253.
At 8:30 A.M., Transaction 300 has not been committed and remains
 in the undo log of the database.
At 8:35 A.M., The instance providing access to the database crashes.`

`At 8:40 A.M., The instance is restarted, and the database files are
 opened as the instance is started:

```
              The committed values in T are still 101, 102 and 103.

              Since 201, 202, and 203, and 251, 252 and 253
              are not committed, if they are written into the "redo
              log" of the database, there is a need to "roll back"
              the transactions AFTER the "redo log" is applied.

              Since 201, 202, and 203, and 251, 252 and 253
              are not committed, they are in the "undo log"
              of the database.

              The undo log of the database is used BOTH to (1) roll
              back a transaction that is deliberately rolled
              back in the memory structure of the database instance,
              and also (2) during the instance recovery at 8:40 A.M.

```

At 8:41 A.M., The redo log has been applied, and the T table
 contains values 251, 252 and 253 in the instance memory.

```
              The undo log has not yet been applied.

````

`At 8:42 A.M., The undo log is applied in the reverse order:
 Uncommitted transaction 300 is undone, and
 Uncommitted transaction 200 is undone.`

**Why are BOTH committed and uncommitted transactions written to the redo log file?** The reason for this is to provide point-in-time recovery.

**This means that the contents of the "redo log" file are NOT transaction-consistent.** For this reason, whenever the redo log is used to apply committed transactions to the data files, the "undo log" MUST ALSO be used to roll back uncommitted transactions.

**Why are the transactions in the "undo log" rolled back in the reverse order?** The transaction 300 has added 50 to the existing value of each column of each row. Therefore, if transaction 200 is rolled back first, the values will change from 251, 252 and 253 to 201, 202 and 203. If transaction 300 were then rolled back last, the values would be 151, 152 and 153 - that do not match the original committed values.

REFERENCES:

https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11\_QUESTION\_ID:1670195800346464273

# Answer
> 0 votes
It's not inherently true. Rollback may simply re-apply the blocks that were cached in the undo log so that the final state is the same as the initial state. Because the log was written in forwards order I made my rollback also apply in forwards order. The order didn't matter whatsoever because rollback would retry until the log file was marked as settled.

---
Tags: concurrency, databases
---


title: Derivative for x-direction for image

text:
# Question
Title: Derivative for x-direction for image
I want to ask, consider we want to compute the slope of x-direction of the following step

.

The slope for it would be

$m =\frac{0}{m\_2 - m\_1} =\frac{0}{5 - 2}$ which is 0.

But the derivate for image in x-direction computed with (something like, some symbols aren't existed in my phone so lets just say $\frac{df}{dx}$)

$\frac{df}{dx} = f(x+1) - f(x)$

It's computed under the consideration of next pixel $f(x+1)$ minus current pixel $f(x)$.

Is there any interpretation that I'm missing, shouldn't it be 0, in both cases?

# Answer
> 2 votes
From my understanding, you are asking about computing the derivative, at some pixel $(x,y)$, with respect to the $x$ direction. We can approximate a derivative of some function $f(x,y)$ along the $x$ direction using the following Finite Difference formula:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+h,y) - f(x,y)}{h} $$

for some $h \neq 0$, usually using $h \ll 1$ if possible. For an image, the best you can do with this formula is the following:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+1,y) - f(x,y)}{1} = f(x+1,y) - f(x,y) $$

This is because $f(x,y)$, the pixel color values at $(x,y)$, is a value of $1$ away from the nearest neighboring pixels in both the $x$ and $y$ direction.

---
Tags: image-processing, mathematical-analysis
---


# Question
Title: Why does russian peasant multiplication work?
can someone provide a proof with induction on why the Russian peasant multiplication work ?

if you don't know what that is , here is the algorithm :

```
                    P(2·a,⌊b/2⌋)   : b>1 and b is even number
P(a,b):=            P(2·a,⌊b/2⌋)+a : b>1 and b is odd number
                    a              :b=1

```

# Answer
Let $ a \cdot b = p \cdot q + r $.

What's the base case for the induction? $p = a, q = b, r = 0$.

Inductive step: $ a \cdot b = p \cdot q + r$ holds, then $ a \cdot b = p' \cdot q' + r' $ in the next iteration.

**Case 1:** $p$ is odd. If $p$ is odd, then $p' = \frac{p-1}{2}, q' = 2q, r' = r + q$

$$ p' \cdot q' + r' = \frac{p - 1}{2} \cdot 2q + r + q = pq - q + q + r = pq + r = a \cdot b$$

**Case 2:** $p$ is even. Then $p' = \frac{p}{2}, q' = 2q, r' = r$

That also implies $p' \cdot q' + r' = p \cdot q + r = a\cdot b$
> 0 votes

---
Tags: proof-techniques, mathematical-analysis
---


# Question
Title: What is the time complexity of an algorithm that calls a polynomial time algorithm?
I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of elements:

```
Foo(A)
for each element a in A:
    for each element b in A-a:
        Polynomial-Time-Algorithm-Bar(A, a, b)

```

If **n** is the size of A,

1) Am I right in understanding that `Foo(A)` is also a polynomial time algorithm , because the function `Polynomial-Time-Algorithm-Bar` is called `(n-1)*n` times ?

2) When would an algorithm making calls to another polynomial time algorithm become exponential. I understand that if it has a running time of O(n^m) and m is variable and n is constant, then it would be exponential. Can you give me an example of such a case in the above example?

# Answer
I assume $n$ is the number of entries in array/set `A`.

1. Yes, since polynomials are closed against multiplication; specifically, $n(n-1) \cdot p(n)$ is always polynomially bounded as long as $p(n)$ is polynomially bounded.
2. As a consequence, the only way to achieve exponential running-time by calling a polynomial-time algorithm with parts of the original input is to call it exponentially often.

**Example:**

```
Foo(A)
  if |A| >= 2
    a = A[0]
    b = A[1]
    Polynomial-Time-Algorithm-Bar(A, a, b)
    Foo(A - a)
    Foo(A - b)

```

The number of calls to `PTA-Bar` is given by

$\qquad\begin{align\*} C(0) &= 0,\\ C(1) &= 0,\\ C(n) &= 2C(n-1) + 1, \qquad n \geq 2, \end{align\*}$

which solves to $C(n) = 2^{n-1} - 1$ for $n \geq 1$. Ergo, the running time of `Foo` is in $\Omega\bigl( 2^n \cdot p(n) \bigr)$ if `PTA-Bar` takes time $p(n)$.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis
---


title: What are the limitations of RNNs?

text:
# Question
Title: What are the limitations of RNNs?
For a school project, I'm planning to compare Spiking Neural Networks (SNNs) and Deep Learning recurrent neural networks, such as Long Short Term Memory (LSTMs) networks in learning a time-series. I would like to show some case where SNNs surpass LSTMs. Consequently, what are the limitations of LSTMs? Are they robust to noise? Do they require a lot of training data?

# Answer
I finally finished the project. Given really short signals and a really small training set, SNNs (I used Echo State Machines and a neural form of SVM) vastly out-performed Deep Learning recurrent neural networks. However, this may be mostly because I'm really bad at training Deep Learning networks.

Specifically, SNNs performed better at classification of various signals I created. Given the following signals:

The various approaches had the following accuracy, where RC = Echo State Machine, FC-SVM = Frequency Component SVM and vRNN = Vanilla Deep Learning Recurrent Neural Network:

SNNs were also more robust to noise:

For more information, including how I desperately tried to improve the Deep Learning classification approach performance, check out my repository and the report I wrote which is where all the figures came from.

**Update:** After spending some time away from this project, I think one of the reasons that RNNs do horribly at this project is that they're bad at dealing with really long signals. Had I chunked the signals together with some sort of smoothing as preprocessing, they probably would have performed better.
> 5 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Understanding the Diameter Constrained MST Problem
I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand it, we have a undirected connected graph $G=(V,E)$, a cost $c$ for every edge $e(i,j) \in E$ and a value $d$ we want to find an minimum spanning tree whose diameter is at most $d$. This paper say's that the diameter is of a tree is equal to the number of edges in the longest path between any pair of its nodes. Does this mean that the cost or weight of the edges are not considered when computing the diameter, in other words the weights do not add any meaning for the diameter? To compute the diameter we treat every edge as constant $1$? But I would assume the weights have meaning for the MST? Also, what are we minimizing here, the spanning tree or the diameter, because I don't think it can be both?

Clearly, I am misunderstanding something here. Could someone explain this problem in more detail? I've been cracking my head with this problem for some days now.

For example if we find an MST with $k$ diameter less than $d$ , and a spanning tree with a lower diameter than k but it's total weight is greater then the MST we found prior, the correct solution would be the MST because it is most minimum and the diameter constraint is satisfied, and does not need to be the most minimum diameter? or which is the correct solution and why?

# Answer
The **diameter** of a graph is the longest shortest-path distance over all pairs of vertices. This distance can be measured in terms of edge weights or in terms of number of edges (which is known as geodesic distance). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance.

When you want to obtain a **Minimum Spanning Tree** (MST), you focus on edge weights because all spanning trees have the same number of edges: $|V|-1$.

Aiming for an MST that is constrained by a maximum diameter is perfectly possible. The authors of the paper are not setting two conflicting optimization goals, but, rather, just adding an additional constraint to the MST problem. Adding this contraint, however, turns the MST problem into an NP-Hard problem (even though computing the diameter of a graph and obtaining an MST, separately, are problems that can be solved in polynomial time).

To gain further insight into the notion of diameter (in the context of MSTs), consider the following example:

The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total weight (i.e., the sum of the weights of its edges) is 7 and its diameter is 5 (because the vertices that are farthest from each other are 5 edges apart). If we add the constraint that the diameter must be at most 2 (that is, $d=2)$, then the diameter-constrained MST is the tree on the right. Its total cost is 12 (higher than the tree on the left), but it is the only spanning tree whose diameter (ignoring weights) is $\leq 2$.
> 3 votes

---
Tags: graphs, optimization, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Architecture of a chatbot - how to organize and fetch possibilities?
I'm building a chatbot that would respond to text messages.

Let's say that my chatbot works for customers of an internet provider and it can respond to the following things:

* Problems:
    + About payment;
    + About internet connection.
* General requests:
    + Change user's account e-mail;
    + Call for technical assistance.

My question is: what's the data structure that I could use to organize this tree?

# Answer
When Building AI and ML for you Chatbot, you basically have 2 options:

1. You can use a 3rd party tool which will take care of the AI/Conversational part of the Chatbot.
2. You can make your own using Machine Learning.Overwhelming, but quite a few developers are choosing to go this route and many companies are trying to democratize Machine Learning.

You can build your own NLP(Natural Language Processing) by using Machine Learning. One of the first things to consider will be the type of model you want to build.

**Using an NLP/NLU Platforms:** Natural Language Processing (NLP) and Natural Language Understanding (NLU) platforms attempt to solve the problem by parsing language into entities, intents and a few other categories. Different NLP platforms may have different names however the essence is moreso the same.

Categories:

* **Agents** correspond to applications. Once you train and test an agent, you can integrate it with your app or device.
* **Entities**: represent concepts that are often specific to a domain as a way of mapping natural language phrases to canonical phrases that capture their meaning.
* **Intents** represent a mapping between what a user says and what action should be taken by your software.
* **Actions** correspond to the steps your application will take when specific intents are triggered by user inputs. An action may have parameters for specifying detailed information about it.
* **Contexts** are strings that represent the current context of the user expression. This is useful for differentiating phrases which might be vague and have different meaning depending on what was spoken previously.

NLP Platforms:

Reference :
> 1 votes

---
Tags: machine-learning, neural-networks, neural-computing
---


# Question
Title: How to apply the pumping lemma for CFGs to languages that contain the empty string
The pumping lemma states that if we can split a string w (taken from a context-free language L) as uvxyz with conditions |vy|\>=1 |vxy|\<=p |w|\>=p for some p then $uv^ixy^iz$ is in L for any i.

However, some context-free languages include the empty string, which has length 0. How can we possibly split the empty string to satisfy the condition |vy|\>=1?

For instance, the following language $\\{0^n1^n0^n1^n|n\>=0 \\} $ contains the empty string but is not context-free, so how can I ensure a string taken from it can we split as uvxyz with |vy|\>=1?

Thanks!

# Answer
> 2 votes
The pumping lemma requires the word $w$ you start with to be large enough — larger than the pumping lemma constant $p$.

However, this doesn't really answer your question, which is how to ensure that the string given to the pumping lemma is not empty. Here you are very lucky — you are the one choosing the string! The pumping lemma only states that whatever string $w$ you choose from the language (as long as it is long enough), it can be decomposed as $w = uvxyz$ so that $uv^ixy^iz$ is in the language for all $i \geq 0$, $vy \neq \epsilon$, and $|vxy| \leq p$.

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


title: Automata for empty language

text:
# Question
Title: Automata for empty language
I am trying to understand how many states should be there in a Finite Automata which does not accept anything.

I thought it to be containing only one non-final state, the starting state, with all transitions going to itself.

But one of my teachers mentioned that the set of final states cannot be empty. Does that mean there will be two states states, one start state and one final state, with no transition between the two?

# Answer
> 7 votes
The standard definition of DFA (as well as NFA) allows the set of accepting states to be empty. Indeed, otherwise the Myhill–Nerode theorem would be false. The theorem states that the number of states in a minimal DFA for $L$ equals the number of equivalence classes in the Myhill–Nerode relation for $L$. When $L = \emptyset$, this relation contains one equivalence class (consisting of all strings), and so there should be a DFA for $L$ having a single state.

Of course, you can define DFAs in any way you like, and in particular, your teacher's definition still results in the same class of regular languages. Nevertheless, the standard definition is better, for the reason stated above.

# Answer
> 3 votes
the resulting automaton consists of one state which transitions to itself on every symbol in the input alphabet. Note that is state is non accepting. An Automaton should always have an initial state but the set of final states could be empty.

# Answer
> 3 votes
The finite automaton accepting nothing will contain transitions on all input symbols to itself only. Thus atleast $1$ state is necessarily required.

> A language accepting nothing can be considered as **complement of language accepting everything**. We know that language accepting everything has only one state with that state being initial and final state.

# Answer
> 0 votes
Maybe the solution your teacher proposed is an automaton with 2 states 1 starting and 1 final, but with **0 transitions**, so technically the final transition does not accept anything.

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


# Question
Title: What are the design issue with today's micro processor
I'm just getting started with cs. In school I heard about that modern micro processor are not perfect. So what are the issues? Are does problems related to energy(power draw)/ time /speed(clock speed)? Or is the design faulty? So if you could design the perfect cpu what would it look like?

# Answer
> 5 votes
There are inherent tradeoffs in targeting a given use. An implementation optimized for one workload, power budget, and cost (at a particular volume of sales) will necessarily be less than optimal for some other use.

Binary compatibility places another constraint on optimization. An ISA which is a good/easy compiler target and which is not strongly tied to a particular set of implementation techniques and technologies will be less than optimal for a given implementation technology (i.e., some optimizations are hindered by the abstraction presented in the ISA) and will sacrifice some benefits in performance, energy-efficiency, etc. for these other goals.

(Redesigning the ISA for every implementation is not a solution, even when using an intermediate-level software distribution format to provide compatibility. The cost and delay of ISA design (including developing an optimizing compiler for the software distribution format) constrains how extensively changes can be made to optimize for particular targets. Even microarchitectures are typically extensively reused because of development costs, including time to market and risk.)

Time to market also constrains optimization. High performance designs targeting new manufacturing processes begin work years before the process characteristics are defined. (This also applies to application targets. Algorithms and use patterns change.) There is also a limited amount of design effort that can be reasonably applied. Even if the value of optimizations could justify the development costs, worse but available products can establish market momentum.

---
Tags: computer-architecture, cpu
---


# Question
Title: Proving a language is not context free using the Pumping Lemma
To prove that $L=\\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|\leq p, |w|\geq p, |yv|\>0, xy^iuv^iz \in L \forall i\>0$

Take $i=0$ then consider 3 cases:

*Case 1*:$yuv$ is only a substring of $0s$.

Then $w'=0^a1^{7p} \text{ with } 21p\>a\geq 20p$. In this case, $a$ is not divided by $7p$

*Case 2*:$yuv$ is only a substring of $1s$.

Then $w'=0^{21p}1^{b} \text{ with } 7p\>b\geq 6p$. In this case, $21p$ is not divided by $b$

*Case 3*:$yuv$ contains both $0s$ and $1s$.

Now I am quite sure this also works when $yuv$ includes both $1s$ and $0s$. We get $w'=0^{21p-a}1^{7p-b} \text{ with }p\>a\>0, p\>b\>0 \text{ and } p\geq a+b$.

I just can't figure out how to formally state how a contradiction arises from case 3. How can I prove that case 3 also fails? Thanks!

# Answer
You can try to take a different value for $i$ in that case. It is not necessary to fix one $i$, but the $i$ chosen may depend on the chosen partition $xyuvz$. Will $7p+ib$ always divide $21p+ia$?
> 1 votes

---
Tags: context-free, proof-techniques, pumping-lemma
---


# Question
Title: Min-cut in graph with demands/lower bounds
This week I read something about network flow from Algorithm Design. But I am confused about some concepts.

We say, if a graph G contains some nodes with demands, positive or negative, how to define the min cut for these graphs? If we still use the definition for simple graph, the value of max flow is not equal to the capacity of min cut. Or is it totally meaningless to talk about min-cut in a network with demands on some nodes.

Another thing is how to define the capacity of a min-cut for graph with lower bound on its edges. Still the sum of capacities of edges out of starting set? Or say, now we have a lower bound for this cut which is the sum of lower bounds of edges out of starting set.

# Answer
Max flow and min cut are dual problems, in a technical sense: there are linear programming formulations of both, and these linear programs are dual to each other. This is explained in the Wikipedia article on the max-flow min-cut theorem.

Given a variant of the max flow problem, you can find the corresponding min cut problem by writing the linear programming formulation of the max flow problem, and dualizing it. I'll let you figure out what you get in your cases.
> 1 votes

---
Tags: network-flow, minimum-cuts
---


# Question
Title: Sum of divisors summatory function with Erathosthenes' sieve
I ran across the following problem from an online problem bank: there are up to $~10^5~$ queries each of which asks to compute the sum $$\sum\_{k = L}^{R} \sigma(k)$$ where $\sigma(k)$ is the sum of divisors of $k$. It is given that $1 \leq L \leq R \leq 5\cdot 10^6$.

My solution (described below) is based on Erathosthenes's sieve. I've implemented it in C++ and it works in about $0.9$ seconds on average which is too slow. I know that this problem can be solved at least twice faster but don't know how.

So here is my solution (arrays are 0-based):

```
M = 5 * 1e6
M = array of zeroes of size M + 1
A[1] = 1
for (k = 2; k <= M; k += 1)
    for (j = k; j <= M; j += k)
        A[j] += k

```

I precalculate $\sigma(k)$ via Erathosthenes' sieve for each $k$ below max possible value. When the main loop reaches $k$, $A\[k\]$ keeps the value of $\sigma(k)$. Then I reassign $A\[k\]$ to be $\sum\_{i=1}^{k}\sigma(i)$. After such preprocessing all queries can be computed in $O(1)$ time by computing $A\[R\] - A\[L-1\]$.

How can I make it faster? I know two formulas: $$ (a) ~~~~~ \sigma(p\_{1}^{a\_1} \cdots p\_{s}^{a\_s}) = \prod\_{i=1}^{s} \frac{p\_{i}^{a\_i + 1} - 1}{p\_{i} - 1}$$ $$ (b) ~~~~~ \sum\_{k=1}^{n} \sigma(k) = \sum\_{k=1}^{n} k \left \lfloor \frac{n}{k} \right \rfloor$$

The problem with (a) is that computing it (at least in my implementation) is slower than given above. The problem with (b) is that I don't understand how to compute prefix sum with such approach faster than in $O(n^2)$ time.

Is there a more efficient algorithm for this problem?

(The problem bank credits the original source of the problem as 2012 Kharkiv, Winter School, Day of Sergey Kopelovich, Problem H.)

# Answer
This isn't really computer science...

You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a table s where you store the sum of divisors for all 1 ≤ j ≤ k, for k = 1 to M. That's easy, $s\_0 = 0$, $s\_{k+1} = s\_k + d\_{k+1}$. And then f (L, R) = $s\_R - s\_{L-1}$.

The first table is the problem. You handle this in $O (n \log n)$. And you only need a factor two, you say...

You will have an array d with 5 million entries, likely 4 byte per entry = 20 Megabyte. On a typical processor that you would have in your home computer, 20 Megabyte doesn't fit into any cache. And your code does lots of accesses to elements of that array in quasi random order. For each potential divisor k, you visit all numbers that are divisible by k, and increase the sum of divisors by k.

Let's do that with fewer visits: When you visit j which is divisible by k, add the two divisors k and j/k. But when you do that, start with $j = k^2$, adding only k (because k = j / k, and you don't want to count the divisor twice), and then add k and j / k for further j. You don't need to divide, because j / k will equal k+1, k+2, k+3 etc. We initialise the array for the case k = 1, that is setting A \[j\] = 1 + j / 1 for j ≥ 2.

```
A [1] = 1
for (j = 2; j ≤ M; j += 1)
    A [j] = 1 + j

for (k = 2; k*k ≤ M; k += 1)
    j = k*k
    A [j] += k
    j += k
    s = k + (k + 1)
    while j ≤ M
        A [j] += s
        j += k
        s += 1 // s equals k + j / k

```

You don't save operations. However, you are now accessing the array A in a much more regular pattern, so this will save you time because access to the items will be faster. j will be smaller, making the number of iterations for each j larger, which will make branch prediction work better.

For more improvement, you would find out how many array items fit into the processor cache in your computer, then perform the whole code for subranges of the array only (for example changing only A \[0\] to A \[99999\], then changing A \[100000\] to A \[199999\], and so on). That way, most memory accesses will only access cache memory, which might be substantially faster.

You are doing N lookups in a table of size M. If M is substantially larger than N, then you should probably think about approaches that don't build this table, and that may be a lot slower per lookup, but faster overall due to the small number of lookups. Even in the case here where N ≤ 100,000 and M = 5,000,000, you might for example not count divisors 1, 2, 3, 4, j/1, j/2, j/3, j/4 in the table (which makes it a bit faster to build), and handle that during the lookup.

Or you could add the sum of the divisors for odd numbers only, then calculate the sum of divisors for even numbers (if the sum of the divisors of an odd k is s, then the sum for 2k is 3s, for 4k it is 7s, for 8k it is 15s etc), which would save almost a factor 2.

PS. I measured it... making the algorithm for counting all sums of divisors more cache friendly by adding both j and k/j doubled the speed. Calculating the sum of divisors for odd k first, then calculating even k from the odd values, makes it a total of 7 times faster. Obviously all just constant factors.
> 6 votes

# Answer
So let me rearrange your problem a bit: using prime sieve should be helpful, but normal Erathostenes sieve is not good enough.

What you need is prime sieve working in linear time, hitting every number just once.
One description of linear time prime sieve shows how to cross every number just once.
What are benefits? Well, if instead of crossing numbers we insert the sum of divisors there, we have fast algorithm placing divisors (please remember about $1$ as a divisor).

Also there is one additional step, prime numbers are not calculated, so encountering one we should write it's divisor as this number + 1.

Next there should be cummulative pass (going through array adding last item to make it sum of all previous divisors).

This way every number should be written exactly once, so this is for sure better than original attempt.

What else could be done?
Since there are less queries than numbers, I thought maybe we can ommit the calculation of the whole array?

This can be done in at least two ways: obvious one is to make partial (or even whole) array offline (not during time measurement), making program bigger, but there was no limit of size.

Another one is to calculate whole array of cumulative divisors, and then fit some functions retreiving results from indices.

The functions itself might be a bit complicated or to make thinks easier we can divide it into ranges - making them shorter and easier to find.
The huge complexity behind that is done offline, and during runtime only queries time matters, since there is no sieve at all.
> 3 votes

# Answer
You may store precalculated results for intervals {L=1, R = k\*10^4} and brute-force only about 2\*10^4 numbers
> -1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: The throughput of the ALOHA protocol if the Binomial distribution was used
In all the examples of ALOHA I've seen, the Poisson distribution is used. Theoretically, how could the throughput be calculated if a Binomial distribution was used instead?

For example, in the case that the offered load follows a Binomial distribution with probability $p$, I know that the probability of $k$ attempts within $t$ time slots is as follows:

$$\Pr\big\[k \text{ attempts within $t$ time slots}\big\] = \binom{t}{k}p^k(1-p)^{t-k}\\,.$$

I know that the throughput, $S$ is equivalent to $G$ (average offered load) multiplied by the probability of success:

$$S = G\cdot\Pr\big\[\text{successful}\big\]\\,,$$

but what would this be in the case that a binomial distribution is used?

# Answer
> 2 votes
I don't think it makes sense to use the binomial distribution.

The point of using the Poisson distribution is that network nodes are assumed to want to transmit with an exponential distribution at some rate. This is a reasonable model for objects that randomly emit stuff – for example radioactive decays follow this distribution. Given a bunch of things emitting stuff at intervals sampled from the exponential distribution, the number of emissions in some time interval is given by a Poisson distribution. In other words, the Poisson distribution arises naturally from a model of the individual nodes. A particular property of the Poisson distribution is that it has infinite support: it assigns a probability to the event that you have a million transmission attempts within ten time slots. Another feature of using exponential distributions is that it allows one to model the back-off time after a collision.

In contrast, using a binomial distribution doesn't come from any natural model of the individual nodes' behaviour. It only allows you to model "were there at least $n$ transmissions attempts during this time slot?" for some $n$ of your choosing. It doesn't seem able to deal with back-off and it doesn't seem able to deal with multiple collisions within a single time slot.

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


# Question
Title: How to calculate virtual address space from page size, virtual address size and page table entry size?
I try to solve an exercise, unfortunately without any success yet.

From the following given information, the virtual address space should be calculated:

* Page size is 16 KB
* Logical address size is 47 bit
* 3 levels of page tables; all have the same size
* Page table entry size is 8 byte

My idea is to find out how many pages can be addressed. The page count should lead then to the size of the virtual address space, right?

> Virtual address space = page size * page count

As far as I understand is the page count defined by the logical address size. The logical address is split up in 3 levels of page tables plus the offset. Due the page table entry size is 8 byte (2^6 = 64 bit), 6 bits of the logical address are used for each stage to address it. The offset will have the size of 30 bits.

Each page stage can address 64 bit plus the 30 bits offset. So does this result in the page count?

> Page count = 64 * 3 + 30 = 222

With the page size and the page count I get the virtual address space of `3552 KB`.

I think this is wrong. It should be much larger. What is not correct? Any help is appreciated!

# Answer
> 3 votes
Since Logical address size is 47 bit, that means logical address space is 2^47 bytes ( assuming system is byte addressable ).

Otherwise in general if the logical address is not given then also it can be found.

```
Page size is 16 KB
Logical address size is 47 bit
3 levels of page tables; all have the same size
Page table entry size is 8 byte

```

From the information assuming the entire page is being used,

```
number of entries in each page = (page size) / (page table entry size ) = (2 ^ 11)

```

Now consider the outermost page table. It has 2 ^ 11 entries, which means the second level page table has 2 ^ 11 pages and each page has 2 ^ 11 entries.
Going by this logic it can be derived that the number of pages in process ( logical address space ) = 2 ^ 33
And given page size = 16 KB
Therefore, the logical address space size = ( 2 ^ 33) * 16 KB = 2^47 bytes

---
Tags: memory-management, virtual-memory, paging
---


# Question
Title: Algorithm for clustering points in $\mathbb{R}^2$ based on pairwise distance (percolation graphs)
I haven't been able to find literature on the efficient solving of the following problem.

Given $n$ random points $x\_i \in (0, 1)^2$ the unit square, obtain the flat clusters of points, such that two points are in the same cluster if their pairwise distance $d(x\_i, x\_j) \< r$, where $r \< 1$ is a fixed parameter of the problem.

The naive solution checks each pairwise distance, therefore completing in $\mathcal{O}(n^2)$ time. Is there a faster way, assuming $n$ large and $r \ll 1$?

# Answer
> 2 votes
The following algorithm *does* unfortunately *does not* allow you to get the $n^2$ factor out (see comment below).

Superimpose an $r/\sqrt 2$-by-$r/\sqrt 2$ grid on the unit square: notice that every point within the same grid cell is automatically within the same cluster. Also notice that there can be at most $n$ grid cells containing one or more points; these are the only grid cells we need to consider from this point on.

1. Map each point to its grid cell.
2. For each grid cell, throw all contained points into the same cluster.
3. For each pair of neighbouring grid cells $P$, $Q$ (each grid cell, apart from those at edges and corners, has 8 such neighbours), determine the closest pair of points $p, q$ having $p \in P$ and $q \in Q$ using this $O(n\log n)$ algorithm. If $d(p, q) \< r$ then combine $C(P)$ and $C(Q)$, otherwise not.

You can use a union/find disjoint set data structure to maintain the clusters in close-to-linear time, just as per the Kruskal algorithm.

---
Tags: algorithms, graphs
---


# Question
Title: Collection of inference rules viewed itself as a judgment
I'm confused about the intended meaning of the following passage from Bob Harper's *Practical Foundations for Programming Languages*:

> A collection of rules is considered to define the *strongest* judgment form that is *closed under*, or *respects*, those rules.

The author goes on to explain the italicized words.

Is this to be understood as saying that a collection of rules defines a *unique* judgment which somehow encompasses all judgments derivable from those rules?

If so- of what does this unique judgment consist? Does this necessarily include formal hypothetical judgments? Does it include some kind of union/conjunction of "orthogonal" applications of the rules? (eg $\overline{\text{zero nat}}$ and $\overline{\text{zero even}}$)

If not- what's the correct interpretation?

# Answer
> 3 votes
The interpretation of such paragraph is that rules *define* judgements. It's more or less the same as saying
**closure**: the judgment satisfies this rules
**strongest**: ..and this is all there is

So, for example, if you have the following two rules to define the judgement "to be a nat":

$$\frac{}{\mbox{zero nat}} \quad \frac{x \mbox{ nat}}{\mbox{suc(} x\mbox{) nat}}$$

then you are stating that:

**closed**:

* $\mbox{zero}$ is a $\mbox{nat}$ and
* if $x$ is a $\mbox{nat}$, then $\mbox{suc}(x)$ is a $\mbox{nat}$

**strongest**: no other word is a $\mbox{nat}$

---
Tags: logic, type-theory, semantics
---


# Question
Title: Turing machine for $u<v$ with $u$ and $v$ positive binary numbers
I was wondering how would I go about constructing a Turing machine that accepts $u \< v$ with $u$ and $v$ positive binary numbers: for example $10\<100$ is accepted but $11\<10$ would not be. (We can assume that the leftmost digit is always a $1$). I was thinking that I should start by changing the $1$s to $X$s but that doesn't seem to work out.

# Answer
> 2 votes
So, firstly let's define the input tape. Let's say it looks like "10101\<00101" i.e. "number1\< number2" and accepts only if the expression is true. Also, let the head in the start be on the most left meaningful character. The idea of the algorithm is just to scan two numbers from the left (assuming big-endian encoding for the numbers), if noticed that there is 0\<1 accept immediately, if 0\<0 or 1\<1 then continue working, if 1\<0 then reject.

So, TM sketch:

alphabet is $\\{0,1,\*,\<\\}$ with empty symbol $\epsilon$.

Record the most left bit of the first number If it is 0 you change you state to something like num1\_0 which means number 1 had the leftmost digit 0. Then you go to the right and look for the leftmost digit for the second number. If it is greater than do no accept else move the head to the left most and start from the beginning. Also, when compared two bits just change them to * , so you know where to compare next.

The tape progression looks like this:

101\<111

\*01\<\*11

\**1\<\**1

\***\<\***

accept.

Using this simulator I have come up with the following code:

```
name: Accepting when num1<num2
init: s0
accept: sfin

//main program
s0,0
s1_0,a,>

s0,1
s1_1,a,>

//uncomment this to allow equality
//s0,<
//sfin,<,-

//s1_b means we read the leftmost symbol and it was b
s1_0,0
s1_0,0,>

s1_0,1
s1_0,1,>

s1_0,<
p0,<,>

s1_1,0
s1_1,0,>

s1_1,1
s1_1,1,>

s1_1,<
p1,<,>

//pb means the symbol read from the left number was b and we are looking for the digit from the right number
p0,b
p0,b,>

p1,b
p1,b,>

//COMPARISON LOGIC HERE

//if 0<0 continue exploring
p0,0
goleft,b,<

//if 0<1 immedaitely report yes
p0,1
sfin,b,-

//if 1<1 continue exploring
p1,1
goleft,b,<

//goleft state simply tells to go until reached a to start over
goleft,b
goleft,b,<

goleft,0
goleft,0,<

goleft,1
goleft,1,<

goleft,<
goleft,<,<

goleft,a
s0,a,>

```

This accepts only when the input tape has the true expression number1\< number2 like

> 100100\<100101

and it is limited to compare only the numbers of equal length (easy fix if needed to compare with different length, think about adding zeros to the first number until it matches the length of the second or reject if the length of the first number is greater).

# Answer
> 0 votes
Think about it this way:

First of all replace the first 1 on the LHS and the RHS by a special character, say P.

Then start from the last character on the RHS,and move to the last character on the LHS. If the character on the left is the same as the one on the RHS, replace it by a symbol, say a. If it is less than, replace it by b and if it is greater than, replace it by c. Then do the same thing for the second to last character and so on until you reach P on the RHS.

So if you run the machine on 10100\<10101 then you will get Paaab \< PXXXX. Then all you need to check is that after P on the LHS you find at least one b, and there can be no c before it. For instance if checking 1101\<1011 you get Pcba \< PXXX will fail since there is a c before the b. Note here that as you proceed you change the last RHS character you read by an X to know it has already been checked

Also if you read a 0 or 1 in the LHS after P (LHS longer than RHS) like 100\<10 or P0b \< P0 it should also fail. And last of all if you are checking the kth character (from the end) on the RHS that is not P and the kth character on the LHS is a P, it means the RHS is longer than the LHS so it should accept.

---
Tags: turing-machines
---


# Question
Title: Why would you introduce the goto statement into a modern language?
I just found out something really quite extraordinary. While looking through Stackoverflow, I came across a question about removing `goto` from a php function. PHP doesn't have goto I thought and looked it up on php.net.

It turns out I was sort of right. PHP introducted goto in version 5.3 which was release in 2009. PHP didn't start out with `goto`it actually introduced it into the language in 2009!

Why on earth with all the horror stories we have from 40 years of bad programs written with `goto` in other languages would php actually decide to introduce it?

The php.net website even has this XKCD image suggesting no programmer should ever use `goto`.

## Question:

What possible reason from a technical point of view could there be for introducing a the goto feature, which I nievely thought had been vanquished from modern computer programming languages?

# Answer
There are two kinds of programmers: Those who for whatever reason never, ever use goto, and go to any lengths to avoid it, and those who use goto in one of the very rare situations where it is the best solution. (Someone said here in a comment that goto could be misused and programmers would find ways to misuse it - but those people are not programmers).

It makes sense to add "goto" to a language that doesn't have it if there is evidence that there are situations where it improves the code, and if it is not too difficult to implement. So I would assume that there was such evidence.
> 9 votes

# Answer
The `goto` in itself isn't "evil", it is just easy to misuse. A famous paper by Knuth is "Structured Programming with goto statements", ACM Computing Surveys 6:4 (dec 1974), 261-301. For example the Linux kernel uses `goto` often, in a disciplined and safe way.
> 8 votes

# Answer
Most algorithms and forms of business logic can fit nicely into the control structures that are built into modern languages, in large measure because such structures were designed to fit the needs of common applications. Some applications, however, need to implement algorithms or business logic that do not fit any such control structures.

Programs are generally most readable if the general design of the program matches the design of the algorithm or business logic implemented thereby. If the algorithm or business logic jumps around in weird bizarre ways, a program which uses `goto` to jump around in those same bizarre ways will likely be more understandable than one which has to implement the same logic by adding flags and/or abusing other control structures like `switch`/`case`.

Most algorithms and forms of business logic will either fit naturally into common control structures, or can easily be adjusted to do so. If the necessary behavior will fit into a language's control structures--as it will for most applications--it's generally better to use those structures than to use `goto`. The fact that most programs would receive no benefit from having `goto` available, however, does not mean that it does not provide great benefits in cases where the required behavior doesn't fit any other control structure.

Incidentally, another factor to consider with `goto`: many languages are used not only to process code which written by humans and intended to be readable by them, but also to process machine-generated code which is not required nor particularly expected to be human readable. If the behavior of the generated code is described by a series of state transitions, it may be much easier for the code generator to define a label for each state and use `goto` to hop between them, than for it to try to identify ways of reforming the code to fit the target language's control structures. While some implementations may be better able to process code written using control structures than code written using `goto`, many others start by converting all control structures to conditional branches (i.e. `goto`) internally and then analyze the resulting control-flow graph. If a compiler is going to turn a `for` loop into a bunch of conditional branches, there no reason for a code generator to seek out ways to replace some `goto` branches with a `for` loop.
> 7 votes

# Answer
I’ve used `goto` in exactly one program, not counting BASIC when I was a child. It was to break out of a couple of levels of nested inner loops in performance-critical code, in order to prune a branch of a search tree, without checking a flag in each invocation of all of them. I did it, and I’m not sorry!

I thought at the time that syntactic sugar like `break 3;` to exit three nested loops would have been elegant and shut people up who complain that `goto` is Considered Harmful, but of course that’s just a renamed `goto`. (Now that I think about it again, `break continue` to break out of an inner loop, then skip to the end of the outer loop, might be equally legitimate.). And at that point, maybe it would start to get confusing where exactly the control flow goes, and it might be more readable to add some kind of comment or label at that line anyway.

The main reason Edsger Dijkstra considered `goto` harmful is that it makes formal proofs of program correctness impossible. So, while I appreciate that I don’t have to maintain spaghetti code, I do wonder how many of the people who know that rule ever formally prove their code correct.
> 4 votes

---
Tags: programming-languages, language-design
---


title: PDA with an unusual double inequality

text:
# Question
Title: PDA with an unusual double inequality
I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before.

$L = \\{w\in\\{a,b\\}^{\*} : 3\\#\_{a}(w) \leq 5\\#\_{b}(w) \leq 4\\#\_{a}(w)\\}$

Could I get some pointers on how to tackle such a problem like this so I can be more familiar with the approaches here.

# Answer
It's your exercise, so you should solve it yourself... but I will give you two hints.

1. Study the methods used in Grammar for a language with 1/3 of a's. They are helpful.
2. Use non-determinism. Build a non-deterministic PDA. (How do you think non-determinism might help here?)
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: Simple question about grammar derivations
I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.

Here is an example of a grammar derivation in a Youtube lecture I found. I get everything he covers here *except* that it isn't clear to me how a derivation is chosen when there are multiples available.

For example, in the video he constructs a grammar E that has productions `E + E`, `E * E`, and `id`. I'm *assuming* that the correct derivation is chosen by pattern matching the input string to the grammar but that isn't made clear, nor is it really made clear in other sources I've read and watched. The derivation used at a given step sometimes seems arbitrarily chosen.

My reason for asking is because if it isn't matched to the input pattern, what is to keep his grammar from expanding an E into the (arbitrarily chosen) non-terminal production `E + E` infinitely, and never reach a terminal condition?

**Edit** Related question:

On the bottom of this page there is a discussion of leftmost and rightmost derivation. In the leftmost derivation example, how does it know the correct derivation to use to move from the second to third derivation? In other words, how does it know to make this derivation: `a+X → a+ X*X`

Why couldn't it just derive `a+X → a+a` and terminate? I know it doesn't match the input string, but what actually prevents that incorrect derivation from being chosen?

# Answer
> 1 votes
Actually you have to study the working of a parser in detail to get the answer to your question.

Parsers can be top down or bottom up. In top down parsing, we try to derive the input string from the start symbol. In bottom up parsing, the reverse procedure is applied, i.e. we try to reduce the input string to the start symbol.

Let me try to answer your question by explaining the working of recursive descent parser, a general top down parser.

Recursive descent parser will choose the productions based on the order in which they are specified. I will explain with an example.

The grammar given is

```
    S-> aAB | bAB
    A-> d | a
    B-> b

```

Let the input be

```
    bab

```

The input pointer points to the first symbol 'b'. The recursive descent parser will start with start symbol S. The working is as follows

```
    S-> aAB

```

Whenever a terminal symbol is obtained, it is checked for match with the current input symbol. Input symbol 'b' doesn't match with the terminal 'a'. So the parser will backtrack and choose the next production

```
    S->bAB

```

The terminal symbol matches with the input. Hence input pointer is advanced and it points to 'a'. Next substitute for A.

```
    S-> bdB

```

Input symbol and the obtained terminal does not match. So backtrack and choose the next production for A.

```
    S-> baB

```

Now a match is obtained and B is replaced with its production

```
    S->bab

```

Thus input is successfully parsed. The steps in derivation can be summarised as

```
    S-> aAB (backtrack)
     -> bAB
     -> bdB (backtrack)
     -> baB
     -> bab

```

# Answer
> 1 votes
The answer to your question lies in the way we construct the parser. The parser constructs its parsing tables based on the next input character(lookahead) which it expects. As explained in the answer by @elantra the recursive descent chooses the production by checking on the input symbol.

if you have come across the terms such as LR(k) parsers , here 'k' represents the number of lookaheads parsers decides to check in the input before deciding which production to use . However for some values of k , such as zero there is a chance that parser is not able to decide which production to use. These situations while parsing are called conflicts. We chose the value of 'k' such that we don't face such conflicts. LR(1) and canonical LR are great examples.

Another aspect to your question is in the case of ambiguous grammars. It is difficult building a parser for the ambiguous grammars so we first convert the grammar to remove the ambiguity by introducing some sort of precedence or we could also use the operator precedence grammar which removes the ambiguity and construction of parser becomes feasible.

# Answer
> 1 votes
The answer to how to find out derivation of an input string require understanding of few basic computations like First and Follow.

To give you an intuition, what we are essentially trying to find out is "For each grammar symbol where in the sentential form this symbol can appear?".

There are multiple algorithms to find this out based on bottom-up or top-down approach. Once we know where possibly a grammar symbol derivation can be used we scan the input string left-to-right and use the appropriate derivation.

It might happen that we end up with multiple derivation appearing at same place in the sentential form. In such cases we cannot be sure which one to use. To tackle this problem we try to find out symbols that can appear after a grammar symbol in the sentential form and we look ahead one or more characters in the input string to check if those characters are the one that can follow the grammar symbol.

If you continue to watch the same video series that you mentioned, it goes on to explain the algorithms to do this.

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Check the Regularity of the folowing Languages
Let $A$ be a regular set. Consider the two sets below.

\begin{align\*} L\_1 &= \\{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \\}, \\ L\_2 &= \\{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \\}. \end{align\*}

Which of the following is true?

1. $L\_1$ and $L\_2$ are regular
2. $L\_1$ is regular but $L\_2$ is not
3. $L\_2$ is regular but $L\_1$ is not
4. Both are not regular

**What I knew**

$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L\_1$ is regular.

But, **How to check the regularity of $L\_2$?** I also wanted to confirm my approach to $L\_1$ being regular is correct.

# Answer
> 7 votes
Your reasoning regarding $L\_1$ is wrong. What you show is that for each $n$, the following language is regular whenever $A$ is regular: $$ L\_1^{(n)} = \\{ x : x^n \in A \\}. $$ The language $L\_1$ is the infinite union of $L\_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).

Nevertheless, $L\_1$ is regular. Given a DFA $\langle Q,q\_0,F,\delta \rangle$ for $A$, we construct a DFA for $L\_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta\_{L\_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.

The language $L\_2$, in contrast, is not necessarily regular. For example, if $A = ab^\*$ then $L\_2 \cap ab^\*ab^\* = \\{ ab^n ab^n : n \geq 0 \\}$, which isn't regular.

# Answer
> 4 votes
A possible way to prove that $L\_1$ is regular is to use finite monoids. A language $A$ of $\Sigma^\*$ is *recognised* by a finite monoid $M$ if there is a surjective monoid morphism $f:\Sigma^\* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = A$.

Now let $Q = \\{ x \in M \mid \text{there exists $n\geqslant 0$ such that $x^n \in P$}\\}$. Then \begin{align} f^{-1}(Q) &= \\{ u \in \Sigma^\* \mid f(u) \in Q \\} = \\{ u \in \Sigma^\* \mid \text{there exists $n\geqslant 0$ such that $f(u)^n \in P$} \\}\\ &= \\{ u \in \Sigma^\* \mid \text{there exists $n \geqslant 0$ such that $f(u^n) \in P$} \\} \\ &= \\{ u \in \Sigma^\* \mid \text{there exists $n \geqslant 0$ such that $u^n \in A$}\\} = L\_1 \end{align} Thus $L\_1$ is regular. This method actually shows that if $M$ recognizes $A$, then it also recognizes $L\_1$. This is useful to prove further properties: for instance if $A$ is star-free, so is $L\_1$.

EDIT. See Yuval Filmus' answer for a proof that $L\_2$ is not regular. My first answer for this part was plain wrong and has been deleted.

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


# Question
Title: How to find the minimal DFA for the language?
Design a minimal DFA for the language which contains numbers in the form of binary strings starting with $101\_2$ and is divisible by $100\_{10}$?

I think the numbers will be 700,1400,2100 ... in the form of binary strings which are starting with $101\_2$ and are even divisible by $100\_{10}$.

100 is divisible by 25 and 4.

For divisible by 4 - Minimum 3 state DFA is possible For divisible by 25 - Min 25 state DFA is possible.

Hence, for divisible by $100\_{10}$ - Minimum 100 states DFA is possible .

So, for starting with $101\_2$, I have to add 3 extra states along with one dead state.

So, total states in minimal DFA = 100 + 3 + 1 = 104

Is my approach correct or am I missing something?

# Answer
> 1 votes
Your approach towards estimating the number of states is just fine. however the number of states looks quite intimidating and it may be cumbersome to minimize the DFA later.
In such cases constructing the automaton through intersection is easier. for example as we know the regular languages are closed under the intersection operation we can devise 3 different automata to accept :
1. String divisible by 25
2. String divisible by 4
3. Strings beginning with 101

And then arrive at the final automaton by taking intersections of the 3 machines.

### How this helps?

Many of the states originally present in the different machines gradually become unreachable from the initial state in the final automaton and thus the number of states reduce or the DFA is minimized.

# Answer
> 0 votes
Your initial approach is right but can be improved.

First, a binary number is a multiple of $4$ if and only if it ends with $00$. Thus the conditions "starting with $101$" and "multiple of $4$" together define the language $L = 101\\{0,1\\}^\*00$. The minimal DFA of $L$ is the following:  You now have to compute the intersection of $L$ with the language $K = \\{ \text{binary strings representing the multiples of $25$}\\}$. As you observed, the minimal DNA of $K$ has $25$ states, say $0, \ldots, 24$, corresponding to the possible values modulo $25$ of a natural number. A DFA accepting $L \cap K$ is obtained by taking the accessible states in the product of the previous automata. The initial state is $(1, 0)$ and the first 4 transitions are the following (since, for instance $101\_2 = 5\_{10}$).  Starting from state $4$, you may have to consider all states $(4,n)$, $(5,n)$ and $(6,n)$, where $0 \leqslant n \leqslant 24$. This gives an upperbound of $3 \times 25 + 3 = 78$ for the minimal DFA of $L \cap K$ (plus one if you want to add the sink state).

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


# Question
Title: Give three words that are in the language of the first and second regular expression
This is our alphabet: $\\{0,1,2\\}$

And lets say I have two regular expressions:

Regular expression 1. $(1|22|0)^\* (2|0)^\*$

Regular expression 2. $(0|1)^\* (1|20|1)^\*$

How can I give three words each over the alphabet such that they are:

* in both languages
* in the first language but not in the second language
* not in the first language but are in the second language
* not in either of the languages

# Answer
> 0 votes
I've worked out how to tackle my problem.

The way I did it was by converting the regular expressions into DFA's and then visually following the DFA to find words that are in both languages, in the first language but not the second, in the second language but not the first and finally, not in both of the languages.

> The alphabet is {0,1,2}
>
> Regular expression 1. (1|22|0)∗(2|0)∗
>
> Regular expression 2. (0|1)∗(1|20|1)∗
>
> Give three words each over the alphabet such that they are:
>
> * in both languages
> * in the first language but not in the second language
> * not in the first language but are in the second language
> * not in either of the languages

**Here is my solution:**

**Step 1:**

Convert the regular expressions into automatons.

(Unfortunately, I can't post the images directly to stackoverflow because I do not have enough reputation points. Instead, click the images below to see the DFA's).

DFA of the first regular expression: https://s17.postimg.org/9rbdmk94f/automaton\_1.png

DFA of the second regular expression: https://s18.postimg.org/3jtyzdesp/automaton\_2.png

**Step 2:**

Follow the transitions of the DFA to check if the DFA accepts or rejects the word. If it accepts the word, it is in the language, if it rejects the word, it is not in the language.

**Answer to question**

Three words over the alphabet which are **in both of the languages:**

1) 00

2) 10101

3) 2020

Three words over the alphabet which are **in the first language but not the second:**

1) 2222

2) 0102

3) 22

Three words over the alphabet which are **in the second language but not the first:**

1) 01201

2) 2011

3) 1011201

Three words over the alphabet which are **not in both of the languages:**

1) 2221

2) 1021

3) 011001121

The problem with this method is if your regular expression is really long and complex, then it might be difficult to draw out a DFA and visually find words that are in and are not in the language. But this method will help if your regular expression is fairly short and simple.

I hope my answer was of help to anyone else who is interested to tackle similar problems.

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


# Question
Title: Linear time algorithm for array with distinct element
Given an array, if all the elements are distinct, can we find the count of elements which are lesser than an element and present to the left of that element in linear time if we have to do it for every element.

I know this can be solved in `O(nlogn)` time by using `self balancing trees`, but I want to know whether we can solve it in `O(N)`?

# Answer
You cannot do it in linear time using only comparisons. If you could, then you could do it for the array and its reverse in $O(n)$ and then for each element determine in $O(1)$ its position in the sorting of the array. This gives a comparison-based linear time sorting algorithm, which we know cannot exist.

You have to tell us more about the domain of the elements in the input array if you want to get an $o(n \log n)$ algorithm. For example, do you have a constant upper bound on the value of the maximum element?
> 5 votes

---
Tags: algorithms, arrays
---


# Question
Title: Construct regular expression for language
How to construct regular expression for language L which contain all words in which there is a letter 'a' and the letter 'b'? Of course, I understand that it's easy problem but I just start to learn this science? Please, any advices and hints.

# Answer
> 1 votes
For $ \Sigma = \big\\{ a,b \big\\} $, all words containing letter $a$ and letter $b$ may be, in my view, expressed as follows: $$ R = (a + b)^\*a(a + b)^\*b(a + b)^\* + (a + b)^\*b(a + b)^\*a(a + b)^\* $$ can be reduced to: $$ R = (a + b)^\*\big\[ a(a + b)^\*b + b(a + b)^\*a \big\](a + b)^\* $$ Graphically:
Now: $$\Sigma ^\* = \big\\{ ab, ba, aab, aaab, babaa, bab, ... \big\\}$$
This means any number of letters $a$ and/or $b$ before and after $a$ letter, followed by letter $b$ followed by any number of letters $a$ and/or $b$ or($a$, $b$) in the reverse order, ie. any number of letters $a$ and/or $b$ before and after the letter $b$, followed by a letter $a$ followed by any number of letters $a$ and/or $b$.

# Answer
> 1 votes
Assuming that the input alphabet is $\Sigma = \\{a,b\\}$, the term $(a|b)^\*a(a|b)^\*b(a|b)^\*$ describes all words where there is an $a$ followed by a $b$, and the term $(a|b)^\*b(a|b)^\*a(a|b)^\*$ describes all words where there is a $b$ followed by an $a$. If we combine both, we get $$ ((a|b)^\*a(a|b)^\*b(a|b)^\*)|((a|b)^\*b(a|b)^\*a(a|b)^\*) $$ which describes the set of all words in which at least one $a$ and one $b$ occurs.

*Edit*: An even shorter solution would be $$ (a|b)^\*(ab|ba)(a|b)^\*. $$ However, this solution requires the alphabet to contain exactly $a$ and $b$ whereas the first solution can easily be extended to arbitrary alphabets.

# Answer
> 1 votes
If you want to construct regular expression not only for this language that you mentioned also for every other regular language you can simply build NFA, usually building NFA is simple after that you can convert NFA to DFA by power set construction algorithm, in this algorithm you create DFA that all of its states are subset of states in NFA for exmple if statest of NFA are $x\_1,\cdots,x\_k$ then you have $2^k$ state in DFA and design new transition function such that state $\\{q\_1,\cdots ,q\_n\\}$ goes to state $\\{p\_1, \cdots ,p\_m\\} $ with $a \in \Sigma$ if from $q\_1 , \cdots , q\_n$ you can go to $p\_1, \cdots, p\_n$ with character $a$. after that, you can use an algorithm to convert DFA to RE which is discussed in Micheal Sipser's book.

---
Tags: regular-expressions
---