# Question
Title: Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?
I'm following an online course about Complexity and I'm learning a lot of stuff.

I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here.

The exercise is to prove the following is true:

$4\ \sqrt{n} + 2\ n\log\_2(n) + 3 = \mathcal{O}(n\log(n))$

So basically I'm looking for a $k$ and a $n\_0$ such as $\forall n \geq n\_o: 0 \leq f(n) \leq k\ g(n)$

* $f(n) = 4\ \sqrt{n} + 2\ n\log\_2(n) + 3$
* $g(n) = \mathcal{O}(n\log(n))$

I started to do:

1. $4\ \sqrt{n} +2n\log\_2(n) + 3 \leq kn\log(n)$
2. Replace $3$ with $3n\log(n)$: $4\ \sqrt{n} +2n\log\_2(n) + 3n\log(n) \leq kn\log(n)$ with $n\_0 \geq 10$
3. Replace $\sqrt{n}$ with $n$: $4n +2n\log\_2(n) + 3n\log(n) \leq kn\log(n)$ with $n\_0 \geq 10$ and $n\_0 \geq 1$
4. Replace $4n$ with $4n\log(n)$: $4\ n\log(n) +2n\log\_2(n) + 3n\log(n) \leq kn\log(n)$ with $n\_0 \geq 10$, $n\_0 \geq 1$
5. Update log base: $4\ n\log(n) +\frac{2}{\log(2)}n\log(n) + 3n\log(n) \leq kn\log(n)$ with $n\_0 \geq 10$, $n\_0 \geq 1$

Therefore

* $n\_0 \geq 10$
* $k \geq 4 + \frac{2}{\log(2)} + 3$

Is this the proper way to do it?

# Answer
> 1 votes
Same can be possible in steps. For $a\>1$: $$4\sqrt{n}\<4n\log\_a n$$ $$3\< 3n\log\_a n$$ where $n\>a$. Summing up we have $$\sqrt{n}+2n\log\_a n+3\<9n\log\_a n$$ for $a\>1$. As to "right" bound, then such doesn't exist - any bounds are right, if/when they satisfy definition.

# Answer
> 1 votes
If we divide the inequation by $n\lg n$, we get

$$\frac{4}{\sqrt n\lg n}+\frac{3}{n\lg n}+2\le c.$$

By a quick study of the denominators, we can see that the fractions are monotonically decreasing, say for $n\ge n\_0=2$ (they are as of $x\>1$). Hence any $c$ such that

$$\frac{4}{\sqrt 2\lg 2}+\frac{3}{2\lg 2}+2\le c$$ will do.

This establishes $\mathcal O(n\lg n)$, which is also $\mathcal O(n\log n)$.

---
Tags: big-o-notation
---


# Question
Title: CFL with regular substitution to make a regular language
If I have a CFL, can I define a regular substitution to make it a RL?

For example, if I have the language $\\{a^nb^n \mid n\ge0\\}:$

Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^\*}$ , am I right?

Thanks!

# Answer
> 1 votes
No,by your defined substitution CFLs remains CFLs. For example, $\\{a^nb^n \mid n\ge0\\} = \\{\epsilon,ab, aabb, aaabbb,.......\\}.$
After substitution by $h(a) = a$ and $h(b) =b$,$h(\epsilon) = \epsilon$ then the language L becomes remains same, which is CFL. But when every symbol converges to single image then your language forcefully becomes regular (as @rici answer) which is really very bad way of thinking because by the definition homomorphism of CFLs is CFLs.

N. B.- One thing remember substitution for DCFLs are not closed in general (for example) but substitution for CFLs(NCFLs) are closed always.

# Answer
> 1 votes
Yes, you can.

For instance: with language $L = \\{a^nb^n \mid n\ge0\\}$ and mapping $h(\epsilon)=\epsilon, h(a)=a, h(b)=a$ (which I think is what you meant to write), $h(L) = (aa)^\*$.

What is more: *every* context-free language on a single-symbol alphabet is regular, so a mapping that maps every symbol to the same symbol always produces a regular language.

However, as user19121278 points out, not every mapping will.

For instance: the identity mapping ($h(\epsilon)=\epsilon, h(a)=a, h(b)=b$ for alphabet $\\{a,b\\}$) maps every language to itself, so it will never map a non-regular language onto a regular one.

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


# Question
Title: I need to sort out the theta complexity for lg(n^(1/2))
Can you help me find the theta complexity for lg(n^(1/2))?

# Answer
$log(n^{\frac{1}{2}}) = \frac{1}{2}log(n) = \theta(log(n))$.

More formally, there exists constants $c1$,$c2$ such that:

$c1⋅\frac{1}{2}log(n)≤log(n)≤c2⋅\frac{1}{2}log(n)$
> 1 votes

# Answer
A valid answer is

$$\lg(\sqrt n)=\Theta(\lg(\sqrt n)).$$

This is true as of $n=1$ with constants $1$.

Another valid answer is

$$\lg(\sqrt n)=\Theta\left(\sum\_{k=1}^n\frac1k\right).$$

(Holds as of $n=2$ with constants $0.2$ and $1$.)
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Tolerance of object size variation for computer vision
relatively new to Computer Vision.

Lets say for example, I have a sequence of images of a car driving away from a static camera into the horizon, and I want to use this image set for some bog standard computer vision experimentation (e.g to train a CNN to recognize a car). I label the car in each frame with a rectangular bounding box. At the start of the sequence, the area of annotation required to cover the visible car is approximately 1500x500 pixels. At the end of the sequence, the area is only 3x1 pixels. Does there come a point in this sequence of images, whether by some rule of thumb or by a derivable metric, in which it no longer becomes beneficial to label the car for training purposes (i.e it will harm model performance)? I remember reading somewhere recently that its not beneficial to train CV algorithms on objects that change size, but I'm not sure whether there are guidelines to setting acceptable tolerance thresholds.

# Answer
> 1 votes
Your labels should be based on what you want the model to output when used in deployment. If you use this in deployment, is it important to produce a 3x1 bounding box? If it is, you'd better include those images and label those cars. If it is important to not produce a 3x1 bounding box, you'd better include those images and not label those cars. If it doesn't matter whether your model produces a 3x1 bounding box for those tiny cars, then you might consider labelling those cars but marking them as "don't-care" so the model is neither penalized for producing a bounding box nor penalized for failing to produce a bounding box; or excluding those images from the training set.

How do you choose the threshold? Choose it based on your application needs.

How can you tell what is the impact of different values for the threshold? Probably you have to do this empirically. You can try an experiment where you set one threshold, train a model, and check to see what happens.

Is there a rule of thumb? Not that I know of specifically, but the usual way to figure this out is to find a few papers that tackle the same task, and check to see what threshold they use. A plausible starting point is to copy whatever they have used.

---
Tags: computer-vision
---


# Question
Title: Rigorous distinction between search and optimization
I'm working my way through parts of Russell and Norvig's AIMA book for a class, and there's something I've never quite managed to wrap my head around. Chapters 3 and 4 contrast 'search' methods with 'local search' optimization methods, suggesting to me that there is some kind of fundamental difference between the two. Here's what I currently understand:

Search algorithms work on graph representations of state space. The idea is to find the least-cost path from an initial state to the goal state. By contrast, local search solves optimization problems by starting from some initial state and moving to the best neighbour at each step, choosing whichever transition is *locally* optimal, until it reaches the desired global optimum (or runs out of resources). It does not keep track of the path to the current state.

A lot seems to be made of this last fact, but it seems to me that this is merely an artefact of the problem formulation. The fact that we're keeping track of the path to the current state in e.g. Dijkstra's algorithm is a consequence of defining the states to be the nodes in the graph. If instead we consider the state space to consist of all *paths to the goal*, then we don't have to keep track of the path, and this 'search' simply becomes an ordinary optimization problem.

Conversely, if we take the example of the 8 queens problem, the fact that a solution is an optimal state instead of a path is an arbitrary choice. To wit, we can equivalently build a graph consisting of representations of possible movements of 1 piece from an initial configuration (e.g. $(0, \dots, L, \dots, 0)$ for move $i$-th piece left), and then the solution would essentially be a path (more precisely the configuration obtained by following this path from an initial position).

Is there any fundamental distinction (i.e. not a consequence of arbitrary problem framing) between search and local search? If not, can Dijkstra's algorithm be considered to simply be global optimization algorithm?

# Answer
A representation where the state space is all paths to the goal is completely unusable. It blows up the state space exponentially large. And it loses the structure that algorithms like A\* make good use of.

Yes, search in a graph *is* an optimization problem, and you could certainly view it from that perspective, and use any optimization algorithm you want. But it is an optimization problem that comes with some special structure, and many graph search algorithms make use of that special structure. This is not unusual in optimization: if we have a kind of optimization problem with some special structure, sometimes we can find custom algorithms that a specialized to that situation and that perform better than general-purpose optimization algorithms on problems with that structure.

For me, the interesting bit about search in graphs is not that we keep track of paths (many graph search algorithms don't keep track of paths), but that it is an optimization problem that has some special structure that can be exploited to construct better algorithms.
> 1 votes

---
Tags: artificial-intelligence, graph-traversal, search-trees
---


# Question
Title: Can almost equal partition problem be solved in polynomial time?
Given a list of positive integers with sum $s$, decide if there is a subset with sum $0.5s$. This is the well-known PARTITION problem, which is NP-hard.

What about the following: Given a list of positive integers with sum $s$, decide if there is a subset with sum in the range $\[0.49s, 0.51s\]$. Can this problem be solved in polynomial time?

# Answer
Yes, this problem is polynomial-time solvable.

Let $A$ be the input numbers and let $S = \mathrm{sum}(A)$ be its sum. Let $T\_1 = 0.49S$, $T\_2 = 0.51 S$ be the target sum range. Let $\epsilon = 0.02$ so that $T\_2 - T\_1 = \epsilon S$.

Define $A\_1 = \\{ a \in A \mid a \geq \epsilon S \\}$ to be *large* items and $A\_2 = A \setminus A\_1$ to be *small* items.

Proposition: For a subset of large items $X \subseteq A\_1$, there exist a solution containing that subset if and only if $T\_1 - \mathrm{sum}(A\_2) \leq \mathrm{sum}(X) \leq T\_2$.

The "only if" direction is from the fact that the range of possible sum containing the subset $X$ is $\[\mathrm{sum}(X), \mathrm{sum}(X) + \mathrm{sum}(A\_2)\]$ (note the assumption of all items are nonnegative) and it must have a non-empty intersection with $\[T\_1, T\_2\]$.

To prove the "if" direction, consider adding small items arbitrary as long as the sum is less than the lower bound $T\_1$. Because added items are small, it cannot overshoot the upper bound $T\_2$.

Now, we have an algorithm solving the problem by brute-forcing all subsets $X \subseteq A\_1$ of large items and checking its sum. The time complexity of the algorithm is $O(n + 2^{|A\_1|} |A\_1|)$. Because we have $|A\_1| \leq \epsilon^{-1}$, the time complexity is polynomial in $n$ for a constant $\epsilon$. The exponent can be reduced to half using the meet-in-the-middle approach.
> 3 votes

---
Tags: algorithms, complexity-theory, time-complexity, partitions
---


# Question
Title: What is the time complexity of SLR and LALR parsers?
What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)?

How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) but I'm not sure there is a relation between LR(k) and SLR(k) or LALR(k)!

# Answer
> 1 votes
They all run linear time with regards to input length ($O(n)$). The different algorithms have different memory trade offs for making it easier to write grammar for. That is not all grammars that work for LR(1) work for SLR for example. However LR(1) uses more memory than SLR which used to be a problem, but not really a problem anymore for modern machines.

LR(k) is rarely used. It hogs up an exponential amount of memory with regards to $k$. However any grammar for LR(k) can be rewritten for LR(1). And LR(1) handles all the languages LR(k) can, and vice versa. So most stick to LR(1) instead of LR(k).

LALR(1) uses less memory again than LR(1). And doesn't handle as many languages as LR(1) does. However LALR(1) is powerful enough to parse Java.

LALR(k) once again is a memory hog, and all grammar suitable for LALR(k) can be rewritten for LALR(1). And they can both handle the same languages as each other.

All of those shift reduce parsers mentioned do a fixed maximum amount of work (with regards to the grammar itself) for each token feed to them. So they are all $O(n)$.

If you going to implement one for sake of learning it, go with LR(1). Because the other algorithms are similar but with missing features (remove a feature to get the other implementation). Learning LR(1) first makes it easiest to learn them all imo.

---
Tags: time-complexity, compilers, parsers, lr-k
---


# Question
Title: Name and complexity of this problem on bipartite graphs
Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes.

I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}\_u$ contains at least one element and is different from $\hat{V}\_{u'}$, $\forall u' \neq u \in U$, where $V\_u \subseteq V$ the set of nodes in $V$ to which $u$ is connected.

Note that we can assume that an optimal solution does exist.

To make an example, consider the following graph, with $U=\\{A, B, C\\}$ and $V=\\{X, Y, Z\\}$:

The optimal $\hat{V}$ here would be:

Indeed:

* $\hat{V}\_{a}=\\{x, z\\}$
* $\hat{V}\_{b}=\\{x\\}$
* $\hat{V}\_{c}=\\{z\\}$

That is, $\hat{V}$ is the smallest subset of $V$ such that, for every node $u \in U$, $\hat{V}\_u$ is non-empty and different from $\hat{V}\_{u'} \\: \forall u' \neq u \in U$.

This problem definitely rings a bell, but both my memory and my searching skills seem to be failing me. My questions are:

* Does this problem have a name?
* Is it NP-hard and, depending on this answer, can anybody sketch (or point me to) a solution or an approximation?

# Answer
> 3 votes
This problem is related to the hitting set problem. You can represent this problem in terms of sets. Let $V$ be the ground set and we define the family $\mathcal{F} = \\{V\_u = N\_G(u)\colon u \in U\\}$

Solutions to your problem have a one to one correspondence with hitting sets $\hat V \subseteq V$ whose intersections with the sets in $\mathcal F$ are pairwise different. The hitting set problem is NP-hard. I am unfamiliar with your version of the problem but you can try to reduce the hitting set problem to your restricted version of the problem to show the hardness of your version as well.

# Answer
> 2 votes
I don't know a prior result on this particular problem. However, I can show this problem is NP-hard by reducing the hitting set problem.

Suppose we are given an instance of the hitting set problem as a bipartite graph $(U, V, E)$. Let $n = |U|$.

The reduction adds $n$ new vertices to both sides $U' = U \cup \\{u\_{n+1}, \dots, u\_{n+n}\\}$ and $V' = V \cup \\{v\_{n+1}, \dots, v\_{n+n}\\}$. Then, add edges connecting newly added vertices $E'\_1 = \\{ (u\_{n+i}, v\_{n+i}) \mid i \in \[n\] \\}$ and edges connecting original vertices of the left-side and newly added right-side vertices $E'\_2 = \\{ (u\_i, v\_{n+i}) \mid i \in \[n\] \\}$ so $E' = E \cup E'\_1 \cup E'\_2$.

Now, I claim a subset $X \subseteq V$ of the original right vertices is a solution to the original hitting set instance if and only if the subset plus newly-added right vertices $X \cup \\{ v\_{n+1}, \dots, v\_{n+n} \\}$ is a solution of the reduced instance $(U',V',E')$ of the problem in the question. A proof sketch follows.

First, because every newly-added left vertex $u\_{n+i}$ have only one neighbor $v\_{n+i}$, every newly-added right vertex $v\_{n+i}$ must be used in the solution.

Second, an original left vertex $u\_i$ has a distinct neighborhood set if and only if at least one original neighbor vertex $v\_j$ is used in the solution. This is because if no original neighbor vertex is used in the solution, the neighborhood set of $u\_i$ is a single newly-added right vertex $\\{v\_{n+i}\\}$ and it is duplicated with the neighborhood set of the newly-added left vertex $u\_{n+i}$. Also, no duplication of neighborhood set occurs between original left vertices $u\_i, u\_j$ because the newly-added right vertex $v\_{n+i}$ is only contained in the neighborhood set of $u\_i$ if $i \neq j$.

---
Tags: graphs, np-hard, bipartite-graph
---


title: How to read Nasa Convolutional code?

text:
# Question
Title: How to read Nasa Convolutional code?
Here is a picture from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 207(English Version)/Page 206(Japanese Version):

I want to verify whether my interpretation is correct or not. My interpretation is in the picture that has red arrows.

From the picture, I made a table to understand easily the internal condition of Nasa Convolutional code.

So from my interpretation, I got

Out1:Input+S2+S3+S5+S6 .. formula(1) Out2:Input+S1+S2+S3+S6.. formula(2)

From the excerpt Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

We know that when internal state is 100000, the output will be 11.However, when I use formula(1) and formula(2), I didn't get 11 but instead I got 10.

Out1:Input+S2+S3+S5+S6=1+0+0+0+0=1 Out2:Input+S1+S2+S3+S6=1+1+0+0+0=0

My question is, is my interpretation is correct? If it's correct, why don't I get the output 11? If it's wrong, where did I get it wrong? Please teach and correct me.

# Answer
It looks like you are taking the "internal state" as each row in your table from input to s1, all the way to s6. But internal state is defined as from s1 to s6.

So internal state is 7 digits, not 6. And it is:

1. Row 1 - 000000, output 00
2. Row 2 - 100000, output 11
3. Row 3 - 110000, output 10
4. Row 4 - 111000, output 01

Compare rows 2 to 4 and you can see it matches with what the author wrote.
> 0 votes

# Answer
It is just a matter of whether you take the values before or after the shift.
> 0 votes

---
Tags: error-correcting-codes
---


# Question
Title: If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular
Prove/disprove the following claim:

If $L\in RL$ then $\\{x~|~\exists y ~~s.t~~ xyx^R \in L\\} \in RL$

I think that this is true, and my intuition is by using $L\_{pq}$ s.t:

For every $(p,q)\in Q\times Q$ define $L\_{pq}=\\{w|\delta'(p,w)=q\\}$.

Then by using $L\_{pq}○L\_{q,q'}○(L\_{pq})^R$ and taking the union of all possible pairs, do we get the desired result?

Thanks!

# Answer
> 1 votes
Start with an automaton for $L$, with states $Q$, initial state $q\_0$, final states $F$, and transition function $\delta$. Construct a new automaton whose set of states is $Q \times 2^Q$. After reading a word $x$, the new automaton should be at state $$ \langle \delta(q\_0,x), \\{q : \delta(q,x^R) \in F\\} \rangle. $$ I will let you complete the definition of the automaton.

---
Tags: formal-languages, regular-languages, automata, finite-automata, context-free
---


# Question
Title: Regular Expressions with at least 3 b's and at most 2 a's
I am not a Regular Experssion expert, but my request is simple: I need to match any string that has at least 3 characters of B and at most 2 characters of A

so for example:

```
"ABABBB"  => Accepted
"ABBBBBB" => Accepted
"BBB"     => Accepted
"ABB"     => Rejected
"AABB"    => Rejected
"AA"      => Rejected

```

# Answer
I don't think there is any simple solution.

There are 15 ways to write a word with 3 $b$'s and at most 2 $a$'s: $bbb$, $abbb$, $babb$, $bbab$, $bbba$, $aabbb$, $ababb$, $abbab$, $abbba$, $baabb$, $babab$, $babba$, $bbaab$, $bbaba$ and $bbbaa$.

Between every pair of letters of those words, you can insert any number of $b$'s, which can be written with a $b^\*$ in a regular expression.

So you'd get: $$bbbb^\* + b^\*abbbb^\* + b^\*babbb^\*+ … + b^\*ab^\*abbbb^\* + …$$
> 0 votes

# Answer
A regular expression can be developed from the following finite state machine for at most 2 **A**s and at least 3 **B**s by using all possible paths separate by |, and using * where their is a loop edge.

Resulting regex: `AABBBB*|ABABBB*|ABBABB*|ABBBAB*|ABBBB*AB*|BAABBB*|BABABB*|BABBAB*|BABBB*AB*|BBAABB*|BBABAB*|BBABB*AB*|ABBBB*|BABBB*|BBABB*|BBBAB*|BBBB*(AB*)?(AB*)?`
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Finding an element within an array that satisfies some rule
I saw a question on an old exam in my university course of DSA and I am not sure if the question is far too easy or if I am missing something.

The question is :

> Given an array A that consists of N integers such that for any $1 \< i \leq N$ the following properties holds :
>
> * $| A\[i\] - A\[i-1\] | \leq 1$
> * $ A\[N\] \> A\[1\] $
>
> Given an element z such that A\[1\] $\leq$ z $\leq$ A\[N\], Write an efficient search algorithm and analyze its complexity.

I started thinking about this problem and after a few minutes, I found that from the fact we have A\[1\] \< A\[N\] and that the absolute value of the difference between 2 consecutive elements has to be at most one, we can deduce that our array must contain all the values between A\[1\] and A\[N\], therefore the algorithm should only check if z is between A\[1\] and A\[N\].
Am I missing something?

# Answer
Lets say a\[1\] = 1, a\[N = 1000\] = 2, and z = 450. The first array element that could equal z is a\[450\], and the last one is a\[552\]. Since 450 ≤ 552, there could be a solution.

So you have reduced the range. Now check the values a\[450\] and a\[552\]. Either one of them is equal to z, or you can reduce the range again. Now the worst case is that you have a large range of values equal to z-1, and there might or might not be one equal to z in the range. Solving this will require linear time. Bad example:

a\[1\] = 1, a\[2\] .. a\[N = 1000\] = 2 except perhaps a\[k\] = 3, and z = 3. You have to check every value.
> 1 votes

# Answer
The proposed approach by @gnasher729 is true. Maybe the following commands clarify it.

Let L=1 and U=N for the lower and upper range of the search area in array A.

1. Repeat the following commands:
2. If L\>U then Z does not exist in array A and terminate.
3. If Z==A\[L\] or Z==A\[U\] then we found Z and terminate.
4. Else, reduce the search area by L=Z-A\[L\] and U=A\[U\]-Z; i.e. Z cannot be found before index Z-A\[L\] and after index A\[U\]-Z.
> 0 votes

---
Tags: arrays
---


# Question
Title: What is the correct complexity of All paths from Source to Target DFS solution?
The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?

# Answer
> 2 votes
First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}\[1, \dots n\]$ such that $\operatorname{TS}\[1, \dots n\]$ is a permutation of $1\\, \dots n$ and $i \< j$ implies that a path from node $\operatorname{TS}\[j\]$ to $\operatorname{TS}\[i\]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum\_{i=1}^{n}T(i).$$

*Proof:* If you call your function on $\operatorname{TS}\[i\]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}\[j\]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\\{\text{Vertices Reachable from} \operatorname{TS}\[j\]\\} \subseteq \\{\operatorname{TS}\[k\] \\;|\\; k = j + 1, \dots n\\}.$$

Moreover $(i, j) \in E \implies i \< j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.

# Answer
> 0 votes
**For directed graph :-**

Suppose there are 7 vertices {0,1,2,3,4,5,6} and consider the worst case where every vertex is connected to every other vertex =\>

No of edges required to reach from x to y vertices is as follows :

(6-\>6) 6 to 6 =0

(5-\>6) 5 to 6 =1

(4-\>6) 4 to 6 = (4 to 5 -\> 6) + (4 to 6-\>6) = (1+( 5 -\> 6)) + (1+0) =(1 + 1) + 1= 3

(3-\>6) 3 to 6 =(3 to 4 -\> 6) + (3 to 5 -\> 6 ) + (3 to 6-\>6) = (1+3) + (1+1) + (1+0)=7

(2-\>6) 2 to 6= 4+7+3+1=15

(1-\>6) 1 to 6= 5+15+7+3+1=31

(0-\>6) 0 to 6 = 6+5+15+7+3+1=63

So the time complexity to cover all the path to reach from 0 to 6= summation of (1+3+7+15+.....+T(n-1)+T(n))+(Total no of vertices -1) = (2^(n+1)-2-n)+(V-1)

value of n=V-1.

So final time complexity = O(2^V)

**For undirected graph :-**

Every edge will be traversed twice = 2\*((2^(n+1)-2-n)+(V-1))=O(2^(V+1))

---
Tags: algorithms, graphs, depth-first-search
---


# Question
Title: Dynamic programming , Matches game and winning strategies
The question is: There are 219 matches on a table and 2 players , each player can take 1,3 or 4 matches off the table , winner is who takes the last match. is there a winning strategy that guarantees for the **second player** to always win? .

I can't think of a way to calculate without having to do the recursion myself , now maybe 219 matches isn't that bad but if it was 1000 matches that wouldn't be so efficient.

I'd appreciate the help

# Answer
> 1 votes
When the number of matches is of the form 7$k$ or 7$k$ \+ 2, the second player wins; otherwise, the first player wins. I cannot claim to have an intuition of why this should be so, but once you write the program and notice the pattern, it is easy to prove by induction.

```
#include <stdio.h>

#define MAX_N 100

bool w[MAX_N]; /* true = player 1 wins; false = player 2 wins */

int main() {
  w[1] = true;
  w[2] = false;
  w[3] = true;
  w[4] = true;

  for (int i = 5; i < MAX_N; i++) {
    w[i] = !w[i - 1] || !w[i - 3] || !w[i - 4];
    if (!w[i]) {
      printf("Player 2 wins for n=%d\n", i);
    }
  }
}

```

The program basically hard-codes the trivial cases, then says "Player 1 wins if and only if there exists a move that takes the game into a state where Player 2 wins". Output:

```
Player 2 wins for n=7
Player 2 wins for n=9
Player 2 wins for n=14
Player 2 wins for n=16
Player 2 wins for n=21
Player 2 wins for n=23
Player 2 wins for n=28
Player 2 wins for n=30
...

```

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


# Question
Title: Let $L$ be a finite language. Show that then $L^+$ is recursively enumerable. Suggest an enumeration procedure for $L^+$
I am solving basic questions about **Recursive** and **Recursively-Enumerable** languages. I know that base on the below theorem, to prove that a language is **RE** we should define an **Enumeration Procedure** for it.

> A language is recursively enumerable if and only if there is an enumeration procedure for it.

And for the below question, I said that if $L$ is finite, it means that it is countable and for every $w ∈ L $, $|w|$ is also finite (I am not sure about this). So we can write $L$ in the below form:

$L = \\{w ∈ L | y \geqslant|w| \geqslant x \\} $

But I can not understand how to implement a procedure for it to enumerate all the strings in $L^+$.

# Answer
First start with a related task: enumerate all (finite) sequences of natural numbers. We will devide those sequences into a sequence of finite sets, and then we can enumerate all sequences by taking the sets one after another and enumerating the items in those sets.

Note that we *cannot* enumerate first all sequence of length one, then of length two, etcetera. Each of those sequences is infinite and does not end. So we have to weave the infinite sequences of infinite length into one single sequence. The process is called dovetailing.

For every sequence of numbers $(n\_1, n\_2, \dots, n\_k)$ let the complexity of the sequence be the maximum of the length of the sequence and the numbers involved: $\max \\{k, n\_1, n\_2, \dots, n\_k\\}$. Now each sequence has a complexity, and we can enumerate the sequences by increasing complexity. Starting with the empty sequence, sequences of one integer that can only be $0$ or $1$, etcetera.

The task of enumerating $L^+$ is simular. If the language $L$ is enumerable, then there is a procedure that lists its elements, $x\_0, x\_1,x\_2,x\_3, \dots$. In that way we assign a number to each word. Then sequences of numbers map to sequences in $L^+$, and we can enumerate in that way. Thus $(5,2,2,0)$ maps to $x\_5\cdot x\_2\cdot x\_2\cdot x\_0$.

Note that we will possibly find some strings in $L^+$ several times, as the decomposition might not be unique (eg., $ab \cdot a = a \cdot ba$). For enumeration that is ok, but you can drop duplicates if you want.
> 2 votes

---
Tags: automata, recursively-enumerable
---


# Question
Title: Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
> Suppose o is a map on strings to strings. For every language R, we let $o(R) := \\{o(x) : x \in R\\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the language $\\{xc o(x) :x \in A\\}$ is context-free, where A is a regular language and c is a symbol not in the alphabet of A, $\Sigma$.

The claim seems to hold when o is the reverse of a string, or the bitwise negation of it. I think a useful idea is to modify the rules for the CFG for A that are of the form $X\rightarrow aY$ for some alphabet element a and variables X and Y. So it might be useful to define Q variables in the new context free grammar, one for each state in a DFA recognizing A.

# Answer
> 1 votes
Your operation is very general, and in its generality your conjecture is not true.

For instance take for $o$ the identity, then we get the simple example $o(\\{a,b\\}^\*) = \\{wcw\mid w\in \\{a,b\\}^\*\\}$ which is not context-free.

Your examples show that a better conjecture would be that instead $\\{ x c\\, o(x^R)\mid x\in A\\}$ is context-free, where the second copy $x$ is reversed. In that case for the identity, $\\{ wcw^R \mid \dots\\}$ is nicely context-free for regular $A$.

But your statement is too general, as in that case we can take $o$ itself to be the mirror image of a string, and we are in trouble again.

The following general statement holds: if $o$ is performed by a finite state transducer, a finite state automaton with output, then $\\{ x c\\, o(x^R)\mid x\in A\\}$ is context-free, for regular $A$.

---
Tags: formal-languages, regular-languages, finite-automata, context-free, formal-grammars
---


# Question
Title: Bounded search tree: k-Vertex cover with $\Delta(G) = 2$
I am studying the book "Parametrized Algorithms" and it suggests a bounded search tree algorithm for k-Vertex Cover. Basically we look at a vertex v and say :
*Either v will cover it's incident edges or it has to be it's neighbors $N(V)$ so either $v$ or $N(v)$ will end up in the cover*.
That's 2 choices , we build a tree with these . The total running time is summarized by this relation :
$T(k) =T(k-1) + T(k-N(v)) + O(n)$
Considering the interesting case is $N(v) \geq 2$ then $k - N(v) \leq k-2$ so we get: $$T(k) =T(k-1) + T(k-2) + O(n)$$ Now the book says that ***"Vertex Cover can be solved optimally in polynomial time when the maximum degree of a graph is at most 2".***
*"Thus, we branch only on the vertices of degree at least 3, which immediately brings us to the following upper bound on the number of leaves in a search tree:"*

**Since the are no vertices with degree 3 or more how do we branch on these ?** What am I missing here?

# Answer
Once all vertices have degree $\<=2$ you don't branch on them - you just apply a standard polynomial time algorithm to solve it.

Since your graph consists of a disjoint set of cycles and line graphs, the min vertex cover for components which are line graphs would be $⌊C/2⌋$ and $⌈C/2⌉$ for cycles where $C$ is the size of the component. Therefore this can be solved in $O(n+m)$ as the problem just reduces to finding the size of components within a graph.

The recurrence given is for reducing the graph to a form where all vertices have degree $\<=2$ as you either remove the current vertex or remove 3 of its neighbours. Doing this repeatedly will eventually lead you to a graph where all vertices have degree $\<=2$
> 2 votes

---
Tags: algorithms, algorithm-analysis, parameterized-complexity
---


# Question
Title: Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
Why is this language regular: $L=\\{w~|~\\#\_a(w) \ge \\#\_b(w)\\}○\\{w~|~\\#\_a(w) \le \\#\_b(w)\\}$?

Where $\\#\_a(w)$ is defined as the number of $a$ in $w$.

Isn't that a concatenation between 2 CFL?

Thanks!

# Answer
The result of this concatenation is $\Sigma^\*$, which is regular.

I will leave it to you to verify this is the case.
> 2 votes

---
Tags: formal-languages, regular-languages, automata, context-free
---


# Question
Title: Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
> For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\\{x2y : |x| = |y|, x\in A, y\in\\{0,1\\}^\*,d(x,y) = k\\}$ is context-free for some infinite regular language $A$ over the alphabet $\\{0,1\\}$.

I think the statement is false. Intuitively, context-free grammars cannot keep track of the number of positions where strings differ, but I'm not sure how to use the pumping lemma for this case. If $k=1$, then I'd need show that the given language isn't context free for any infinite regular language $A$. If we consider the regular language generated by $0^\*$ for instance, then the language would consist of all strings $0^n 2 y$ where $y$ has length $n$ and exactly one $1$. If $A$ were finite, obviously the given language would be context-free for all $k$ because it would be finite.

> This question was based off of this other post.

# Answer
> 2 votes
Let $F=\\{x2y : |x| = |y|,\ x\in \\{0\\}^\*,\ y\in\\{0,1\\}^\*,\ d(x,y) = 1\\}$, the language of all strings $0^n2y$ where $y$ consists of $n-1$ $0$s and one $1$.

Note that $F=\\{0^p00^q20^q10^p: p\ge0, q\ge0\\}$. Here is a context-free grammar for it.
$S\to 0S0\mid 0T1$
$T\to 0T0\mid 2$

Since $F$ is context-free, the proposition in the question is true.

---

On the other hand, the language $H\_{A,k}=\\{x2y^R : |x| = |y|,\ x\in A,\ y\in\\{0,1\\}^\*,\ d(x,y) = k\\}$ is always context-free when $A$ is regular. Note that $y^R$ instead of $y$ appears at the end of each word, so that we can construct a context-free grammar by synchronizing the generation of $x$ by a right linear grammar and the generation of $y^R$ by a corresponding left linear grammar, as pointed out by Hendrik Jan.

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


# Question
Title: Show that the Hamming distance of $wx$ and $xw$ cannot be 1
> Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.

I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w\_1\cdots w\_k$ and $x = x\_1\cdots x\_n$, and proceeding with a case-based argument. Let $i$ be the unique index where the strings differ. We have the following cases: 1) $1\leq i\leq k$ and 2) $i \> k.$ We also need to consider the subcases a) $n \< k$ and b) $n \ge k$ for each case. In the first case (case 1 a), $x\_1\cdots x\_n = w\_1\cdots w\_n$ and $w\_1\cdots w\_{i - n} = w\_{n+1}\cdots w\_i$. Also, $w\_{i-n + 1} = w\_{i+1}, \cdots, w\_{k-n} = w\_k.$ This argument seems very tedious, so I was wondering if there's a better argument?

# Answer
**Lemma:**

The parity of the Hamming distance between two strings is the parity of the total number of $1$s.

**Proof:**

If you toggle any bit in any of the strings, the parity of the distance changes. Start from two "all zeroes" strings and toggle all it takes to get to the targeted strings.

**E.g.:**

$$00000, 00000\to0\to0\\01000, 00000\to1\to1\\01000, 00100\to2 \to0\\01000, 10100\to3\to1\\\\01000, 11100\to2\to0\\\cdots$$

---

The main claim follows because the total number of $1$s in $wx$ and $xw$ is perforce even.
> 3 votes

# Answer
$w$ and $x$ are binary strings.

Clearly $|wx|=|xw|$ and $|wx|\_0=|xw|\_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)\[i\]\ne(xw)\[i\]$, $(wx)\[1..i-1\]=(xw)\[1..i-1\]$, and $(wx)\[i+1..n+k\]=(xw)\[i+1..n+k\]$.

Wolog, assume $(wx)\[i\]$ is $1$, and thus $(xw)\[i\]$ is $0$. Now,

$$\begin{align}|wx|\_0 &= |(wx)\[1..i-1\]|\_0 + 0 + |(wx)\[i+1..n+k\]|\_0\\ |xw|\_0 &= |(xw)\[1..i-1\]|\_0 + 1 + |(xw)\[i+1..n+k\]|\_0\\ &= |(wx)\[1..i-1\]|\_0 + 1 + |(wx)\[i+1..n+k\]|\_0\\ \end{align}$$ which contradicts $|wx|\_0=|xw|\_0$.

More generally, let $w$ be any binary string and let $w'$ be any permutation of $w$. Using a generalization of the above argument, show that the Hamming distance between $w$ and $w'$ is even.
> 2 votes

---
Tags: formal-languages, formal-grammars, strings, hamming-distance
---


# Question
Title: is there a non-context free language A such that A1 is context free?
> Is there a non-context free language A over the alphabet $\\{0,1\\}$ such that $A1 := \\{a1 : a\in A\\}$ is context free?

I was thinking of the language $A = \\{0^n 1^{n-1} : n \> 0\\}.$ Unfortunately, this language is context-free. I’m not sure if one might be able to show that context-free languages are closed under the operation of removing the last bit from every such nonempty string.

# Answer
No. Note that $A = A1 / \\{1\\}$, the right quotient of $A1$ over $\\{1\\}$. Since $\\{1\\}$ is a regular language, we know that $A$ is context-free when $A1$ is context-free, thanks to this post that shows the right quotient of a context-free language over a regular language is also context-free.
> 1 votes

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


# Question
Title: CNF-SAT time complexity and input processing
Boolean Satisfiability (CNF-SAT) problem in $n$ variables may contain a CNF formula with $O(2^n)$ clauses in the worst case.

My question is: Wouldn't a program reading a CNF formula have to asymptotically run $O(2^n)$ steps? Is the search for a sub-exponential CNF-SAT algorithm moot?

# Answer
No. The meaning of "polynomial-time" is "polynomial in the length of an input". We can still search for an algorithm that is efficient on short inputs.

For instance, suppose we have CNF formulas with $n$ variables and only $10n$ clauses. No one knows how to solve this in time polynomial in $n$.
> 2 votes

---
Tags: time-complexity, np-complete, satisfiability
---


# Question
Title: How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
Let $L$ be a regular language.

Define: $half(L)=\\{x|xy\in L,|x|=|y|\\}$

Prove that $half(L)$ is regular as well.

I have seen a hard proof by using the DFA A of L, building a NFA B (such that every transition from the stating state to the next one with the word $x$ will exist iff $\exists y$ s.t $|x|=|y| , \delta\_A(q,y)\in F\_A$).

Then using the product automaton of A and B to solve it.

I wonder if there is a easy proof for this one.

Thanks a lot!

# Answer
If $L$ is regular , then FirstHalves or $Half(L)$ is also regular.

**Algorithm:**

1. Design $DFA, M$ of language $L$
2. Find the reversal of $DFA$ ,$M$ , say $N.$
3. Traverse $M$ for one transition (for given $\Sigma$ ) and $N$ for one transition (for $\Sigma$ ) , and repeat the process.
4. If We reach at common states, Mark them as New finals in $DFA$, $M$ (remove old final and do minimization )
5. Result is $DFA$ of $Half(L)$ or $FirstHalve(L)$

<sup>\[Note: In Short, design $DFA$ for $L,$ traverse from both directions (start and final),if reach at common states with same number of transitions, make them as new finals, result will be $DFA$ for $Half(L)$ \]</sup>

---

**Example:** Suppose $L=\\{ab,bb\\},$ $Half(L)=\\{a, b\\}$

**Step1.** Design $DFA, M$ for $L$

**Step2.** Reversal of $M$ which becomes $NFA,$ $N.$

**Step3.** $\delta(q\_0,b)=q\_1$ for $M$ and $\delta(q\_2,b)=q\_1$ for $N.$

**Step4.** We see that $q\_1$ state is common for both $M$ and $N.$ So new final state is $q\_1.$

**Step5.** New $DFA$ of $Half(L)$ or $FirstHalve(L)$ which accepts only $\\{a, b\\}$

<sup> Miscellaneous Examples try yourself: * $L=a^∗$ , then $half(L) =a^∗$
* $L=a(aa)^∗$, then $half(L) =\phi$
* $L=a^∗b^∗$, then $half(L) =a^∗b^∗$

</sup>
> 1 votes

# Answer
The language $\mathrm{half}(L)=\\{x\mid xy\in L,|x|=|y|\\}$ can be quite complicated, compared to the original language $L$. I am afraid that **there is no simple construction and we have to keep track of the behaviour of the automaton both forward and backward**, which is the product automaton you are referring to.

Let me walk through an example, take $L = (aaa)^\*b(cc)^\*$, a rather innocent language, which can be accepted by a five-state automaton.

We can manually check that $\varepsilon$, $a$ and $a^4$ are *not* in $\mathrm{half}(L)$, where as all other strings in $a^\*$ are $\mathrm{half}(L)$, as follows: $aa|ab$, $aaa|bcc$, $a^5|a{\cdot}a^3b$, $a^6|a^3bc^2$, $a^7|a^2bc^4$, $a^8|a{\cdot}bc^6$, etcetera. (That is not a proof, I know.) Turn to strings of the form $a^\*b$. They can only belong to $\mathrm{half}(L)$ if there exists a "devision" of the form $a^{3k}b|c^{2\ell}$. This means that $3k+1$ should be even, or $k$ is odd. Then we get $a^3b$, $a^9b$, $a^{15}b$, ... in $\mathrm{half}(L)$. I will not repeat this for strings ending in $c$'s, but for $a^{3k}bc^{m}|c^{n}$ we get the same restriction on $k$ (and no restriction on $m$).

Thus $\mathrm{half}(L)= a^\*\setminus\\{a^0,a^1,a^4\\} \cup a^3 (a^6)^\*b c^\*$.

Now the automaton version, using the forward-backward method.

The product construction starts with two states in the automaton, the initial and final states. It follows the first state as in the original automaton, but for the second we follow an edge (any label) backwards, and we know that from that second state we can reach the final state in exactly the number of steps we have done so far. Accept when both states are equal. The "hard proof" you mention. Here is what I got. Choosing the backward edge is non-deterministic (several edges may point to the state) and the result is quite unclear. Note the large blop of useless states at the top.

This can be improved in this case by first determinizing the backward automaton. We keep track of sets of (backward) reachable states. Now accept if the forward state is an element of the backward set. (eg., $0\in S=\\{0,1,4\\}$.) Lower diagram is the final result of this "deterministic" product construction. Here a line of useless states at the bottom that can be removed without changing the language.

To keep the answer of reasonable size, the figures are reduced. If you click on the image you get again reduced size. Remove the final 'm' from the filename and it will be better readable.

note. In the answer to Is Lhalf={ w :for some z∈L,x∈Σ∗,z=wx∧|w|=|x| } regular? \[duplicate\] a slightly different construction is given. Rather than forward-backward simulation, the automaton guesses the middle state $q$ and simulates two parallel forward computations, the second one starting in $q$. When the first computation ends in $q$ and the second in a final state, we accept.
> 1 votes

# Answer
I guess this question Prove half(L) is regular is the same.

There are several ways to prove a language is regular:

1. By building DFA, NFA, or Regular Expression (which is the case in your question).
2. Using the Myhill-Nerode theorem. However, in general, it's used only to prove a language isn't regular.
3. By contradiction. That is if you assume that the language isn't regular and show that this leads to another known regular language to be 'not regular' then your language is regular.
4. By using closure properties. That is if you show that its complement, reverse, etc... is regular then the language is regular.

***Note:*** You can't use the pumping lemma to prove a language is regular.

In the end, I don't assume there is a simpler way to prove your language is regular using one of the above options. Since you almost know nothing about that language it's hard to use the above strategies.
> -1 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata, context-free
---


# Question
Title: Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?
I was studying Turing languages for an exam and I came up with this problem for wich I haven't found a solution online. This is my question:

> Let's say we have $L\_1, L\_2 \subseteq\\{0,1\\}^\*$. $L\_1$ is Turing-recognisable and $L\_2$ is Turing-decidable.
>
> Is $L\_u = L\_1 \cup L\_2$ decidable? Is it recognisable?

My guess is that $L\_u$ is just recognisable. Here is my attemp on proving it.

A language $L \subseteq \\{0,1\\}^\*$ is decidable if and only if both $L$ and $L^c$ are recognisable (where $L^c = \\{0,1\\}^\* \setminus L$). My idea was to prove that $L\_u$ is recognisable and $L\_u^c$ is not.

In our case $L\_u$ is recognisable (trivial) and $L\_u^c = (L\_1 \cup L\_2)^c = (L\_1^c \cap L\_2^c)$. We know that $L\_1^c$ is recognisable and $L\_2^c$ is not-recognisable (or else, $L\_2$ would have been decidable). At this point I got stuck. I'm pretty sure that $L\_u^c$ is not-recognisable, but I found this example:

> Let $L\_x = \\{stuff\\} \cup L\_1$ be a not-recognisable language and $L\_1$ the language we defined above. The intersection $L\_x \cap L\_1 = L\_1$ wich by definition is recognisable.

Follow up question:

> Can we sometimes recognise the intersection between a not-recognisable language and a recognisable one? In other words, is my proof wrong somehow?

# Answer
> 3 votes
The answer to the question "Is $L\_u = L\_1 \cup L\_2$ decidable?" is "sometimes".

For a positive example, let both $L\_1$ and $L\_2$ be the empty language.
For a negative example, let $L\_1$ be Turing-recognisable but not Turing-co-recognisable such as the language of halting Turing machines, and let $L\_2$ be the empty language.

---

The answer to the question "Is $L\_u = L\_1 \cup L\_2$ Turing-recognisable?" is "Yes". In fact, we have a stronger statement below.

Proposition: the union of two Turing-recognisable languages are Turing-recognisable.
Proof: Suppose $L\_1$ and $L\_2$ are recognised by Turing machine $T\_1$ and $T\_2$ respectively. Let $T\_3$ be the Turing machine that upon input $s$ simulates $T\_1$ and $T\_2$ simultaneously. If and only if either $T\_1$ or $T\_2$ accepts, $T\_3$ accepts. Then $T\_3$ accepts the union of $L\_1$ and $L\_2$.

---

The answer to "Can we sometimes recognise the intersection between a not-recognisable language and a recognisable one?" is "yes".

For example, let the recognisable one be the empty language.

# Answer
> 2 votes
A few things,

* It's hard to find what your proof attempt is trying to do. I know you're stuck, but you should at least have a strategy of what you want to do. In your proof, a good idea is to use AFSOC and look for a contradiction.
* The online theorem you found makes no sense, if we have $L\_x = S \cup L\_1$ but we don't know anything about $L\_1$, I'm not sure why there is a claim about recognizability.

So we want to know if $L\_1 \cup L\_2$ is decidable, right? Intuitively, this is probably not true, because if $L\_1$ is just recognizable, adding a decidable language to it should probably not in general make it decidable all of a sudden (it can though, but remember if we have no assumptions about $L\_1, L\_2$, then this has to hold in all cases).

So normally when we have an intuition that something *doesn't* work, we use contradiction or a counterexample.

You can have 2 options here, so you can either

1. AFSOC $L\_u = L\_1 \cup L\_2$ is decidable, and try to show a contradiction, most likely that $L\_1$ is decidable.
2. Find a counterexample

I think 2 is much easier to find. You can just take any recognizable (but not decidable) language $L\_1$, and then take a trivial subset that is decidable, let's say a single element, to make $L\_2$. Then $L\_2$ is decidable, but $L\_1 \cup L\_2 = L\_1$ which is not decidable. (note that we can take some element, because if $L\_1$ is empty, then it cannot be undecidable).

---
Tags: formal-languages, turing-recognizable
---


# Question
Title: Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed
I came here to ask for help with a two-tape Turing machine for the following language.

$L = \\{ a^{n^2} | n \ge 0 \\}$

I tried following the advice on this site: Turing machine that accepts L={an2|n≥1} \[duplicate\]

because it was the one with the most answers, but I'm still not sure about the algorithm.

If I understood it correctly, both tapes start at the respective beginnings (the 1st tape starts at the first symbol, and the second tape starts at the first "cell" in the tape). So, we move both heads by one, until we get to the end of the counter tape. Then, we add two symbols (markers) to the last two cells on the right of the tape.

My questions are, what do I do after adding two markers to the last two cells on the right of the tape? Do I return both heads to the beginnings of the respective tapes? Also, do I have to go to the end of the counter tape on each iteration, or do I just go to the first marker symbol, and then go back two steps and place markers there?

# Answer
I'll let the mods decide if it's a duplicate or not, but I do agree that the explanations could warrant a bit more explicit explaining.

1. You have two tapes, one of them is the one with the input, and the other one is to help us advance by $1, 3, 5, \cdots.$ since as they mentioned, $1 + 3 +5 + \cdots (2n+1) = (n+1)^2$
2. The idea is that the tape that's helping us advance by odd numbers is doing a bunch of bookkeeping to make sure we only advance by odd numbers.

I'll explicitly illustrate how this works for a few runs

We are at an unvisited cell in our first tape, accept if the second input is done (this is up to you how to do it, but you can just move one to the right, check for end, and then come back if it's not the end). As you will see later, you might have to modify the first case a bit depending on how you think about it.

```
| | | | | |
 ^
|a|a|a|a| |
 ^

```

Add two markers

```
|x|x| | | |
   ^
|a|a|a|a| |
 ^

```

Go back to the start

```
|x|x| | | |
 ^
|a|a|a|a| |
 ^

```

This is where we can have off-by-one errors, but I'll be very explicit here.

1. Advance tape 2
2. If tape 1 has an x, then advance tape 1 and repeat

```
|x|x| | | |
   ^
|a|a|a|a| |
   ^

```

I'll skip a step. Now, we are at an unvisited cell. Remember we always advance tape 2, but we don't do the cycle again unless tape 1 sees an x. In this case, we advanced tape 2 but tape 1 did not see an x.

```
|x|x| | | |
     ^
|a|a|a|a| |
       ^

```

Now, we would check tape 2 to see if the input is done. In this case we are done so we accept, but let's just pretend tape 2 had more, then we would repeat our steps for extending the markers on tape 1.

So we fill two more x's

```
|x|x|x|x| |
       ^
|a|a|a|a|a|
       ^

```

And we go back and start again

```
|x|x|x|x| |
 ^
|a|a|a|a|a|
       ^

```

Hope this helps. There are a few ways to go about doing the off-by-one errors, which I suspect you're confused about, but I think explicitly showing these should be able to get you to your understanding.
> 0 votes

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


# Question
Title: Can computer vision process 3D “images” directly?
Most CV algorithms deal with 2D images produced by cameras. However, sometimes we need to process 3D “images” (I don’t know how to call them). For example, CT and MRI produce 3D radiographs. Traditionally these radiographs are cut into many slices for doctors to read. Because human eyes can only see 2D images (and most people lack the ability to comprehend complex 3D structures), doctors need to analyze them slice by slice, which is very time consuming. Computers on the other hand can process 3D patterns as efficiently as 2D. So can we design a CV algorithm to process 3D images directly? For example, instead of cutting the radiographs into many slices and mapping the edges (which marks the cross sections of blood vessels), the algorithm maps the surface of blood vessels directly. Will such direct 3D processing be more efficient and more accurate than 2D processing?

# Answer
This is a *very* general question, so I'll give some ideas.

The short answer is yes. If you're talking about the "processing" as some function, then yes, we can use some function $f\_3: \mathbb{R}^3 \to A$ in our computer algorithm rather than a $f\_2: \mathbb{R}^2 \to B$. In fact, there are many computer algorithms that already do this. In fact, you can give any $n$-dimensional input, and have some algorithm process the $n$ inputs into anything you want (e.g. lots of econ models do this).

In terms of efficiency, it depends what you consider efficiency. But I think what you're trying to get at is, "*Is there a 2D algorithm that can be more efficient if done in 3D?*", and I would say no, because 2D algorithms are designed for 2D, and 3D are designed for 3D. E.g. if you want to do edge detection in 2D, it doesn't even make sense to use it in the context of 3D (there would be 3D collision or edge detection instead, a different version).

However, to entertain your question about efficiency, there are ideas of "creating features" from lower dimensional data, moving it to upper dimensional data and then doing analysis. PCA and neural networks are some examples that do that, and are sometimes very good at it. E.g. the classic is number digit recognition, where the 2D problem is quite difficult, but you might be able to find more patterns in higher dimensions and recognize the numbers more easily (neural networks are great for this).

Also, even though you might think of your vision as 2D (because that's how cinema portrays it), you have depth perception and many other senses that help you perceive 3D, which actually would make your visual senses a 3D rather than 2D function as you might think.

Doctors look at CAT scans in 2D because it might help them target certain areas they want to look at more. There are of course software that can process these slice by slices into 3D, and I would bet doctors use those as well. Also, you have to remember that CAT scans are "looking inside" of something in the first place, so it might be more helpful to see cross-sections rather than the whole thing.
> 2 votes

---
Tags: computer-vision, pattern-recognition
---


# Question
Title: How much of a difference does bottom-up vs top-down make in actual practice when implementing dynamic programming?
In actual industry use, does bottom-up provide a significant speed-up compared to an equivalent top-down approach to a dynamic programming algorithm?

Assume that the top-down and bottom-up implementations both have the same asymptotic runtime.

Do the constants really make a difference? Or does this all depend on the specifics of the algorithm without any general conclusions?

# Answer
Whether you care about such a thing depends on:

1. The specifics of the code at hand.
2. Whether the application is time-critical.

In other words, there is no general conclusion here. Luckily, the vast majority of applications are not time-critical so we don't care.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What would be an easy approach for this Turing machine description?
I am tasked to design a turing machine which calculates the function:

$f(n) = 2n \iff 0 \le n \le 2$, or $4n+2 \iff n\>2$

Where "n" is given in **binary**.

Now, I'm not in the slightest way sure how to do this. This is what I came up with so far:

I tried checking if a binary number is bigger than two. First, I thought that a binary number will be bigger than two if it contains more than two "1". However, this is not really the case always because 100 contains only one "1" and is bigger than two. I tried going to the end of the input string and checking the number of 1s and 0s backwards, but it ended up being even more confusing.

The only thing I have surmised until now is that if there is more than one "1", the number is surely bigger than two. That would be easy to test. Unfortunately, depending on its position, if it had only one "1", it still could be a bigger number than two.

I tried everything that popped into my mind but I'm not sure how to proceed here. Can someone give a hint, or a description of an algorithm which tests what boundary the number belongs to? I can compute the rest of the computations myself.

# Answer
> 0 votes
Instead of just checking "if a binary number is bigger than two", check whether the input is 0, 1, 2 or "big", where "big" means greater than 2.

---

Assume the most significant digit in the input is to the left.

Let the Turing machine (TM) read the input from left to right, remembering the value of the binary number read so far, which is 0, 1, 2 or big. In other words, "0", "1", "2" and "big" will the possible states while the TM is reading the input.

The state transitions are quite easy. For example, reading 0 will update state "1" to "2". For example, "big" will always result in "big".

Once the blank symbol is encountered, the TM will write 0 if the state is not "big", which means $n\to 2n$, and write 1 and then 0 otherwise, which means $n\to 2n+1\to4n+2$.

```
; Run the following code at https://morphett.info/turing/turing.html.
; Solve https://cs.stackexchange.com/questions/152480

; Machine starts in state 0.
; Always moves to the right.
; Never overwrites the input.

; <current state> <current symbol> <new symbol> <direction> <new state>
; * means the new symbol is the same as the current symbol.

0 0 * r 0
0 1 * r 1

1 0 * r 2
1 1 * r big

2 0 * r big
2 1 * r big

big 0 * r big
big 1 * r big

; _ is the blank symbol.
0 _ 0 r halt
1 _ 0 r halt
2 _ 0 r halt
big _ 1 r 1_appended
1_appended _ 0 r halt

```

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


# Question
Title: Prove big O notation for $\log(n!)$ without applying Stirling's formula
I want to prove that, $$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$ The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow.

Can somebody please guide me towards it?

# Answer
> 2 votes
A nice method is : $$ \begin{align\*} \log n! & = \log \prod\_{\psi=1}^n \psi \\ & = \sum\_{\psi=1}^n \log \psi \\ & \sim \int\_1^n \log \psi \\; \mathrm d \psi \\ & = \psi \log \psi - \psi \Biggr|\_{1}^{n} \\ & = n \log n - (n - 1) \end{align\*} $$ If we had used stirling's approximation instead, we would have received $$ \log n! = n \log n - n + \Theta(\log n) $$ Alternate methods involve

* The method present in this math.se page.
* Using $n! = \int\_0^\infty x^n e^{-x} \\; \mathrm d x$

# Answer
> 3 votes
Note that $\log n! = \sum\_{k = 1}^n \log k$. Then $$\sum\_{k = 1}^n \log k = \int\_1^{n + 1} \log \lfloor x \rfloor dx \le \int\_1^{n + 1} \log x dx = (n + 1) \log (n + 1) - n,$$ and $$\sum\_{k = 1}^n \log k = \int\_0^{n} \log \lceil x \rceil dx \ge \int\_0^{n} \log x dx = n \log n - n .$$

# Answer
> 2 votes
As far as I see, the solutions have all used integration. We can easily do without. Of course $\log n! = \sum\_{k=1}^n \log k$.

For the upper bound use $\log k \le \log n$ for $1\le k \le n$, so $\sum\_{k=1}^n \log k \le \sum\_{k=1}^n \log n =n \log n$.

For the lower bound, observe that $\log \frac n2 \ge \frac 12{\log n}$ for $n\ge 4$. Thus $\sum\_{k=1}^n \log k \ge \sum\_{k={\frac n2}}^{n} \log k \ge \frac n2 \log \frac n2 \ge \frac n4 \log n$.

# Answer
> 1 votes
For complete rigor,

$$x-1\le\lfloor x\rfloor\le x$$

so that by monotonicity of the logartihm

$$\log(x-1)\le\log\lfloor x\rfloor\le \log x.$$

Hence by integration from $2$ to $n+1$,

$$\int\_1^n\log x\\,dx\le\sum\_{k=2}^n\log k\le\int\_2^{n+1}\log x\\,dx$$

and

$$n\log n-n+1\le\log n!\le(n+1)\log(n+1)-n+1-2\log2.$$

# Answer
> -1 votes
Without any hard maths: log n! = log 1 + log 2 + log 3 + … + log n. We are adding n numbers, each at most log n, so the sum is at most n log n.

On the other hand, log ( sqrt (n)) = (log n) / 2, so all but sqrt(n) of the numbers we are adding are at least (log n) / 2, giving a lower bound. For n\>= 4, sqrt(n) \<= n/2 so we are adding at least n/2 numbers, each at least (log n) / 2, for a total of (n log n) / 4.

---
Tags: big-o-notation, factorial
---


# Question
Title: Convolutional Neural Network : how to ignore swaths of uninteresting areas? Or make it focus to interesting regions only?
Imagine you trained a text-from-image reader, similarly to the one described in this article https://medium.com/analytics-vidhya/image-text-recognition-738a368368f5

Now you want to port the trained network, or at least the bottom CNN layers, to process huge images (large photograph with tiny street name in the corner. Or multiple street labels which can be found anywhere in the image). If the kernels are eg. 50x50 pixels, each having 200 features, and you shift-apply every 2 pixels... on a 4K image, it's a huge amount of processing.

What are the techniques to quickly throw away areas where surely there is nothing of interest, and only CNN-process the regions that have something promising on them?

OR, eg. is there any technique whereby each layer downsamples,keeps interesting features, downsamples... AND in the end the thing won't be like grid-sensitive? (like if convolution-shift is too large, eg. kernel size/2, and feature is a couple of pixels off, doesn't fall on the grid) Is there a rule-of-thumb kernel\_size / convolution\_shift ratio people tend to plug in?

OR, is there a technique that works with layers of List\<(object,position)\> instead of float\[with,height,feature\]? Eg. I take a large photo, and want to find all letters in the photo. Then, knowing Collection\<letter+position\> find all street names, based only on the letters I found, I don't care about pixels, or a big piece of sky on that level.

# Answer
Object detection is responsible for finding regions of interest in a large image. You will have to train it on labelled images, that are labelled with bounding boxes on all of the regions of interest in each of the images in the training set.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Compute a commutative and associative operation on n-2 arguments efficiently
Considering a function $f$ such that: $$ f(x\_1, x\_2, x\_3) = f(f(x\_1, x\_2), x\_3) = f(x\_1, f(x\_2, x\_3)) $$ and $$ f(x\_1, x\_2) = f(x\_2, x\_1) $$

and a set $X = \\{ x\_1, \dots, x\_n \\}$; how to compute $$f(x\_1, \dots, x\_{i - 1}, x\_{i + 1}, \dots, x\_{j-1}, x\_{j+1}, \dots, x\_n)$$ for all pairs $i, j \in 1, \dots, n$, $i \< j$ while minimizing the number of calls to $f$?

* Only $f(x)$ and $f(x, y)$ can be computed
* $f^{-1}$ is not defined

---

For example, let $f$ be addition, i.e, $f(x\_1, x\_2, \cdots, x\_n)=x\_1+x\_2+\cdots+x\_n$. However, only calls to $f$ with one or two arguments are allowed, i.e $f(x)=x$ and $f(x\_1,x\_2)=x\_1+x\_2$. In particular, neither subtraction nor negation is allowed. The problem is to compute all sums of $n-2$ numbers among the given $n$ numbers with the least number of additions. There are $n(n-1)/2$ such sums.

# Answer
(1) You can compute $f(x\_1,\dots,x\_{i-1})$ for all $i$ with $n-2$ calls to $f$. (Simply iterate over $i:=1,\dots,n$.)

(2) Then, using (1), you can compute $f(x\_1,\dots,x\_{i-1},x\_{i+1},\dots,x\_{j-1})$ for all $i,j$ with $n(n-1)/2$ more calls to $f$. (For each $i$, iterate over $j:=i+2,\dots,n$.)

(3) You can also compute $f(x\_{j+1},\dots,x\_n)$ for all $j$ with another $n-2$ calls to $f$. (Iterate over $j:=n,\dots,1$.)

(4) Finally, using (2) and (3), you can compute $f(x\_1,\dots,x\_{i-1},x\_{i+1},\dots,x\_{j-1},x\_{j+1},\dots,x\_n)$ for all $i,j$ with another $n(n-1)/2$ calls to $f$.

In all, this uses about $n^2+n$ calls to $f$.

This is within a factor of 2 of the best possible, as you need to output $n(n-1)/2$ different values, so obviously you'll need to make at least $n(n-1)/2$ calls to $f$.
> 2 votes

# Answer
(Motivation: let $h = n/2$.
Given $f\_{ih} = f(x\_i\dots x\_{h-1}) \text{ and } f\_{hj} = f(x\_h\dots x\_j)$ (precomputed in about $n$ evaluations of $f$),
$f(x\_{i+1}\dots x\_{j-1})$ can be computed as $f(f\_{(i+1)h}, f\_{h(j-1)})$ for all $i\lt h\lt j$.
This saves ?$\frac{(n-2)(n-3)} 2 - n$? evaluations.
Similarly for $q = n/4, 3q = h+q, o = n/8, 3o = q+o, 5o = h+o, 7o = 3q+o, \dots$.)

---

The above promises to be a bookkeeping headache.
Instead, pre-compute $f(x\_{k2^l}\dots x\_{(k+1)2^l-1}), 0\<l\le\lg\_2(n), 0\<k\<\frac n {2^l}$ in about n evaluations of $f$:
Any $f\_{ij}$ can be computed in less than $2\lg\_2(n)$ evaluations.

## An example

Let $f\_{\boxed {lk}} := f(x\_{k2^l}\dots x\_{(k+1)2^l-1})$

Suppose $n = 13$, then $\lg\_2(n) \approx 3.7$. Since $l$ is an integer and $0 \< l \leq 3.7...$), this means $l$ iterates through $1, 2, 3$.

## $l = 1,\quad 2^l = 2$

$0 \< k \< \frac n {2^l} = \frac {13} 2 = 6.5$

So $k$ iterates from $1$ to $6$ inclusive

$$ k=1,\quad f\_{\boxed {11}} = f(x\_2, x\_3)\\ k=2,\quad f\_{\boxed {12}} = f(x\_4, x\_5)\\ k=3,\quad f\_{\boxed {13}} = f(x\_6, x\_7)\\ k=4,\quad f\_{\boxed {14}} = f(x\_8, x\_9)\\ k=5,\quad f\_{\boxed {15}} = f(x\_{10}, x\_{11})\\ k=6,\quad f\_{\boxed {16}} = f(x\_{12}, x\_{13})\\ $$

## $l = 2,\quad 2^l = 4$

$0 \< k \< \frac n {2^l} = \frac {13} 4 = 3.25$

So $k$ iterates from $1$ to $3$ inclusive

$$ k=1,\quad f\_{\boxed {21}} = f(x\_4 \dots x\_7)\\ k=2,\quad f\_{\boxed {22}} = f(x\_8 \dots x\_{11})\\ k=3,\quad f\_{\boxed {23}} = f(x\_{12} \dots x\_{15})\\ $$

## $l = 3,\quad 2^l = 8$

$0 \< k \< \frac n {2^l} = \frac {13} 8 = 1.625$

So $k$ iterates from $1$ to $1$

$$k=1,\quad f\_{\boxed {31}} = f(x\_8 \dots x\_{15})$$
> 1 votes

# Answer
Count how many times each $x\_i$ occurs in the argument list.

Suppose $X\_1$ is the set of $x\_i$ that occur once, $X\_2$ is the set of $x\_i$ that occur twice, ..., $X\_m$ is the set of $x\_i$ that occur $m$ times, ... etc.

Suppose $y \in X\_j$, eventually you will have to evaluate $f(y)$ $j$ times. So instead of computing $f(y)$ $j$ times, just compute it once and save the result (in a dictionary, map, w/e).

Suppose $X\_j = \\{a, b, c\\}$. You will have to evaluate $f(a, b, c)$ $j$ times. Instead of computing it $j$ times, evaluate it once and save the result.

Suppose $d \in X\_{2^p}$ for some integer $p$. Let

* $d\_0 := f(d)$
* $d\_1 := f(d, d) = f(f(d), f(d)) = f(d\_1, d\_1)$
* $d\_2 := f(d, d, d, d) = f(f(d, d), f(d, d)) = f(d\_1, d\_1)$
* ...
* $d\_p := f(\underbrace{d, d, ..., d}\_{2^p\ \text{times}}) = f(d\_{p-1}, d\_{p-1})$
> 0 votes

---
Tags: algorithms, optimization, recursion
---


# Question
Title: What is different between two classes are 'incomparable' or two classes are 'not equal'?
Arora and Barak states (p. 230) the following:

> What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete problems. There are also oracle results showing that $NP$ problems require exponential time on quantum computers \[BBBV97\]. So most researchers believe that $NP \subsetneq BPP$. On the other hand, there is a problem in $BQP$ (the Recursive Fourier Sampling or RFS problem \[BV93\]) that is not known to be in the polynomial-hierarchy, let alone in $NP$. **Thus it seems that BQP and NP may be incomparable classes**.

My question is: what is different between two classes are 'incomparable' or two classes are 'not equal'?

I knew that it is possible that $P \neq NP$, but $P \subsetneq NP$, so classes P and NP are comparable. Also, I am aware that when two classes have different type then they are incomparable, e.g. one is decision problems (NP) and another is counting problems (#P), then they are not comparable. But BQP and NP are both decision class of problems, so it is not clear to me why Arora and Barak said that both classes could be incomparable. For example, why not saying they are 'not equal' instead of 'incomparable'?

# Answer
Two sets $A$ and $B$ are *comparable* if $A \subseteq B$ or $B \subseteq A$. However, if $A \neq B$, it could be that $A \subsetneq B$ or $B \subsetneq A$.

If $A \neq B$ and $A$ and $B$ are comparable, we know that (wlog) all elements of $A$ also are in $B$, and this is an interesting piece of information.

If $A$ and $B$ are *incomparable* they are necessarily not equal ($A \neq B$). It also means that there is an element in $A$ that is not in $B$, and an element in $B$ that is not in $A$.

For example, since $P \subseteq NP$, we know that every problem in $P$ has a polynomial-time verification since every fact about problems in $NP$ is also true about problems in $P$.
> 1 votes

---
Tags: complexity-theory, complexity-classes, quantum-computing
---


# Question
Title: Difference between two's complement and sign-and-magnitude
I'm just starting to learn about representing numbers in sign-and-magnitude and two's complement, and both as signed binary integers two's complement if representing a negative number I should invert all bits and add one, while sign-and-magnitude represents negative numbers with the first bit as a sign bit, but is it possible whether I can tell if a number is represented in sign-and magnitude or two's complement from just looking at it?

# Answer
Every string of bits can be interpreted both as a two's complement or a sign-and-magnitude number. So the answer is clearly no.

\[Usually, sign-and-magnitude allow negative zero; if not in your context, then you could say that $100\cdots0$ is a two's complement number, anyway.\]
> 1 votes

---
Tags: binary
---


title: nth Permutation generator

text:
# Question
Title: nth Permutation generator
I'm just trying to write a little algorithm. I've got nine objects, so there's 9! permutations. My question is, is there a way of turning a number from 1 to 9! into a permutation?

for example, f(1)=\[1,2,3,4,5,6,7,8,9\], f(2)=\[1,2,3,4,5,6,7,9,8\] or something similar.

Each number should have a unique ordering, and vice versa.

I know it's possible to write out everything into an array, but that's very memory taxing. Is there a simpler way of doing it?

# Answer
Use the factorial number system.

See also https://oeis.org/wiki/Ranking\_and\_unranking\_functions, Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time for more background.
> 2 votes

---
Tags: algorithms, permutations
---


# Question
Title: Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
I have to find a CFG for the given expression:

$L = \\{a^wb^xc^yd^z | w + x = y + z\\}$

This is what I've tried so far:

S -\> aSd | B | ϵ

B -\> bBc | ϵ

It works for expressions like: aabcdd, abbbcccd

However, using my grammar I wouldn'd be able to generate strings like: aaaacddd, abbddd, which, I assume, the language L should contain.

# Answer
> 3 votes
The constraints on $w, x,y, z$ are not given, I choose everyone $\geq 0.$

The strings could have equal $a$ and equal $d,$ equal $b$ and equal $c,$ equal $b$ and equal $d,$ equal $a$ and equal $c $ etc(since $w, x,y, z\geq 0.$). So the grammar will be only this equal case:

$S\to aSd. $

$X\to aXc. $

$Y\to bYd. $

$Z\to bZc. $

Now from start symbol we could go either $X, Y \text{or} Z$ directly. Then $S$ becomes now $S\to aSd/X/Y/Z.$

Now for $X$ when are generating $a, c$ we are generating $b, c$ in middle, but $b, c$ are generated by $Z.$ So $X$ becomes $X\to aXc/Z.$

Same things happens with $Y$, So $Y$ becomes $Y\to bYd/Z.$

Now collectively all things together,

$S\to aSd/X/Y/Z.$

$X\to aXc/Z.$

$Y\to bYd/Z.$

$Z\to bZc/\epsilon$

<sup>

**Note:-** For $w, x,y, z\geq 1,$

$S\to aSd/aXd/aYd/aZd.$

$X\to aXc/Z.$

$Y\to bYd/Z.$

$Z\to bZc/bc$

</sup>

# Answer
> 1 votes
This answer on purpose is more complicated than necessary. My goal is to apply a general property of regular and context-free languages, see: Prove that the equal-length concatenation of regular languages is context free.

> Given regular languages $A$ and $B$, then $A@B=\\{xy\mid x\in A, y\in B \text{ and } |x|=|y|\\}$ is context free.

The solution is to generate $A$ with a right-linear grammar, and to generate $B$, this time backwards, with a left-linear grammar. Then the two derivations can be synchronized, which ensures the equal length requirement. The new grammar is in fact linear, a subclass of the context-free grammars.

In this example we choose the following two grammars for $A =a^\*b^\*$ and $B = c^\*d^\*$, with axioms $S$ and $X$ respectively.

$S \to \varepsilon \mid aS \mid bT$, $T\to \varepsilon \mid bT$

$X \to \varepsilon \mid Xd \mid Yc$, $Y\to \varepsilon \mid Yc$

Synchronize the two grammars, using pairs of nonterminals (which form a new alphabet of nonterminals). For each of the sides we apply its possible productions from the original right/left linear grammar.

$\langle SX \rangle \to \varepsilon \mid a\langle SX\rangle d \mid a \langle SY\rangle c\mid b\langle TX\rangle d \mid b \langle TY\rangle c$

$\langle SY \rangle \to \varepsilon \mid a\langle SY\rangle c \mid b \langle TY\rangle c$

$\langle TX \rangle \to \varepsilon \mid b\langle TX\rangle d \mid b \langle TY\rangle c$

$\langle TY \rangle \to \varepsilon \mid b\langle TY\rangle c$

Renaming the four nonterminals into $S,P,Q,R$ we obtain a more familiar solution.

$S \to \varepsilon \mid aS d \mid a P c\mid bQ d \mid b R c$

$P \to \varepsilon \mid aP c \mid b R c$

$Q \to \varepsilon \mid bQ d \mid b R c$

$R \to \varepsilon \mid bR c$

# Answer
> 0 votes
You have a grammar where it is natural to build sentences from the outside to the inside. You'll have a symbol in the middle, and in each derivation step you add a terminal at the left and one at the right, so the number of symbols on the left and on the right are the same.

Initially you produce a's and d's. Then you switch either to a's and c's or to b's and d's, from there to b's and c's, and eventually you stop producing new letters. So here's the grammar:

```
S -> aSd | T | U
T -> bTd | V
U -> aUc | V
V -> bVc | eps

```

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


# Question
Title: Solving linear programming problem with mixed type of constraints
I have a query in solving the problem below:

**An automobile company has two factories. One factory has 400 cars (of a certain model) in stock and the other factory has 300 cars (of the model) in stock. Two customers order this car model. The first customer needs 200 cars, and the second customer needs 300 cars. The cost of shipping cars from the two factories to the customers is shown:**

|  | Customer 1 | Customer 2 |
| --- | --- | --- |
| Factory 1 | \\$ 30 | \\$ 25 |
| Factory 2 | \\$ 36 | \\$ 30 |

**How should the company ship the cars in order to minimize the shipping cost?**

I am confused about how to proceed with this problem. I have considered the slack variables $x\_3$ through $x\_6$, and conversion of the minimisation problem to a maximisation one, and got:

$\text{Maximise Z}=6x\_1+5x\_2-16200$
$\text{subject to, }x\_1+x\_2+x\_3=400$
$~~~~~~~~~~~~~~~~~~~-x\_1-x\_2+x\_4=-200$
$~~~~~~~~~~~~~~~~~~~x\_1+x\_5=200$
$~~~~~~~~~~~~~~~~~~~x\_2+x\_6=300$
$~~~~~~~~~~~~~~~~~~~x\_1, x\_2, x\_3, x\_4, x\_5, x\_6 \ge 0$

However, when I start with the dual simplex method, I cannot get an entering variable, since the $C\_j-Z\_j$ values of the first iteration are all $\gt 0$.
How do I solve this using simplex and/or dual simplex? Any help is appreciated.

# Answer
You first need to transform this into normal form. Depending on how you learned it, you need to transform all constraints to the form $a\ge b$, or $a\le b$, where in $a$ you have variables and in $b$ only constants.

Transform $=$ into $\le$ and $\ge$ and from there you can easily transform this into normal form
> 0 votes

# Answer
You always need an initial solution. If you don't have one, you create another problem to get the initial solution.

In your case: Imagine you don't ship enough cars. Customer 1 misses $x\_7$ and customer 2 misses $x\_8$ cars. So you change two equations : $x\_1 + x\_5 + x\_7 = 200$, $x\_2 + x\_6 + x\_8 = 300$. And this has an initial solution: $x\_1 = x\_5 = x\_2 = x\_6 = 0$, $x\_7 = 200$, $x\_8 = 300$. And you find the minimum for $x\_7 + x\_8$. If the minimum is \> 0, then your original problem has no solution. If the minimum is 0, then you drop $x\_7$ and $x\_8$ and you just have found a (non-optimal) solution for the initial problem.

(I don't know if it is 100% correct, but the idea is that you create variables that express exactly how "wrong" your solution is, the initial value is "completely wrong", and you minimise the wrongness. If the minimal wrongness is zero, you have a starting point for the original problem, otherwise there is no solution).

PS. What if there is no solution? You can tell people there is no solution, but that isn't really helpful because the solution should tell people what action to take.

In that case you could say "Customers will be angry if they don't get their cars, and we add an annoyance factor of \\$200 for each car that customer 1 doesn't get, and \\$300 for each car that customer 2 doesn't get. Now we have a problem with a solution. We may not like the solution, but it will be the best we can get". And people can act on the solution.
> 0 votes

---
Tags: optimization, linear-programming, simplex
---


# Question
Title: How is the lookahead for an LR(1) automaton computed?
I'm reading Douglas Thain's book called "Introduction to Compilers and Language Design" and I've come across the following grammar:

, with the following LR(1) automaton:

, and I am not sure the look-ahead sets in state 0 (or any other state, really) is computed.

The algorithm given is the following:

```
For an item like A → α.B with a lookahead of {L}, add new rules
like B → .γ with a lookahead of {L}.
• For an item like A → α.Bβ, with a lookahead of {L}, add new rules
like B → .γ with a lookahead as follows:
– If β cannot produce epsilon, the lookahead is FIRST(β).
– If β can produce epsilon, the lookahead is FIRST(β) ∪ {L}

```

I don't really understand what FIRST(β) is in the case where β = + E (since E -\> E + T is of the form A-\> α.Bβ)

Also, it seems to me that `+ T` *cannot* produce epsilon, then how is it that its lookahead is `{$,+}` ? (which seems like it's `FIRST(β) ∪ {L}`)

# Answer
> 2 votes
$\text{FIRST}(\beta)$ is the set of possible first tokens in a derivation from β. (It's usual to also add ε to the first set if β could derive the empty sequence.)

So $\text{FIRST}(\mathbf{+}\mathit{T})$ is $\\{\mathbf{+}\\}$. No other token could possibly be at the beginning of any sentence derived from $\mathbf{+}\mathit{T}$. If that's not clear, it would be useful if you could explain your confusion.

The lookahead for an item is the set of tokens which could immediately follow the *complete* production of the item. It has absolutely nothing to do with the • in the item, but it's really only meaningful if the • is at the end (and therefore the state containing the item could be reduced). Giving every item a lookahead set is an algorithmic convenience for certain ways of computing lookahead sets, but in the completed state machine the only place lookahead sets are relevant is in the reduction states.

It might, however, make it easier to understand how lookahead sets are computed:

* Conceptually, lookahead sets are created during the itemset closure operation. Closure (recursively) creates new items with the • at the beginning for every non-terminal $\mathit{N}$ which follows the • in some item in the state. The new items are precisely the productions for $\mathit{N}$. Each such item is annotated with the lookahead for $\mathit{N}$ in the existing item; in other words, the lookahead set tells us what symbols could follow the new item when it's finished (at which point we'll come back to this state in order to take the GOTO action for $\mathit{N}$). If the item already exists in the state (because $\mathit{N}$ was previously encountered during the closure operation), we don't add a new item; instead, we add the symbols from the follow set for this instance of $\mathit{N}$ to the lookahead set for the new item.

As an example, consider State 12 in your diagram. The first item is $\mathit{T}\to\\;\mathbf{id} \\;\mathbf{(}\\;•\\;\mathit{E}\\;\mathbf{)}$, in which $\mathit{E}$ follows the •. So we're going to add items for each production for $\mathit{E}$, and all of those new items will be given the lookahead set $\\{\mathbf{)}\\}$, because that's what follows the $\mathit{E}$ here. So that causes us to add the item, $\mathit{E}\to\\; •\\; \mathit{E}\\; \mathbf{+}\\; \mathit{E}$. Since we've already added items for the productions of $\mathit{E}$, we don't add new ones; however, we must add $\mathbf{+}$ to all their lookahead sets, because that's the symbols which follows *this* instance of $\mathit{E}$. So now the lookahead sets for the new $\mathit{E}$ items are $\\{ \mathbf{+}, \mathbf{)} \\}$. There are no more instances of $\mathit{E}$ following the •, so those lookahead sets are now complete.
* When we create a new state by advancing the •, we simply copy the lookahead sets for each item in the new state. So the lookahead sets still reflect what the possible following symbols are when the item's production is completed.

But note that the LALR algorithm merges states with the same items, independent of the items' lookahead sets. In the resulting merged state, the lookahead set for each item is the union of the lookahead set for each item in the states being merged. This is actually imprecise, which is why LALR parsers can have conflicts which don't appear in the LR parser for the same grammar (in which states with different lookahead sets are not merged). However, it's not *fatally* imprecise; it cannot cause a valid derivation to be discarded, but it can cause the parser to perform a reduction step which will lead it to limbo.

---
Tags: compilers, parsers, lr-k
---


# Question
Title: Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Define $L'=\\{u\\#v^R ~|~ u,v \in L\\}$ and $L\in RL$ while $\\#\notin \Sigma$

Why is $L'$ a regular language?

I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped edges. I think this is correct.

Thanks!

# Answer
Regular languages are closed under reversal, therefore $L^R = \\{v^R \mid v \in L\\}$ is regular. Moreover, regular languages are closed under concatenation, therefore $L' = L \circ \\{\\#\\} \circ L^R$ is regular.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, context-free, regular-expressions
---


# Question
Title: Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Why is $L=\\{w \mid ~|w|\bmod3=\\#\_a(w)\bmod3\\}$ a regular language?

$\\#\_a(w)$ is the number of $a$'s in $w$.

So far every language that I saw containing `modulo` was a regular language. Can you give me an example of a non-regular language with a `modulo` operator in it?

# Answer
> 11 votes
$\newcommand{\m}{\operatorname{\\%}}$ Let $d(w)=(|w|-\\#\_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language. Note $L=\\{ w\mid d(w)=0\\}$.

The simple and critical observation is that there are only 3 possible values for $d(w)$: $0, 1, 2$. A deterministic finite automaton (DFA) can remember and update that value for the input read so far. Accordingly, it is easy to construct a DFA that accepts $L$.

Specifically, let DFA $D$ have three states, $q\_0, q\_1$ and $q\_2$. Here are the transitions of $D$ so that state $q\_i$ accept words of $d$ value $i$.

* $\delta(q\_i, a)= q\_i$, since reading an $a$ will increase both $|\cdot|$ and $\\#\_a(\cdot)$ by 1.
* $\delta(q\_0, x)= q\_1$, $\delta(q\_1, x)= q\_2$, $\delta(q\_2, x)= q\_0$, where $x$ is any symbol that is not $a$, since reading a $x$ will increase $|\cdot|$ by 1 but keep $\\#\_a(\cdot)$.

Let $q\_0$ be the start state and the only final state. Then $L$ is accepted by $D$. So $L$ is regular.

---

"Every language that I saw containing $\text{modulo}$ was a regular language." This is nice observation. The reason is that there is only finitely many values of $n\m d$ for an integer $n$ and a fixed integer $d$. DFAs are powerful enough to remember and update finitely many information.

However, if there are other conditions involved to define the language, it may not be regular any more.

For example, consider $N= \\{a^nb^n \mid n = 0 \bmod 2\\}$. $N$ is non-regular since $a^0, a^2, a^4, \cdots$ are pairwise distinguishable. For two different even number $i$ and $j$, $a^i$ and $a^j$ are distinguished by $b^i$ as $a^ib^i\in D$ but $a^jb^i\not\in D$.

# Answer
> 6 votes
The following language is not regular $L = \\{a^n b^m c^n \mid m = n \bmod 2\\}$.

To see that $L$ is not regular, suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Then, $a^{2p}c^{2p} \in L$ and there is some $1 \le k \le p$ such that $a^{2p + ik} c^{2p} \in L$ for every integer $i \ge -1$. Choosing $i=-1$ yields the contradiction $a^{2p-k} c^{2p} \in L$.

# Answer
> 5 votes
Lucky enough, your case is quite easy. The language is defined by the rule "total number of letters, modulo 3, equals total number of a's, modulo 3". This is equivalent to "number of letters that are not a's is divisible by 3". Same language, but a lot easier.

You build a state machine with three states $S\_0$, $S\_1$, and $S\_2$. Being in state $S\_i$ means "the number of letters that are not a's is i modulo 3". You start in state $S\_0$ which is also the only valid ending state. An a returns to the same state, anything that is not an a goes from $S\_0$ to $S\_1$, from $S\_1$ to $S\_2$, and from $S\_2$ to $S\_0$.

If you had only two symbols a and b, then a regular expression for the language would be (a\* b a\* b a\* b)\* a\*. For more symbols, say a, b, c, d, you would replace b with (b | c | d).

# Answer
> 5 votes
> So far every language that I saw containing modulo was a regular language.

As John L. notes, that's a very good observation. Indeed, any language where the *only* constraint on words is that *some number* modulo $n$ (which we can update letter by letter as we parse the input) belongs to some set of numbers modulo $n$ must be regular. This is because such a language can be parsed by a DFA with $n$ states, where each state encodes one of the $n$ possible values of the number, and where the state transitions define how the number changes when a new input letter is appended to the end of the input word.

More generally, we can even prove the following theorem:

> **Theorem**: A language $L$ is regular if (and only if!) it can be represented in the following form: $$L = \\{w \mid s(w) \in A\\}$$ where $s(w)$ can only take a finite number of possible values and where, for any word $w$ and any letter $c$, knowing $s(w)$ and $c$ is sufficient to determine $s(wc)$.

Again, the proof is basically trivial, given that we know that a language is regular if and only if it is accepted by some DFA: Given a language $L$ defined as above, define a DFA $D$ with one state for each possible value of $s(w)$, with transitions encoding the map $(s(w), c) \mapsto s(wc)$, and let its accepting states be those that correspond to values of $s(w)$ that are in $A$. Clearly $D$ accepts exactly the language $L$. (Conversely, given a DFA $D$ accepting a language $L$, let $s(w)$ be the current state of $D$ after reading the input word $w$ and let $A$ be the set of accepting states of $D$. Then $L$ will satisfy the definition above.)

---

Note that $s(w)$ doesn't necessarily have to be a single number modulo $n$. For example, for the example language in your question, we could naturally define $s(w)$ to be a *pair* of numbers modulo $3$: $$s(w) = (|w| \bmod 3, \\#\_a(w) \bmod 3).$$ As defined, $s(w)$ can still clearly take only a finite number of possible values (nine, to be exact) and it should be easy to see how to update each of the numbers in the pair whenever a new input letter is read.

Of course, in this particular case a more compact encoding, such as $$s(w) = (|w| - \\#\_a(w)) \bmod 3,$$ is also possible. But the "naive" encoding method is more general, and can be used (with trivial modifications) to show e.g. that the following language is *also* regular: $$L = \\{w \mid |w| \bmod 3 = \\#\_a(w) \bmod 4\\}$$

---
Tags: formal-languages, regular-languages, automata, finite-automata, context-free
---


# Question
Title: substitution of same variable in context-free grammars
Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables. Could someone explain why A and B have to be different variables?

# Answer
As you suspect probably, theorem 6.1 still holds even if $A$ and $B$ are the same variable. This can be seen by following the proof of the theorem, assuming $B$ is $A$.

So, it is not correct to say "it is necessary that $A$ and $B$ be different variables" so that the conclusion $L(\widehat G) = L(G)$ holds. The quoted text is from the text right after the proof of that theorem in that textbook.

However, when $A$ and $B$ are the same variable, the change from $G$ to $\widehat G$ is unlikely to be helpful to simplify a context-free grammar by any reasonable measure. In order to simplify a context-free grammar, we would most probably use theorem 6.1 in the case when $A$ and $B$ are different variables, if we want to use it at all.
> 2 votes

---
Tags: automata, finite-automata, context-free, logic
---


# Question
Title: Why do the pointers in Two-pointer algorithm move only towards each other?
Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number. The solution to the above problem goes like this:

> With using the Two Pointers pattern, and Pointer 1 pointing to the beginning of the array and Pointer 2 pointing to the end of the array, we will check if the numbers pointed by the pointers add up to the target sum. If they do, we have found our pair. If not, we should do one of these things:

> If the sum is bigger than the target sum, this means that we need a smaller sum so, we are going to decrement the Pointer 2 (end-pointer).

> If the sum is smaller than the target sum, this means that we need a bigger sum so, we are going to increment the Pointer 1 (start-pointer).

What I fail to understand in the above solution is: If the sum is bigger than the target sum, why is decreasing the Pointer 2 position the only way? Why can't we decrease Pointer-1 position?

# Answer
> 0 votes
Consider a situation where Pointer 1 is equal to $i$ and Pointer 2 is equal to $j$, and $A\[i\] + A\[j\] \> K$.

The last time Pointer 1 was incremented, Pointer 2 was in a position $j' \geqslant j$. Since it was Pointer 1 which was modified, that means that $A\[i-1\] + A\[j'\] \< K$. Since the array is sorted, $A\[j\] \leqslant A\[j'\]$. Therefore, there is no need to decrement Pointer 1, because $A\[i-1\] + A\[j\] \leqslant A\[i-1\] + A\[j'\] \< K$.

# Answer
> 0 votes
For every position of the left pointer, there is a *unique position* of the right pointer such that the sum exceeds or equals $K$ and moving the right pointer to the left makes the sum smaller than $K$.

E.g. $2,5,6,8,11,15,21$, target sum $14$. We show the unique right positions for increasing left positions:

$\mathbf2,5,6,8,11,\mathbf{15},21\\ 2,\mathbf5,6,8,\mathbf{11},15,21\\ 2,5,\mathbf6,\mathbf8,11,15,21$

The two-pointer algorithm works by finding these unique positions, because as you can see no backtracking is ever necessary.

---
Tags: algorithms, arrays
---


# Question
Title: How are regular languages not structurally recursive?
This blog posting states that *"regular languages aren't structurally recursive"* while *"That's not the case for context-free grammars"*

In what sense is the term "structurally recursive" meant here?

# Answer
> 1 votes
Regular languages don't have recursive structures, so formally regular expressions cannot express recursive structures by definition.All regular languages can be recognized by a finite automaton. A finite automaton has a finite number of states, and consequently, finite memory .

A recursive "regular" expression requires a potentially infinite stack space to do the recursion, thus it is not possible to recognize it with a finite automaton, therefore it is not regular.But for CFL it's true.

---
Tags: formal-languages, regular-languages, context-free, recursion
---


# Question
Title: variable repetitions in pumping lemma for context-free languages
Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz.

The picture below is in support of the proof.

I do not understand two things about this proof:

1) "we can assume that no variable repeats in the subtree T\_5". Why should there not be any variable that repeats itself? Why is that a problem?

2) "Similarly, we can assume that no variable repeats in the subtrees T\_3 and T\_4." I don't quite see how we can fix the issue if there are variables that repeat in the subtrees T\_3 or T\_4?

# Answer
It is certainly possible that some variables repeat in the subtree $T\_3$, $T\_4$ or $T\_5$. There is nothing wrong with those situations, except that those situations are too relaxed for us to ensure "the lengths of the strings $v$, $x$, and $y$ depend only on the productions of the grammar and can be bounded independently of $w$ so that (8.2) holds"

---

Let us verify that we are able to assume those two assumptions.

One way to enable those two assumptions is described in the textbook. I will let you to convince yourself it works.

Here is a slightly different way to enable those two assumptions. We know that there are repeated variables on some path from the root to a leaf. Choose a pair of the same variable so that the number of nodes in the subtree rooted at the upper appearance of the variable is the smallest among all possible such pairs. Let that pair be shown as the two $A$s in the following derivation, which corresponds to figure 8.1.

$$ S\stackrel{\*}{\implies}uAz\stackrel{\*}{\implies}uvAyz\stackrel{\*}{\implies}uvxyz$$

There is no repeated variable in subtrees $T\_3$, $T\_4$ and $T\_5$, since any repeated variable in $T\_3$, $T\_4$ or $T\_5$, say $B$, means the subtree rooted at the upper appearance of $B$ has smaller number of nodes than the subtree rooted at the upper $A$ (as the former tree is strictly contained in the latter tree), which contradicts to how $A$s in the figure have been selected.

---

That means any path from the upper $A$ to any leaf in the tree passes at most $|V|+2$ nodes, where $V$ is the set of variables. ("$+2$" since $A$ may appear twice in that path and the leaf node holds a terminal symbol instead a variable') Since each node can have at most $\ell$ children, where $\ell$ is the maximum length of the string on the right side of any production, the number of leaves in the subtree rooted at the upper $A$ is at most $\ell^{|V|+1}$, i.e., $|vxy|\le\ell^{|V|+1}$. Note $\ell^{|V|+1}$ is a constant that depends on the grammar only.
> 2 votes

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