# Question
Title: Unambiguousness and determinism of CFGs for them to be LR
I came across this statement:

> Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.

I was guessing what could be the characteristics of such grammars?

Then I came across this question which very well asks:

> Why does there exist a conflict even though it is not ambiguous grammar?

The answer does not give straight answer to above "Why". But definitely says this:

> A context-free language is LR(k) precisely if it is deterministic.

In this context, I have following guessings which I want confirmations for:

1. All LR grammars are unambiguous, merely because they need to be deterministic and set of deterministic languages is proper subset of unambiguous languages.
2. In other words, unambiguous languages which are non LR are those which are non deterministic.
3. Dragon book says we can enforce association and precedence to ensure unambiguousness of grammar by resolving conflicts. I also read that we do left factoring to convert non deterministic grammar to deterministic grammar.
I am quite confused about what actually converts non LR grammar to LR after considering above two sentences and point 2. Is it enforcing association and/or precedence or left factoring. I feel it should be left factoring given determinism is absolutely necessary than unambiguousness and there must exist some ambiguous grammars which do not turn to LR by enforcing association and/or precedence. Am I correct with this? Left factoring eliminates FIRST-FIRST conflicts in LL grammarref. But does it help to eliminate SHIFT-REDUCE and REDUCE-REDUCE conflicts in LR grammars?

# Answer
> 2 votes
Your first and second points are correct, although you need to take more care distinguishing between properties of *grammars* and properties of *languages*.

A language is context free if (and only if) there exists a context free grammar for it. It is also deterministic if (and only if) there exists a deterministic context free grammar for it. That doesn't mean that all grammars for the language will be deterministic or even context-free; there are basically an infinitude of possible grammars for any language, deterministic and not, ambiguous and not, and not restricted to the smallest class in the Chomsky hierarchy.

In fact, figuring out whether a language has one of these properties is often not easy. While we can easily see which of Chomsky's classes a grammar belongs to, and we can easily determine whether or not a particular context-free grammar is, for example, $LR(k)$ for any given $k$, similar statements about languages are much harder. In particular, the following questions are undecidable, which means that no algorithm exists which will produce a correct answer for every possible input:

* Does a context-free grammar exist for a given language?
* Does an $LR(k)$ grammar exist for a given language?
* Does a deterministic grammar exist for a given language?

Some questions about grammars are also undecidable:

* Is there a $k$ for which an $LR(k)$ parser can be generated for a given grammar?
* Do two context-free grammars recognise the same language?
* Is a given context-free grammar ambiguous?

(There are many more, but these ones seemed relevant.)

Note that "undecidable" doesn't mean you can't ever figure it out. For certain languages and grammars it is quite possible to answer the above questions. But there is no algorithm which can generate a solution. Finding a solution requires luck and perseverance, and there's no guarantee you'll manage it. (This is somewhat like the problem of proving a given mathematical hypothesis.)

One of the consequences of all that undecidability is that there are no 100% reliable algorithms which can "remove ambiguity" from a grammar, make a grammar deterministic, and so on. All of the procedures recommended in the various textbooks you refer to (and internet sites) are just heuristics: they might work, but there are no guarantees. If you determine that a given grammar is not $LR(1)$, or not $LL(1)$, etc., you can try applying the various procedures mentioned, but you might not be able to find a transformation which works. And the mere fact that you didn't manage that transformation proves absolutely nothing about the language, although again there are cases in which you can prove that a given language has no deterministic grammar, or even that it has no unambiguous grammar. (Languages for which no unambiguous grammar exists are called "inherently ambiguous" and you can find examples by searching for that phrase, if you're interested.)

I understand that this may all seem unsatisfactory. I think you really want there to be some visible attribute of a grammar (or language) which you can point to and say, "because of this feature, this grammar is not $X$" (for some property $X$). But there really isn't a better characterisation of, for example, grammars which are not $LR(1)$ than "the $LR(1)$ parser generation algorithm failed to produce a parser for this language".

So, in short:

A grammar is deterministic if the $LR(k)$ parser generation algorithm works for some $k$, and non-deterministic if it doesn't work for any $k$. But you can't prove non-determinism that way, because you'd have to try all possible values of $k$ and that would literally take you forever.

Furthermore, even if a grammar is non-deterministic, it might or might not be ambiguous. There's no algorithm which can tell you that, either.

Finally, with respect to my answer which you quoted, I think it does explain why that particular grammar is non-deterministic: it's because you need to do the first reduction when you hit the middle of the sentence, but since you don't know where the middle of the sentence is until you reach the end (and the sentence could be arbitrarily long), you cannot know at which point in the input you need to do the first reduction. However, the language is certainly unambiguous: there is only one derivation which works.

(These statements are true of palindrome grammars regardless of how many symbols there are in the alphabet. But if the alphabet contains only a single symbol, then there is a *different grammar* which happens to be regular. In this particular case it's not hard to figure out what it is.)

---
Tags: formal-languages, automata, context-free, compilers, parsers
---


# Question
Title: What is the use of First() and Follow() in compiler design?
I am completely aware of how to calculate first and follow, my professor has taught me that well , but he had not explained what is the need of First() and Follow(), so any explanation why we need them will help me very much.

# Answer
> 1 votes
$FIRST$ and $FOLLOW$ sets are used by the algorithm which produces an $LL(k)$ parser from a grammar. They're also used in a number of other algorithms which analyze grammars, but most students will run into them when learning about top-down parsers.

Parsing is a tiny part of the work of producing a compiler, and in practice you can generate a parser using code-generation tools which avoid you having to know much about implementation details. So I'd say that th4e direct answer to your question is that $FIRST$ and $FOLLOW$ sets have very little to do with compiler *design*, but they are useful in the understanding of how particular parsing algorithms work.

# Answer
> 0 votes
$FIRST$ of a non-terminal would refer to the very first character of the strings that can be derived starting from that non-terminal. The $FIRST$ of a terminal would be the terminal itself.

The $FOLLOW$ of a non-terminal $A$ refers to the $FIRST$ of the non-terminal or terminal that immediately comes after $A$ in the dervivation rules.

They are used by parsing algorithms to determine which production to use for parsing a string. If we have a choice of multiple productions, and we wish to generate a string $x$ we would like to use the productions that can generate strings that start with $x$. This is where $FIRST$ can be used to identify such productions.

---
Tags: compilers, parsers
---


# Question
Title: Connection between non determinism and LL(1) conflicts
I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.

As per my understanding non deterministic context free grammar is a context free grammar in which at some point in time during parsing, multiple actions are allowed. Also I believe non determinism occurs when we have multiple productions in grammar with same prefix of production (right hand side) bodies. Also I know we eliminate non determinism by left factoring grammar.

Wikipedia article says:

1. We do left factoring to eliminate FIRST-FIRST conflicts. ref
2. Left recursion is a special case of FIRST-FIRST conflict. ref
3. Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
4. Left recursion is eliminated using rule like below ref :
$A\rightarrow A\alpha | \beta $
ios converted to
$A\rightarrow \beta A'$
$A'\rightarrow \alpha A' | \epsilon$

I have following doubts:

1. Since both non determinism and FIRST-FIRST conflicts are removed with left factoring and since left recursion is special case of FIRST-FIRST conflict, is non determinism a reason behind FIRST-FIRST conflict and left recursion (and also for FIRST-FOLLOW conflict)? If yes, does non determinism cause anything else and there is nothing else apart from these three (FIRST-FIRST conflict, left recursion and FIRST-FOLLOW conflict) in which non determinism manifests?
2. Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?
3. I know LL grammar should be both non deterministic and unambiguous. Does ambiguity also manifests in some way in LL parsing table or grammar? I read ambiguity can be eliminated by enforcing association and precedence between grammar symbols and this resolves SHIFT-REDUCE conflicts in LR parsers. Is anything like this required for eliminating ambiguity to make grammar a valid LL grammar?

# Answer
> 3 votes
1. No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.
2. Some deterministic grammars -- and even some deterministic context-free languages -- have no $LL$ parser. Such grammars are not necessarily ambiguous. An accurate deterministic parser obviously cannot be generated for an ambiguous grammar, but failure to generate a parser doesn't say anything about ambiguity.
3. Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.

---
Tags: automata, context-free, formal-grammars, compilers, parsers
---


# Question
Title: Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?
Are there languages $L\_1$, $L\_2$ such that such that $$L\_1 \cup L\_2\leq\_m\\, L\_1\cap L\_2,$$ and two other languages such that $$L\_1 \cap L\_2 \leq\_m\\, L\_1 \cup L\_2?$$ And if so, what are they? How can i go about finding these?

# Answer
How about taking $L\_1=L\_2$? Then we will have both $L\_1 \cup L\_2\leq\_m\\, L\_1\cap L\_2$ and $L\_1 \cap L\_2 \leq\_m\\, L\_1 \cup L\_2$.

If you want to have $L\_1\not= L\_2$, you just try $L\_2=L\_1\cup\\{w\\}$, where $w$ is a string not in $L\_1$.

If you are determined to have infinity elements in both $L\_1\setminus L\_2$ and $L\_2\setminus L\_1$, try $L\_1=L\cup aL$ and $L\_2=L\cup bL$, where $L$ is an infinite language over $\Sigma$ and $a,b$ are two new symbols not in $\Sigma$.

By now, you should be able to see that there are lots of way to construct examples that satisfy the requirements.
> 3 votes

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


title: Is Lambda Calculus purely syntactic?

text:
# Question
Title: Is Lambda Calculus purely syntactic?
I've been reading for a few weeks about the Lambda Calculus, but I have not yet seen anything that is materially distinct from existing mathematical functions, and I want to know whether it is just a matter of notation, or whether there are any new properties or rules created by the lambda calculus axioms that don't apply to every mathematical function. So, for example, I've read that:

**"There can be anonymous functions"**: Lambda functions aren't anonymous, they're just all called lambda. It is permissible in mathematical notation to use the same variable for different functions if the name is not important. For example, the two functions in a Galois Connection are often both called \*.

**"Functions can accept functions as inputs"**: Not new you can do this in with ordinary functions.

**"Functions are black boxes"**: Just inputs and outputs are also valid descriptions of mathematical functions...

This may seem like a discussion or opinionated question but I believe that there should be a "correct" answer to this question. I want to know whether lambda calculus is just a notational, or syntactic convention for working with mathematical functions, or whether there are any substantial or semantic differences between lambdas and ordinary functions.

# Answer
Ironically, the title is on point but not in the way you seem to mean it which is "is the lambda calculus just a notational convention" which is not accurate.

Lambda terms *are not functions*1. They are pieces of syntax, i.e. collections of symbols on a page. We have rules for manipulating these collections of symbols, most significantly beta reduction. You can have multiple *distinct* lambda terms that *correspond to* the *same* function.2

I'll address your points directly.

First, lambda is not a name that is being reused. Not only would that be extremely confusing, but we don't write $\lambda(x)$ (or $(\lambda\ x)$) which is what we'd do if $\lambda$ was a name for a function, just like we write $f(x)$. In $f(x)$ we could replace $f$ (if it were defined by a lambda term) with the lambda term producing something like $(\lambda y.y)(x)$ meaning $(\lambda y.y)$ is an expression that can represent a function, not a declaration declaring a function (named $\lambda$ or anything else). At any rate, when we overload terminology/notation, it is (one hopes) done in a manner where it can be disambiguated via context, that certainly can't be the case for lambda terms.

Your next point is fine but somewhat irrelevant. This is not a competition where there's Team Lambda Terms and Team Functions, and only one can win. A major application of lambda terms is studying and understanding certain kinds of functions. A polynomial is not a function though we often sloppily identify them. Studying polynomials doesn't mean one thinks that all functions should be polynomials, nor is it the case that polynomials have to "do" something "new" to be worth studying.

Set theoretic functions are not black boxes, though they are entirely defined by their input-output relation. (They literally *are* their input-output relation.) Lambda terms are also not black boxes and they are *not* defined by their input-output relation. As I've mentioned before, you can have distinct lambda terms that produce the same input-output relation. This also underscores the fact that lambda terms *can't* be functions, though they can *induce* functions.2

In fact, the analogy between polynomials and lambda terms is very close, and I suspect you may not appreciate the distinction between a polynomial and the function it represents, so I'll elaborate a bit.3 Typically when polynomials are introduced, usually with real coefficients, they are treated as real functions of a particular type. Now consider the theory of linear-feedback shift registers (LFSRs). It is largely the theory of (uni-variate) polynomials over $\mathbb F\_2$, but if we think of that as a *function* $\mathbb F\_2\to\mathbb F\_2$, then there are at most $4$ such functions. There are, however, an infinite number of polynomials over $\mathbb F\_2$.4 One way to see this is that we can interpret these polynomials as something other than $\mathbb F\_2\to\mathbb F\_2$ functions, indeed any $\mathbb F\_2$-algebra will do. For LFSRs, we commonly interpret the polynomials as operations on bitstreams, which, if we wanted could be represented as functions $\mathbf{2}^{\mathbb N}\to\mathbf{2}^{\mathbb N}$, though the vast majority of such functions would not be in the image of the interpretation of an LFSR.

This applies to lambda terms as well, we can interpret both of them as things other than functions. They are also both much more tractable objects to work with than the typically uncountably infinite sets of functions. They are both much more computational than arbitrary functions. I can write a program to manipulate polynomials (with coefficients that are computably representable at least) and lambda terms. Indeed, untyped lambda terms are one of the original models of computable functions. This more symbolic/syntactic, calculational/computational perspective is usually more emphasized, especially for the *untyped* lambda calculus, than the more semantic interpretations of the lambda calculus. *Typed* lambda terms are far more manageable things and can usually (but not always) easily be interpreted as set theoretic functions, but can also usually be interpreted into an even broader class of things besides functions than the untyped lambda calculus. They also have a rich syntactic theory of their own and a very deep connection to logic.

1 It's possible the issue might go the other way. Maybe you have a misapprehension about what a function is.

2 This is actually not so straightforward. For the *untyped* lambda calculus, it doesn't really make sense to naively interpret arbitrary lambda terms as set-theoretic functions. You can start to see this when you try to articulate what the domain of the interpretation should be. If I interpret a lambda term as an element of a set $D$, I also want to be able to interpret it as a function on $D$ and into $D$ since I want to interpret application as function application. You end up with $D^D\subseteq D$ (or a weakening of this) which is true only of the singleton set. What we need for the untyped lambda calculus is a reflexive object, and for the category of sets there are no non-trivial reflexive objects. The story is quite a bit different for *typed* lambda terms, but can still be non-trivial.

3 If you are clear on this distinction, then the analogy should be pretty informative.

4 This issue doesn't occur with fields of characteristic 0, like the complex numbers, reals, rationals, or integers, so the distinction isn't as sharp, though it still exists.
> 65 votes

# Answer
Think about the concept of variables. In old languages like basic, you didn't have dynamic allocation and you needed one name for each variable. (This is not perfectly accurate because you had arrays, but the idea is that...) in many problems, you need to be able to allocate as many variable as you want, without being limited by the number of names your program defines.

Lambda functions allows you to get rid of the same limitation about functions names, allowing your program to define as many functions as it needs and "store" them in the sames complex data structures as other variables. This is not something you could do with conventional named functions.
> 0 votes

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


# Question
Title: How to construct an ordinary matching from a fractional matching?
Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in \[0,1\]$, with the constraint: for $v \in V$, $\sum\_{e \ni v}f(e) \leq 1 $.

My question is : does the fractional matching give a matching that we know (of $G$) i.e. with no conflicting edges? I am confused, since there is no criteria for choosing a fraction $f(e) \in \[0,1\]$, for every $e \in E$. For example, if we have $e\_{1}, e\_{2} \in E$ such that $v \in e\_{1}, e\_{2} $ and I assign $f(e\_{1})=1/4$ and $f(e\_{2})= 1/2$, then $f(e\_{1})+f(e\_{2})=3/4 \leq 1 $, hence both $e\_{1}$ and $e\_{2}$ should belong to the fractional matching.

Thank you in advance.

# Answer
It is not possible to get a maximum matching from any fractional matching by only looking at the values of the fractional matching. Consider the undirected triangle graph with vertices $v\_1,v\_2,v\_3$ and edges $e\_1=(v\_1,v\_2), e\_2=(v\_1,v\_3), e\_3=(v\_2,v\_3)$. If we assign $f(e\_1)=f(e\_2)=f(e\_3)=\frac{1}{2}$, this is a valid fractional matching. However, an actual matching can only contain one of the edges, so we cannot distinguish these edges by their value.

It is of course always possible to obtain a matching from a fractional matching by first selecting all edges with at least a certain fraction and then removing edges such that you end up with a matching. This matching, however, is usually not a maximum matching.
> 2 votes

---
Tags: graphs, matching
---


# Question
Title: Data structure for selection of K elements and taking sum
**The problem:**

We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ elements from the given array and perform XOR on each of them with $Q$.

Is there any data structure I can use which can perform this efficiently or any algorithm I am not aware of?

I tried finding each element's maximum possible value (using XOR/ignoring it), sorting the array and then making the selection but it did not work, which leads me to believe that the greedy approach won't work here.

I am primarily looking for an algorithm that can help or a data structure, not necessarily the code.

For example, given the array $\[1, 2, 3, 4, 5\], Z = 2$ and $Q = 4$, the answer is 23 as I can take XOR of 1 and 2 with 4 and of 3 and 4 with 4 as well.

Edit: The sum 23 is obtained as follows: We need to select Z (2) values at a time. So we select 1 and 2 and obtain their XOR with Q(4), which makes it 5 and 6. We then select 3 and 4 and obtain their XOR with Q, which makes them 7 and 0. Thus the final array becomes $\[5,6,7,0,5\] which is equal to 23 and is maximum possible sum.

# Answer
> 1 votes
First, note that for any $a$, since XOR is associative:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b)$$

Since $b \oplus b$ is $0$ and $0$ is neutral for XOR, we get that:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b) = a \oplus 0 = a$$

In other words, there is no point performing XOR operation more than twice, for any $a$ with any $Q$. You can either XOR once, or not XOR at all (XOR twice)

---

Now, suppose you have an array $A$. Prepare the array $B$ as an array of the difference between $A$ before and after we XOR it:

$B\_i = \max\\{0, A\_i \oplus Q - A\_i\\} $ (Since performing XOR on $A\_i$ twice yields $A\_i$, we can also choose $A\_i$ itself).

Preparing $B$ takes $O(n)$.

Increasing the sum of $A$ is now equivalent to selecting the $Z$ XORS that their sum - difference is greatest, which is equivalent to selecting $Z$ max elements from $B$.

For that, there's a better solution than sorting ($O(n\log n)$):

* Select the $Z-th$ largest element of $B$ using selection algorithm
* Sweep $B$ and save any element that is larger than the $Z-th$ largest element

The indices of the elments chosen in $B$ determine both the elements of $A$ you select, and the XOR performed (or not performed). In total, it took $O(n)$ time.

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


# Question
Title: Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.

The question: $L\_1$ and $L\_2$ are regular languages over the same $\Sigma$. prove that the following language is regular as well:

$L^\frown \\:=\left\\{\\:w\\:\in L\_1 | \\:w=\sigma \_1\mu \_1\xi \_1\sigma \\:\_2\mu \\:\_2\xi \\:\_2...\sigma \\:\_n\mu \\:\_n\xi \\:\_n\right\\}$ Where $n \geq 0$, for every i:$\left(1\\:\le i\\:\le n:\\:\sigma \_i\mu \_i\xi \_i\\:\in \Sigma \right)$, $\mu\_1\mu\_2...\mu\_n \in L\_2$.

Prove using: 1)Closure properties. 2)Building an multipication automaton

My try:

1)I do not understand how to define the homomorphism from which I can deduct using closure properties that the given language is indeed regular.

2)Since both $L\_1$ and $L\_2$ are regular, There exist two deterministic finite automatas that can accept them: $A^i\\:=\\:\left(\Sigma ,\\:Q^i,q\_0^i,F^i,\delta ^i\right)$ ($i\\:\in \left\\{\\:1,2\right\\})$. So, let L be the automaton that accepts those two languages: let L be $L\\:=\\:\left(\Sigma \\:,\\:Q^1\\:X\\:Q^2,\left(q\_0^1,q\_0^2\right),F^1X\\:F^2,\delta \\:\right)$. However, here I don't know what its transition function should be

Would really appreciate your help with it, if possible with explanations to understand so I'll be able to overcome similar questions in the future.

Thank you so much!

# Answer
> 1 votes
**Proof using closure properties**

Let $add\colon \Sigma \to \Sigma^\*$ be a regular substitution that maps $\mu \in \Sigma$ to $\\{ \sigma \mu \xi : \sigma, \xi \in \Sigma \\}$ (the image is regular since it is finite). Then your language is $L\_1 \cap add(L\_2)$.

**Proof using product automaton**

Let $(\Sigma, Q^i, q\_0^i, F^i, \delta^i)$ be automata accepting $L\_i$ (for $i = 1,2$). We construct a new automaton $(\Sigma, Q, q\_0, F, \delta)$ where:

* $Q = Q^1 \times Q^2 \times \\{1,2,3\\}$.
* $q\_0 = (q\_0^1,q\_0^2,1)$.
* $F = F\_1 \times F\_2 \times \\{1\\}$.
* $\delta((q^1,q^2,1),\sigma) = (\delta^1(q^1,\sigma),q^2,2)$.
* $\delta((q^1,q^2,2),\sigma) = (\delta^1(q^1,\sigma),\delta^2(q^2,\sigma),3)$.
* $\delta((q^1,q^2,3),\sigma) = (\delta^1(q^1,\sigma),q^2,1)$.

The product automaton keeps track of the state in both automata, as well as the location within the triple $\sigma\_i \mu\_i \xi\_i$ (this is the purpose of the third argument).

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


title: Quantum vs classic in NP-hard problems

text:
# Question
Title: Quantum vs classic in NP-hard problems
Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?

# Answer
> 3 votes
It is conjectured that the complexity of SAT on $n$ variables is $\tilde\Omega(2^n)$ (a version of this is SETH, the strong exponential time hypothesis). In contrast, Grover's algorithm solves it in $\tilde O(2^{n/2})$.

On the other hand, it is conjectured that quantum computers cannot solve NP-hard problems in polynomial time, that is $\mathsf{NP} \not\subseteq \mathsf{BQP}$.

---
Tags: complexity-theory, time-complexity, np-hard, np, quantum-computing
---


# Question
Title: Can these two languages be reduced to one another?
Given:

$L\_1=\left\\{ \left\langle M\right\rangle :L\left(M\right)\ni w\_{0}\right\\}$

$L\_2=\left\\{ \left\langle M\right\rangle :L\left(M\right)=\left\\{ w\_{0}\right\\} \right\\}$

I believe I've managed to show that:

* $L\_1 \in \mathcal{RE \setminus R} $ since it's easy to construct the acceptor:

```
U(<M>):
  if <M> is an invalid encoding of a TM:
    REJECT
  emulate M(w_0)
  if M accepts:
    ACCEPT
  if M rejects:
    REJECT

```

But according to Rice's Theorem $L\_1\notin \mathcal{R}$.

* $L\_2 \notin \mathcal{RE}$ since $\overline{H\_{TM}}\leq\_{m} L\_2 $ where $\overline{H\_{TM}}$ is the complement of the halting problem, which we know to be unrecognizable. I defined $f( \left\langle M,w\right\rangle) = \left\langle M^{\prime}\right\rangle$ s.t.:

```
M'(x):
  if x==w_0:
      ACCEPT
  if <M> is an invalid encoding of a TM:
    if x==w_0:
      ACCEPT
    else
      REJECT
  emulate M(w)
  if M halts:
    REJECT

```

These two proof attempts are not related, but they are two parts of the same question - So first I tried showing that $L\_2 \leq\_{m} L\_1 $ which seems intuitively correct but I couldn't work it out. Then I got to think about it and since it's quite difficult to come up with an acceptor for $L\_2$ or $\overline{L\_2}$ it seems to me more like that $L\_2 \notin \mathcal{RE}$.

I'm pretty confident that my proof for $L\_1 \in \mathcal{RE \setminus R} $ it correct, but as for $L\_2$, I tried so many versions of the pseudocode for $M^\prime$ (including a reduction from $\overline{A\_{TM}}$) and I still can't convince myself that I got it right.

What bothers me the most is that nothing assures me $ \left\langle M,w\right\rangle \in \overline{H\_{TM}} \implies \left\langle M^\prime\right\rangle \in L\_2 $: As far as $M^\prime$ concerned, it might also get a valid encoding of $M$ and some $w$ on which it *halts*, but if $x=w\_0$, then $M^\prime$ will accept anyways, which contradicts the definition of the reduction. Am I getting something wrong?

Any help would be appreciated, and if you're impressed I haven't fully grassped the methodology behind reductions, references to better explainations (other than the classic textbook's examples) would be great as well.

***EDIT:***

Okay, I now understand how to show that some language is unrecognizable via reductions from $\overline{A\_{TM}}\notin\mathcal{RE}$ and $A\_{TM}\notin co\mathcal{RE}$.

So I tried it with $L\_{2}$: $A\_{TM}\leq\_{m}L\_{2}$ seems about right, it resembles Yuval's suggestion in the comments, but I have the same trouble I had earlier convincing myself that the reduction from $\overline{A\_{TM}}$ makes sense.

---

## $A\_{TM}\leq\_{m}L\_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

```
M'(x):
  if x==w_0:
      emulate M(w)
  else:
    LOOP

```
1. $\left\langle M,w\right\rangle \in A\_{TM}\implies L\left(M^{\prime}\right)=\left\\{ w\_0\right\\} \implies\left\langle M^{\prime}\right\rangle \in L\_{2}$
2. $\left\langle M,w\right\rangle \notin A\_{TM}\implies L\left(M^{\prime}\right)=\emptyset\implies\left\langle M^{\prime}\right\rangle \notin L\_{2}$

Therefore, $A\_{TM}\leq\_{m}L\_{2}$, and since $A\_{TM}\notin co\mathcal{RE} \implies L\_{2}\notin co\mathcal{RE}$

*In this case, both implications are intuitive and make sense.*

---

## $\overline{A\_{TM}}\leq\_{m}L\_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

```
M'(x):
  if x!=w_0:
      emulate M(w)
      if M accepts:
        ACCEPT
  else:
    ACCEPT

```

Thus:

1. $\left\langle M,w\right\rangle \in\overline{A\_{TM}}\implies L\left(M^{\prime}\right)=\left\\{ w\_0\right\\} \implies\left\langle M^{\prime}\right\rangle \in L\_{2}$
2. $\left\langle M,w\right\rangle \notin\overline{A\_{TM}}\implies L\left(M^{\prime}\right)=\overline{\left\\{ w\_0\right\\} }\implies\left\langle M^{\prime}\right\rangle \notin L\_{2}$

Therefore, $\overline{A\_{TM}}\leq\_{m}L\_{2}$, and since $\overline{A\_{TM}}\notin\mathcal{RE} \implies L\_{2}\notin\mathcal{RE}$

*In this case, the 2nd implication is really intuitive but the 1st one doesn't seem right.*

# Answer
> 1 votes
It is easy to reduce $L\_1$ to $L\_2$: given a Turing machine $M$ and an input $w\_0$, construct another Turing machine $M'$ that runs $M$ if the input is $w\_0$, and loops on any other input. Then $w\_0 \in L(M)$ iff $L(M') = \\{w\_0\\}$.

In contrast, you cannot reduce $L\_2$ to $L\_1$, since otherwise the halting problem would be co-r.e. Stated differently, if there is a computable reduction from $L\_2$ to $L\_1$, then the non-halting problem (on empty input, say) is recursively enumerable. Given a machine $M$, construct a machine $M'$ which halts if the input is $0$, and otherwise clears the tape and runs $M$. Then $M$ doesn't halt on the empty input iff $L(M') = \\{0\\}$. If you could computably reduce $L\_2$ to $L\_1$, then this would give an r.e. algorithm for deciding whether $M$ doesn't halt on the empty input.

---

The halting problem reduces to both $L\_2$ and $\overline{L\_2}$. Given a Turing machine $M$ and an input $x$:

1. Construct a Turing machine $M'$ which on input $x$ executes $M$, and otherwise loops. Then $M$ halts on $x$ iff $L(M') = \\{x\\}$.
2. Construct a Turing machine $M''$ which on input $x$ executes $M$, on input $1x$ halts, and otherwise loops. Then $M$ halts on $x$ iff $L(M'') \neq \\{1x\\}$.

This shows that $L\_2$ is neither r.e. nor co-r.e.

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


title: NL-Hardness of Target

text:
# Question
Title: NL-Hardness of Target
When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:

$ TARGET = \\{\<G, t\> : t\ is\ reachable\ from\ every\ other\ node\ in\ G\\}$

Now we are allowed to use any standardly known problems that are NL-Hard in this part of the question. I considered between reducing from $REACH$ or $\overline{REACH}$, its complement - where $REACH$ is the standard NL-Complete problem. I thought perhaps $\overline{REACH}$ would reduce more naturally to $TARGET$ as the negation of $REACH$'s membership logical formula would be "$\<G,s,t\>$ where for all paths $P$ originating from $s$, $t$ is not on $P$".

However, I did not get very far from here. Then again, it is quite late in the evening and perhaps I am missing an obvious reduction here.

Many thanks for any hints and pointers!

# Answer
> 2 votes
Let us reduce REACH to TARGET. Given an instance $(G,s,t)$ of REACH, add edges from all nodes other than $s$ to $s$ to form a new graph $G'$. If $t$ is reachable from $s$ in $G$ then it is reachable from all other nodes in $G'$ using the new edges. Conversely, if $t$ is reachable from all other nodes in $G'$, then in particular it is reachable from $s$ in $G'$. Even if this path uses any of the new edges, all they can do is bring it back to the starting point, and so $t$ is reachable from $s$ already in $G$.

Altogether, we have shown that $(G,s,t)$ is a yes instance of REACH iff $(G',t)$ is a yes instance of TARGET.

---
Tags: complexity-theory, reductions, complexity-classes, space-complexity
---


# Question
Title: Advantages of Lambda calculus over Turing machine and vice versa
What kind of advantages does Lambda calculus have over Turing machine, and vice versa?

# Answer
The lambda calculus and Turing machines are equivalent models of computation, each of which formally captures the informal notion of effective calculation (this is the Church-Turing thesis). The lambda calculus is a more abstract and algebraic approach, whereas Turing machines offer a more concrete, algorithmic approach.
> 1 votes

---
Tags: turing-machines, computability, lambda-calculus
---


# Question
Title: Language whose intersection with a CFL is always a CFL (2)
This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, *intersection resilience*:

> If $L'$ is context-free then so is $L \cap L'$.

We know that all regular languages are intersection-resilient, and clearly every intersection-resilient language is context-free. Ginsburg and Spanier showed in 1964, in their paper Bounded ALGOL-like languages, that every context-free subset of $x^\*y^\*$ is intersection-resilient (Theorem 6.1, Corollary 2).

> Which languages are intersection-resilient?

# Answer
Just a few notes (I'll try to add the proofs later).

Intersection-resilience seems closed under homomorphism.

A necessary condition for intersection-resilience is that for all homomorphisms $\varphi : \Sigma \to \Sigma \cup\ \\{\epsilon \\}$; $\varphi(L) \cap x^\*y^\*x^\*$ must be a regular language (where $x$ and $y$ are any two distinct symbols of $\Sigma$).

So the result of Ginsburg and Spanier seems "tight" (if we use the same homomorphism trick).
> 1 votes

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


# Question
Title: Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L\_1,L\_2$(over the same $\Sigma$)is indeed regular:

$$L^\frown = \\{ w\in \Sigma^\* | w=u\sigma\_1\mu\_1...\sigma\_n\mu\_nv\\}$$

* $u,v \in \Sigma^\*$
* $0\leq n$, for every i($1\leq i \leq n$): $\sigma\_i,\mu\_i \in \Sigma$
* $\sigma\_1...\sigma\_n \in L\_1$
* $\mu\_1...\mu\_n \in L\_2$

I don't understand how to prove if because of the suffix and prefix(u,v accordingly).

If it weren't for u,v what I think I would've done is building an automaton(Deterministic finite automaton): $A=\left(Σ,Q1xQ2x\left\\{1,2\right\\},\left(q01,q02,2\right),F1xF2x2,δ\right)$, Ending in accepting iff both automatons that accept each language end in an accepting state, and $L\_2$ needs to be after $L\_1$ from the language's description. However, I don't know how to deal with the u,v in the beginning and in the end. I am not sure how to configure it correctly to prove $L^\frown$ is regular.

Would very much appreciate your assistance with it.

# Answer
Your language is the concatenation $\Sigma^\* L \Sigma^\*$, where $L$ is the so-called perfect shuffle of $L\_1$ and $L\_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^\* L \Sigma^\*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).
> 2 votes

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


# Question
Title: Partitioning a graph with specific constraints
We have an exercise where we need to find the partitions G\[V1\] and G\[V2\] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:

* |V1| - |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
* either
    + \[case A\] all nodes in V1 have edges to all nodes in V2
    + \[case B\] all nodes in V1 have no edges to any node in V2

We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) \< |V2| then there is a partition with case B, otherwise if we find a node v with degree(v) \> |V1| then there is a partition that fulfills case A. However other than that we have been stuck and extendind or other ideas ended in a dead end.

How do we find those partitions? I'd like to not be given the answer but only a pointer to find a easy algorithm for the problem.

# Answer
> 1 votes
It suffices to be able to identify case B, since a graph satisfies case A if, and only if, its complement satisfies B.

A graph satisfies case B if, and only if, it is composed of components of size $n\_1, \dots, n\_\ell$ and there is some set $S\subset \\{1, \dots, \ell\\}$ such that $\sum\_{i\in S} n\_i = \sum\_{j\notin S} n\_j$. (If $n\_1 + \dots + n\_\ell$ is odd, this is impossible, so include a fake component of size $1$.)

This is the set partition problem. Bad news! It's **NP**-complete. Good news! It's not strongly **NP**-complete and we're encoding the numbers $n\_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context. By checking the algorithms carefully, you can probably avoid the "fake component" trick.

---
Tags: graphs, partitions
---


# Question
Title: How does dynamic memory-allocation exactly work?
I have wondered about ordinary code. Assume we are running this code on any modern System like Unix/Linux/Mac/Windows. This code is C, but it should work with every language which is close to the hardware.

```
int a = 8;
//printf("%d", (int)&a);

```

This will show obviously that the system allocated the int dynamically. So there is no static address used. Now we continue by:

```
a = a+1;

```

Now, my question follows:

Since the address to "a" is allocated dynamically, we need presumably a pointer which points to a pointer pointing to "a". But how do we store this pointer? We would again need a dynamically allocated address and would, therefore, pass the problem. So, in my mind, we need static addresses the program can use, but how does the process know these addresses?

How does the process store its own allocations, so that after initializing a variable, the process knows what the variable actually is or at least where the variable was allocated?

If this question is not clear enough, please comment below.

Thank you!

# Answer
> 1 votes
Consider the following code:

```
int a = 8;
a = a+1;

```

On my system, this snippet compiles to the following code:

```
movl    $8, -20(%rbp)
movl    -20(%rbp), %edi
addl    $1, %edi
movl    %edi, -20(%rbp)

```

The register `rbp` points at the top of stack. The variable `a` is located 20 bytes below the top of stack.

The first assembly line about implements the C line `int a = 8`, and the rest implement `a = a+1` by first loading `a` into the register `edi`, then increasing `edi` by 1, and then storing `edi` back at `a`.

If you want to try it out, use the following command:

```
cc -O0 -S <progname>.c

```

The assembly will appear in `<progname>.s`.

---
Tags: operating-systems, memory-allocation, c
---


# Question
Title: Minimum cost to match $n$ people with $m$ shops
We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost of one matching is sum of all matchings, and for each matching its cost is calculated as Manhattan distance between those two points. It will always hold that $m \> n$.

For me, this looks a lot like the bipartite matching problem, however I'm not sure what to do with the costs of the matchings. I started thinking about algorithms that starts with one trivial matching and update it if making some other matching decreases the cost. However, I'm not sure if this will work. What is the correct way to solve this problem. I don't have much experience with matching algorithms, so I'm not sure how to approach this problem.

# Answer
Your problem is an instance of minimum bipartite perfect matching. This is known as the assignment problem, and there are known efficient algorithms.

As a first step, you should compute the weights of all edges, using the formula your are given (L1 distance between the point corresponding to the person and the point corresponding to the shop).
> 3 votes

# Answer
To convert your problem into minimum cost bipartite perfect matching, pad the smaller side with dummy vertices. Make your graph a complete bipartite graph where the cost of each edge is the Manhattan distance between the points, and all edges to the dummy vertices are large enough to essentially be infinity. Then you can use a standard assignment problem algorithm. The unmatched shops will be matched with the dummy vertices.
> 1 votes

---
Tags: bipartite-matching
---


# Question
Title: Does Google's PageRank count as a sorting algorithm?
Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?

# Answer
> 1 votes
The answer depends on what you mean by a *sorting algorithm*. The usual meaning is:

> A sorting algorithm is an algorithm that gets a list $L$ of comparable objects, and sorts them in (say) nondecreasing order. The algorithm could only work for a certain class of objects.

If you use this definition, then PageRank isn't a sorting algorithm. But it's up to you.

---
Tags: algorithms, sorting
---


# Question
Title: Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?
In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows:

"On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to simulate the execution of $M\_x$ on $x$." Here $M\_x$ is the machine encoded by string $x$.

Since we are simulating another TM on $D$, this would implicitly make $D$ a universal TM, right? If this is the case, then why is it necessary to state that $D$ will simulate $\mathcal{U}$ in order to simulate $M\_x$ when $D$ is already capable of simulating $M\_x$ directly?

On the other hand, if it is not the case that $D$ is a UTM, then why can't we "run" (whatever that means) $M\_x$ directly on $x$ instead of running $M\_x$ through $\mathcal{U}$ (in the same way that we "run" $\mathcal{U}$)? Why do we need to simulate a machine capable of simulating an arbitrary TM if we only need to simulate exactly one TM?

# Answer
The difference between $\mathcal{U}$ and $M\_x$ is that $\mathcal{U}$ can be hardcoded while $x$ is an input to the machine.

In other words, when Arora and Barak write "run $\mathcal{U}$ to simulate $M\_x$", what they mean is to switch to a part of the Turing machine which behaves like $\mathcal{U}$ (you can think of it as a function), and afterwards switch to some other part of the machine. The states of $\mathcal{U}$ do the work of simulating $M\_x$.

You are not simulating $\mathcal{U}$. You incorporate its code as part of your Turing machine. (In programming languages, this is sometimes known as *inlining*.)
> 1 votes

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


# Question
Title: Confused about 3rd rule of CFG pumping lemma
Let $L = \\{\space ww \space | \space w \in \\{0,1\\}^\*$} (need to prove that $L$ is not CFL)

Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the pumping length.

Using the 3$^{rd}$ rule, namely $|vxy| \le p$, can I say that $vxy$ can consist only of $0's$ and either pumping up(e.g. $uv^2xy^2z)$ or down ($uxz$) will throw us out of $L$ ?

# Answer
> 2 votes
Remember that the PL is stated *for any* partition $s=uvxyz$, so it is not enough to show that for one specific partition pumping $v$ and $y$ will exclude the resulting string from $L$. While it is true that $xyz$ can consist only of 0′s, it could also be the case that $xyz$ is of the form $0^i1^j$ for some $i, j \< p$, for instance. You must show that pumping excludes the resulting string from $L$ in this (and all possible other) cases as well.

# Answer
> 1 votes
Here is a decomposition $s = uvxyz$ such that $|vxy| \leq p$ but $xyz$ doesn't consist only of zeroes: $$ u = 0^p \\ v = 1^p \\ x = \epsilon \\ y = \epsilon \\ z = 0^p 1^p $$

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


# Question
Title: Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine
What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?

# Answer
> 3 votes
A Turing machine is a computation model in theory only, able to simulate any computer algorithm. By formally defining this model mathematically, Its possible to draw conclusions and limits regarding the abilities of our computers.

There are many more models, and much more literature about each of them, but below is a short review of the three mentioned in your question

---

**Deterministic Turing Machine (DTM)**:

For any given state $Q\_i$ the machine is presently at, and for any given symbol under the input alphabet $\Sigma$ the head is at, there is **exactly one** action the machine can perform.

It means in every step, the transition (and write operation) is well established, or *deterministic*, under a certain set of rules predefined into the machine.

**Non-Deterministic Turing Machine (NTM)**:

A machine like the DTM, with the important exception that in every step, it may make **more than** one transition. So for input symbol $s$ and state $Q\_i$, it may transition to to $Q\_j$, but it may also transition to $Q\_k$ and so forth.

Since in no step is the transition well established, we say the NTM "guesses" the best transition that eventually leads to an accepting state $Q\_{F}$ (if such a transition path exists).

Imagine being in a maze, and constantly having to decide whether to turn left, or right. If you always guessed the correct choice, then you will find the find the quickest way out possible (if there was one).

**Probabilistic Turing Machine (PTM)**:

A machine like the NTM, only its transition is subject to a probabiliy function (that is well established) and not "guess" like the NTM. For example, suppose the current input symbol is $s$ and state $Q\_i$, a transition can be defined as follows:

Flip 2 coins.

* If the result is ($head$, $head$), move to state $Q\_j$
* Else, move to state $Q\_k$

Unlike the DTM, we cannot say we know how the machine will act given the situation, since we don't know what the coin flip will show. However, its also not as "lucky" as the NTM, and we can often measure accurately the probability of a mistake.

---

Further reading on probabilistic classes:

Randomized polynomial time class

Bounded error polynomial time class

---
Tags: complexity-theory, turing-machines
---


# Question
Title: Minimize sequence storage by overlapping prefixes
I bumped into this problem today, and after a bit of pondering, I *think* I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can you beat my best answer?

**The Real-World Impetus**

Given a set of data $C$ that consists of nonoverlapping, nonempty, *unique* sequences $S\_1, S\_2, S\_3, ...$ of atomic values. Each sequence tends to have a lot of repeated values.

For example, in the code where I bumped into the problem, the sequences were initially something like this:

```
    9, 1, 1, 1, 1, 1;
    5, 5, 5, 3, 2;
    1, 1, 1, 1, 4;
    1, 7, 5, 5;
    4, 4, 4;
    ...

```

To access the data, there's a secondary table of offsets into the overall data to show where each sequence starts: i.e., sequence $S\_1$ starts at 1, and $S\_2$ at 7, and $S\_3$ at 13, and so on. But this means that the *sequences may occur in any order*, and they may even *overlap*.

Given that the data could overlap, it occurred to me that by reordering the sequences, I could reduce the storage required. For example, in the above data, I can reduce the size of the required storage by reordering the sequences as $S\_1, S\_3, S\_5; S\_4, S\_2$:

```
    9, 1, 1, 1, 1, 1, 4, 4, 4;
    1, 7, 5, 5, 5, 3, 2;
    ...

```

By overlapping the prefixes and suffixes, we can store 16 values instead of the original 23, a considerable savings.

**The Problem Statement**

Generalizing this, the problem, then, is to find an algorithm for ordering an arbitrary set of sequences, so that the resulting ordering will have the *maximum* overall overlap of those sequences' prefixes and suffixes.

(And for what it's worth, I don't *actually* have to solve this for the code I was working on: This is purely a question of academic interest at this point.)

**My Best Answer**

It's easy to "see" an optimal answer for trivial examples like the one above, but in the *general* case of a large number of sequences of arbitrary values, it gets hard quickly. A greedy algorithm could likely at least give an acceptable answer in polynomial time, but that wouldn't be the true minimal answer. And obviously, you can simply try every possible ordering, but $O(n!)$ is not a very nice solution either.

It occurred to me a possible solution might exist as a variation on a longest-path-through-a-weighted-graph problem. You consider each sequence $S\_1, S\_2, S\_3, ...$ as a node in a graph, and construct a directed edge anywhere $S\_n$ has a prefix that matches a suffix of $S\_m$ for all $n$ and $m$, weighted by the match length. This results in a two-step solution:

* Calculate all the edge weights. The edge weights can be calculated trivially in $O(n^2)$, or maybe even in $O(n)$ using a trie constructed via dynamic programming.
* Then for each vertex, use Dijkstra's shortest-path algorithm (or similar), inverted, to find the longest path for that vertex. Of all the possible longest paths, then take the overall longest. This is $O(n^3)$, or maybe $O(n^2\ log\ n)$ using priority queues.

I *think* this might work, with an overall time of $O(n^3)$ or maybe $O(n^2\ log\ n)$, but I haven't attempted to prove it for real (or implement it). There might also be a better technique than Dijkstra's algorithm for "longest path in the graph when you don't care what node it starts or ends on."

**Can you do better?**

Here's the problem statement again:

> Find an algorithm that can efficiently order a set of sequences $S\_1, S\_2, S\_3, ...$ such that there is maximal global overlap of their prefixes and suffixes.

Good luck; I'm curious to see if you can solve it better than I could!

# Answer
This problem is known as "Shortest Common Superstring" (or sometimes just "Shortest Superstring"). It is an NP-complete problem in general, though good approximations are known (e.g.: via approximations of weighted set cover, as outlined in the linked Wikipedia article).
> 1 votes

---
Tags: time-complexity, graph-traversal, subsequences
---


title: Speed Up Access to Fractal-Like Array

text:
# Question
Title: Speed Up Access to Fractal-Like Array
I'm trying to speed up the following function in c++:

```
void num_to_xy(int num, int *x, int *y):
    *x = (cl & 0x03) | ((cl & 0x10) >> 2) | ((cl & 0x40) >> 3) | ((cl & 0x100) >> 4) | ((cl & 0x400) >> 5) | ((cl & 0x1000) >> 6) | ((cl & 0x4000) >> 7);
    *y = ((cl & 0x0c) >> 2) | ((cl & 0x20) >> 3) | ((cl & 0x80) >> 4) | ((cl & 0x0200) >> 5) | ((cl & 0x0800) >> 6) | ((cl & 0x2000) >> 7) | ((cl & 0x8000) >> 8);

```

which basically converts `num` to an x,y coordinate. This is equivalent to getting the x,y position of `num` in the following array

$\left| \begin{array}{ccc} 0 &1 &4 &5 &16 &17 &20 &21 &...\\ 2 &3 &6 &7 &18 &19 &22 &23 &...\\ 8 &9 &12 &13 &24 &25 &28 &29 &...\\ 10 &11 &14 &15 &26 &27 &30 &31 &...\\ 32 &33 &36 &37 &48 &49 &52 &53 &...\\ 34 &35 &38 &39 &50 &51 &54 &55 &...\\ 40 &41 &44 &45 &56 &57 &60 &61 &...\\ 42 &43 &46 &47 &58 &59 &62 &63 &...\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots & \end{array} \right|$

The array above follows a pattern where for all $k,n$, all numbers between $k4^n$ and $(k+1)4^n-1$ form a perfect square.

Can the code above be sped up without generating a ginormous list and storing all the values? Or is there a completely different, faster method?

# Answer
I think that the fastest approach with modern CPUs is

```
i = num & 255
j = num >> 8
*x = x1[i] + x2[j]
*y = y1[i] + y2[j]

```

That is 4 arithmetic ops plus 4 loads
> 1 votes

---
Tags: algorithms
---


# Question
Title: Conditions for a binary tree being balanced
> Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.
>
> If you disprove, the counterexample should consist of an infinite sequence of trees in the family rather than just a single tree, because the property is asymptotic.
>
> A. There is a constant $c$ so that for each node of the tree, the difference in height between the two sub-trees is at most $c$.
>
> B. There is constant $c$ so that the average height of each node in the tree is at most $c \log n$.

Now I proved A using induction, and I know how to disprove B using a single example, but I don't know how to do so using infinitely many examples.

# Answer
> 2 votes
This is an interesting question. How do we define a family of binary trees is balanced?

**A generalized definition of balanced binary trees**

One of the most general definitions is that the height of a tree $T$ in the family is $O(\log n)$, where $n$ is the number of nodes in $T$. In other words, there is a constant $c$ such that the height of each tree $T$ in the family is no more than $c\log n$. We call such a family of binary trees balanced. Each tree in the family is called balanced (with respect to the family).

For example, the family of AVL trees is balanced. The family of red-black tree is balanced. For any given $0\lt \alpha\lt1$, $\alpha$-weight-balanced trees are balanced. A family of finitely many trees is balanced.

The family of all degenerated trees is not balanced.

**$c$-height-balanced trees are balanced**

Let $c$ be a constant. Let $T$ be a binary tree such that for each node of it, the difference in height between the two sub-trees is at most $c$. We call $T$ $c$-height-balanced. The family of $c$-height-balanced trees is balanced, which you have probably proved.

**$O(\log n)$-average-height trees may not be balanced.**

Let us call a family of trees that satisfies the condition (B) $O(\log n)$-average-height family of trees. Here is an example of an $O(\log n)$-average-height family of trees that is not balanced.

Let us start from a perfect binary tree with node $1,2, \cdots, 2^m-1$, where the children of node $i$ are node $2i$ and $2i+1$. Add node $2^m, 2^m+1, \cdots, 2^m+m^2-m$ to the tree so that the right child of node $j$ is node $j+1$ for all $j\ge 2^m-1$. Denote the tree thus obtained by $T\_m$. The number of nodes in $T\_m$ is $n=2^m+m^2-m$.

The rightmost nodes of $T\_m$, $$2^1-1, 2^2-1, \cdots, 2^m-1, 2^m, 2^m+1, \cdots, 2^m+m^2-m$$ form a linear tree with $m+ m^2-m = m^2$ nodes.

The sum of heights of all nodes is

$$\begin{aligned} \sum\_{1\le i\le 2^m+m^2-m} h(i) &= \sum\_{1\le j\le m-1}\sum\_{2^j\le i\le 2^{j+1}-2} h(i) + \sum\_{0\le j\le m-1}h(2^{j+1}-1)+ \sum\_{2^m\le i\le 2^m+m^2-m} h(i) \\ &= \sum\_{1\le j\le m-1}(2^j-1)(m-1-j) + \sum\_{1\le k\le m^2}(k-1) \\ &\lt m\sum\_{1\le j\le m-1}(2^j-1) + \sum\_{1\le k\le m^2}m^2\\ &\lt m2^m + (m^2)^2\\ &\lt 10m2^m\\ &\le 10mn.\\ \end{aligned}$$

So the average height of each node is not greater than $10m \le 10\log\_2 n.$

However, the height of node $2^m+m^2-m$ is $m^2-1=\Theta((\log n)^2)$. So the $O(\log n)$-average-height family of trees $T\_1, T\_2, \cdots$ is not balanced.

**Exercises**

**Exercises 1.** Show that the height of a tree $T$ in a given balanced family of binary trees is, in fact, $\Theta(\log n)$.

**Exercises 2.** Construct an $O(\log n)$-average-height family of trees such that the height of a tree $T$ is $\Omega(\sqrt {n})$.

**Exercises 3.** Let $F$ be a family of binary trees such that the ratio between the heights of two subtrees with the same parent node is bounded for all parent nodes of all trees. In other words, there is a constant $c$ such that for every $T$ in $F$, for every node $v$ of $T$, the ratio between the heights of two subtrees of $v$ is at most $c$. In order to avoid dividing by zero, if any subtree of $v$ is empty, the height of that empty subtree is redefined as 1/2. We call $F$ height-ratio-bounded. Is a height-ratio-bounded family balanced?

---
Tags: trees, combinatorics
---


# Question
Title: Longest path in DAG or finding DAG diameter
A directed acyclic graph (DAG), is a directed graph with no directed cycles.

That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.

we have several algorithms to finding shortest path from one vertex to another(Dijkstra algorithm and Bellman-ford algorithm) or such algorithms to find shortest path from every to vertices( floyd-Warshall algorithm and Johnson algorithm)

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path. and we could use many other features in DAG.

Is any polynomial time order algorithm for this problem....?

thanks

# Answer
> But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

That's not how the *diameter* is usually defined; it's rather the maximum *distance*, i.e. the length of the longest shortest path. As such, any general-purpose APSP algorithm helps you find the diameter of DAGs.

> here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path.

Infinite loops are not the problem; finding longest paths is NP-hard in general graphs.

> Is any polynomial time order algorithm for this problem....?

As explained on Wikipedia \[1\], the Longest Path problem can indeed be solved efficiently on DAGs by finding the shortest path in the graph obtained by multiplying all weights by $-1$.

---

1. Algorithms by R. Sedgewick and K. Wayne (2011)
> 2 votes

# Answer
It can be solved in $O( V + E)$

We initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using the distance of current vertex.

The following figure shows step by step process of finding the longest paths.  source geeksforgeeks.

pseudocode:

```
1) Initialize dist[] = {NINF, NINF, ….} and dist[s] = 0 where s is the source vertex. Here NINF means negative infinite.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
    Do following for every adjacent vertex v of u:
        if (dist[v] < dist[u] + weight(u, v)):
            dist[v] = dist[u] + weight(u, v)

```
> 1 votes

---
Tags: algorithms, graphs, time-complexity, optimization, dag
---


# Question
Title: Construct a DFA from the regular expression (a)*+(aab)*
I've broken down the expression into two simpler DFAs but right now I'm stuck.

I don't know what to do with the expression a\*, my solution currently (as presented above) is a NFA, not DFA.

# Answer
> 0 votes
The approach of combining two smaller DFAs is right. However, it is not correct to superimpose one DFA on another simply. For example, your combined DFA accepts $aaab$, which is not included in $a^\*+(aab)^\*$.

The correct way to combine two DFAs so as to produce the union of their languages is to construct the product automaton of them, defining the new final states appropriately. Please check this question and answer for details.

For the current case, we can use more states in the DFA so that it remembers more about the input string and it is deterministic enough to stipulate each transition.

$$\begin{aligned} q\_0&: \text{for the empty string}.\\ q\_{a}&: \text{for string }a.\\ q\_{aa}&: \text{for string }aa.\\ q\_{aaaa^\*}&: \text{for strings } aaa, aaaa, \cdots.\\ q\_{aab(aab)^\*}&: \text{for strings } aab, aabaab, \cdots.\\ q\_{aab(aab)^\*a}&: \text{for strings } aaba, aabaaba, \cdots.\\ q\_{aab(aab)^\*aa}&: \text{for strings } aabaa, aabaabaa, \cdots.\\ q\_{\text{reject}}&: \text{for all other strings.}\\ \end{aligned}$$

$q\_0$ is the initial state. $q\_0, q\_{a}, q\_{aa}, q\_{aaaa^\*}$ and $q\_{aab(aab)^\*}$ are accept states. $q\_{reject}$ is a dead state.

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


# Question
Title: how to find total paths in a graph which have only one vertex common with a given path
Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.

How can I find the total number of paths in the graph that do not share any edge with the (unique) path from $a$ to $b$ and have only one vertex in common with it?

For example, suppose I have following graph :

and am given $a=4$, $b=5$. Then there are six paths satisfying the above condition: $(1,1)$, $(1,3)$, $(2,2)$, $(2,6)$, $(4,4)$, $(5,5)$ where $(x,y)$ is the path from $x$ to $y$.

# Answer
> 3 votes
Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes.

Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. You want to compute the number of different paths passing through $a$. There are two possibilities:

* either $a$ has only one neighbour: then the possible paths are the $N$ paths ($a$, $i$) with $i \in N$
* either $a$ has several neighbours: then count the number of vertices in the subtree of each of these neighbours. The number of possible paths is the sum of the cross-products more the $N$ paths having $a$ as start.

Note that $T$ may have between $n$ and $n^2$ paths through $a$.

To answer your question, just sum all the trees' number of paths.

EDIT: small examples

If the tree has 4 vertices called $a,b,c,d$, connected linearly like that $a-b-c-d$ with $a$ being the vertex of the given path. Then $a$ has only 1 neighboor and the possible paths are all the $(a, i)$ =\> \[$(a,a),(a,b),(a,c), (a,d)$\]

If the tree has 5 vertices $a $(of the given path)$, b, c, d, e$ connected like that:

```
    b-a-c-d
      |
      e

```

Then $a$ has 3 neighboors leading to the 3 subtrees: $b, c-d$ and $e$. The possible paths are:

* all the $(a, i)$ =\> \[$(a,a),(a,b),(a,c), (a,d), (a,e)$\]
* the cross-products between $b$ and $c-d$: \[$(b, c), (b, d)$\]
* the cross-products between $e$ and $c-d$: \[$(e, c), (e, d)$\]
* the cross-products between $b$ and $e$: \[$(b, e)$\]

total 10 paths.

---
Tags: algorithms, graphs, trees
---


# Question
Title: Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?
The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when minimizing the resulting DFA. The most common case is when states are "unreachable" from the corresponding start state.

I am interested in the following question: if we have an NFA with $n$ states and $q$ symbols, is there a $\mathrm{poly}(n, q)$-time algorithm to output the *number* of states that the standard conversion (and minimizing, if possible) to a DFA would produce? Note that producing the DFA itself can take exponential time.

# Answer
It is well known that NFA universality (given an NFA, does it accept all words?) is PSPACE-complete. This easily implies that the following problem is PSPACE-complete:

> Given an NFA, is there an equivalent DFA with exactly one state?

To show that the problem is in PSPACE, note that in order to show that an NFA *isn't* equivalent to a DFA with exactly one space, it suffices to show that its language is not universal (known to be in PSPACE) and non-empty (can be checked in P).

To show that the problem is PSPACE-hard, we reduce from NFA universality. Given an NFA $A$ over the alphabet $\Sigma = \\{0,1\\}$, we construct an NFA for the language $L = \epsilon + 0\Sigma^\* + 1L(A)$; this requires adding a constant number of states. The language $L$ is never empty, and it is universal iff $L(A)$ is, hence $L(A)$ is universal iff $L$ is accepted by a DFA having a single state.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Time complexity of subset sum problem with reals instead?
It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete still or harder (NP-hard)?

# Answer
> 1 votes
What model of real numbers are you using? If it's something like floating point, where everything is really rational, just multiply through by a common denominator and you're back in the world of integers. The bit-length is only polynomially larger than the ones you started with (the common denominator is at most the product of $n$ $n$-bit numbers, so it has at most $n^2$ bits), so nothing has changed, complexity-wise.

Beyond that, things will get more complicated – can you even tell in polynomial time what numbers are represented by the input?

However, the real-number version is definitely still **NP**-hard, since it has the integer version as a sub-problem.

---
Tags: np-complete, np-hard, subset-sum
---


# Question
Title: NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}
Consider the following decision problems:

$CONN$= {$〈G,k〉$$G$ is undirected graph with at least $k$ connected components}
$E-CONN$= {$〈G,k〉$$G$ is undirected graph with exactly $k$ connected components}

I'd like to show this two problem are in $NL$. I Know it's possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it's impossible to hold $k$ vertices on the work tape?

# Answer
We can assume without loss of generality that the vertex set is $1,\ldots,n$. Let us say that a vertex is *minimal* if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.

A graph has at least $k$ connected components iff there is a list $v\_1 \< v\_2 \< \cdots \< v\_k$ of minimal vertices. This shows that CONN is in NL. Since NL=coNL, it follows that E-CONN is also in NL.

Morale: if you want to make sure that you guessed $k$ *distinct* vertices, guess them in increasing order.

---

Since undirected connectivity is in L, we can actually count the number of connected components in L, by just going over all vertices, and counting how many of them are minimal.
> 4 votes

---
Tags: complexity-theory, graphs, nondeterminism
---


# Question
Title: Showing Maximum Independent Set is $NP-hard$
I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that the most straight forward reduction? Is it can also be shown directly from Clique problem?

# Answer
Clique is the decision version of Maximum Clique, which is an optimization problem:

* Clique: Given a graph $G$ and an integer $k$, decide whether there is a $k$-clique in $G$.
* Maximum Clique: Given a graph $G$, find the maximum size of a clique.

*Let me mention that these names are not standard. Other people might use Clique or Maximum Clique to refer to slightly different problems. Optimization problems and their decision versions are often confused in the literature, since usually it is clear from context which of the two is referred to.*

There is a canonical way to convert an optimization problem to a decision problem, demonstrated above. This conversion ensures, in most circumstances, that the decision version is in NP.

We say that an optimization problem is NP-hard if its decision version is. To show that Maximum Independent Set is hard, you really need to show (*by definition*) that Independent Set is hard; and this you can do by reduction from Clique (not Maximum Clique).

Also, Clique and Independent Set are really the same problem — you get one from the other by complementing the graph.

Finally, let me stress that Independent Set is NP-complete, but it is not known to be in coNP or to be coNP-hard; indeed, it is conjectured *not* to be in coNP and *not* to be coNP-hard (otherwise NP=coNP).
> 3 votes

---
Tags: complexity-theory, graphs, reductions
---


title: Why are ambiguous grammars bad?

text:
# Question
Title: Why are ambiguous grammars bad?
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.

# Answer
Consider the following grammar for arithmetic expressions: $$ X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const} $$ Consider the following expression: $$ a - b - c $$ What is its value? Here are two possible parse trees:

According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.

When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.

---

Parse trees generated using syntax tree generator.
> 57 votes

# Answer
In contrast to the other existing answers \[, \], there is indeed a field of application, where ambiguous grammars are **useful**. In the field of natural language processing (NLP), when you want to parse natural language (NL) with formal grammars, you've got the problem that NL is inherently ambiguous on different levels \[adapted from Koh18, ch. 6.4\]:

> * Syntactic ambuigity:
>
> > Peter chased the man in the red sports car
>
> *Was Peter or the man in the red sports car?*
> * Semantic ambuigity:
>
> > Peter went to the bank
>
> *A bank to sit on or a bank to withdraw money from?*
> * Pragmatic ambuigity:
>
> > Two men carried two bags
>
> *Did they carry the bags together or did each man carry two bags?*

Different approaches for NLP deal differently with processing in general and in particular these ambuigities. For example, your pipeline might look as follows:

1. Parse NL with ambiguous grammar
2. For every resulting AST: run model generation to generate ambiguous semantic meanings and to rule out impossible syntactic ambiguities from step 1
3. For every resulting model: save it in your cache.

You do this pipeline for every sentence. The more text, say, from the same book you process, the more you can rule out impossible superfluous models, which survived until step 3, from previous sentences.

As opposed to programming language, we can let go of the requirement that every NL sentence has precise semantics. Instead, we can just bookkeep multiple possible semantic models throughout parsing of larger texts. From while to while, later insights help us to rule out previous ambiguities.

If you want to get your hands dirty with parsers being able to output multiple derivations for ambiguous grammar, have a look at the Grammatical Framework. Also, \[Koh18, ch. 5\] has an introduction to it showing something similar to my pipeline above. Note though that since \[Koh18\] are lecture notes, the notes might not be that easy to understand on their own without the lectures.

---

**References**

\[Koh18\]: Michael Kohlhase. "Logic-Based Natural Language Processing. Winter Semester 2018/19. Lecture Notes." URL: https://kwarc.info/teaching/LBS/notes.pdf. URL of course description: https://kwarc.info/courses/lbs/ (in German)

\[Koh18, ch. 5\]: See chapter 5, "Implementing Fragments: Grammatical and Logical Frameworks", in \[Koh18\]

\[Koh18, ch. 6.4\] See chapter 6.4, "The computational Role of Ambiguities", in \[Koh18\]
> 13 votes

# Answer
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.

In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
> 11 votes

# Answer
Does `IF a THEN IF b THEN x ELSE y` mean

```
IF a THEN
    IF b THEN
        x
    ELSE
        y

```

or

```
IF a THEN
    IF b THEN x
ELSE
    y

```

? AKA the dangling else problem.
> 9 votes

# Answer
Take the most vexing parse in C++ for example:

```
bar foo(foobar());

```

Is this a function declaration `foo` of type `bar(foobar())` (the parameter is a function pointer returning a `foobar`), or a variable declaration `foo` of type `int` and initialized with a default initialized `foobar`?

This is differentiated in compilers by assuming the first unless the expression inside the parameter list cannot be interpreted as a type.

when you get such an ambiguous expression the compiler has 2 options

1. assume that the expression is a particular derivation and add some disambiguator to the grammar to allow the other derivation to be expressed.
2. error out and require disambiguation either way

The first can fall out naturally, the second requires that the compiler programmer knows about the ambiguity.

If this ambiguity stays undetected then it is possible that 2 different compilers default to different derivations for that ambiguous expression. Leading to code being non-portable for non-obvious reasons. Which leads people to assume it's a bug in one of the compilers while it's actually a fault in the language specification.
> 6 votes

# Answer
I think the question contains an assumption that's only borderline correct at best.

In real life it's pretty common to simply live with ambiguous grammars, as long as they aren't (so to speak) too ambiguous.

For example, if you look around at grammars compiled with yacc (or similar, such as bison or byacc) you'll find that quite a few produce warnings about "N shift/reduct conflicts" when you compile them. When yacc encounters a shift/reduce conflict, that signals an ambiguity in the grammar.

A shift/reduce conflict, however, is usually a fairly minor problem. The parser generator will resolve the conflict in favor of the "shift" rather than the reduce. The grammar is perfectly fine if that's what you want (and it does seem to work out perfectly well in practice).

A shift/reduce conflict typically arises in a case on this general order (using caps for non-terminals and lower-case for terminals):

```
A -> B | c
B -> a | c

```

When we encounter a `c`, there's an ambiguity: should we parse the `c` directly as an `A`, or should we parse it as a `B`, which in turn is an `A`? In a case like this, yacc and such will choose the simpler/shorter route, and parse the `c` directly as an `A`, rather than going the `c` -\> `B` -\> `A` route. This can be wrong, but if so, it probably means you have a really simple error in your grammar, and you shouldn't allow the `c` option as a possibility for `A` at all.

Now, by contrast, we could have something more like this:

```
A -> B | C
B -> a | c
C -> b | c

```

Now when we encounter a `c` we have conflict between whether to treat the `c` as a `B` or a `C`. There's a lot less chance that an automatic conflict resolution strategy is going to choose what we really want. Neither of these is a "shift"--both are "reductions", so this is a "reduce/reduce conflict" (which those accustomed to yacc and such generally recognize as a much bigger problem than a shift/reduce conflict).

So, although I'm not sure I'd go quite so far as to say that anybody really *welcomes* ambiguity in their grammar, in at least some cases it's minor enough that nobody really cares a whole lot about it. In the abstract they might like the idea of removing all ambiguity--but not enough to always actually do it. For example, a small, simple grammar that contains a minor ambiguity can be preferable to a larger, more complex grammar that eliminates the ambiguity (especially when you get into the practical realm of actually generating a parser from the grammar, and finding that the unambiguous grammar produces a parser that won't run on your target machine).
> 6 votes

---
Tags: compilers, ambiguity
---


# Question
Title: Count paths of length $n$ that a player can take
I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move left, right, or up. The caveat is that the character cannot go back to the same position in a path.

I've come up with a mediocre brute-force method the count the paths, but any ideas on an efficient way to calculate this?

# Answer
> 1 votes
This is a question in combinatorics, and can be calculated in a closed formula.

The key settings are:

* "Down" is not allowed
* Visiting previously visited square is not allowed

From the two requirements, we can draw the following conclusions:

* **Up** is always a valid move (since we never went down, going up is essentially revealing a new square)
* **Left** is not valid after **Right**, but is valid after **Up** (revealing new row) or after **Left** (which is essentially unvisited)
* **Right** is not valid after **Left**, but is valid after **Up** (revealing new row) or after **Right** (which is essentially unvisited)

Denote $U$, $L$ and $R$ for **Up**, **Left** and **Right** respectively. We can now represent a path in a string like so: $P = (U,U,U,U,L)$

The question is now: How many valid paths strings of length $n$ are there?

---

Let $T(n)$ be the number of valid strings of length $n$

* If the first move is $U$ then the remaining strings are $T(n-1)$
* If the first move is $L$ then the remaining strings are those starting with $L$ or $U$
* If the first move is $R$ then the remaining strings are those starting with $R$ or $U$

Looking at strings where the first move is either $L$ or $R$: the remaining strings are: strings starting with $U$ (twice), starting with $L$, or starting with $R$. (simple summation of all the options in 2nd and 3rd bullet).

Note that all the strings starting with $U$ \+ all the strings starting with $L$ \+ all the strings starting with $R$ is exactly $T(n-1)$ since the first move is already set.

We are left with one more instance of "all the strings starting with $U$" = $T(n-2)$ (again, first move is set)

Which results the following recursive formula: $$T(n) = 2T(n-1)+T(n-2)$$ where:

$$T(1) = 3, \space T(2) = 7 $$

---

Calculations omitted, the closed formula for the relation above is:

$$T(n)= \frac{(1+\sqrt{2})^{n+1}}{2} + \frac{(1-\sqrt{2})^{n+1}}{2} $$

# Answer
> 0 votes
Obervations :

* As you only allow for up and left/right moves, when you leave a row (by going up), you can't come back to it.
* As you cannot revisit the same node in a given path, when you go right on a row, you can't go left afterwards.

I think this can lead to a direct formula for paths of length $n$, but you can first try to compute the paths with $k$ moves up, and then sum for $k$ from 0 to $n$ (and you get a recurrence relationship here)

---
Tags: algorithms, graphs, combinatorics
---


# Question
Title: Is time complexity more important than space complexity?
I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it will take. Or the time to find the discrete log for a public key.

Edit:

While writing this question, I pondered that maybe because for most algorithms in cryptography (that I have seen) , have O(1) space time complexity. i.e. If the solution does not work, we throw it away and encrypt.

Clarification on this will be really helpful.

# Answer
> 8 votes
In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon which applies to the cryptography as well.

* There are much more about time-complexity to talk about in computer science and software industry while space-complexity is more restricted to hardware. It occurs to me that there are over 10 times more tasks/techniques/concepts/results/articles about time-complexity than space-complexity. Overwhelmingly, programming contests are about time-complexity.
* Space/memory can be reused easily. Available space can be expanded easily. On the other hand, time needed for computing cannot be shorten that easily. Parallelization helps, but it cannot speed up the serial part of the program. Practically and relatively speaking, we are enjoying the cheap memory now while we are still hungry for computing speed.

Now come to the cryptography side of the question.

* As you have observed, most algorithms in cryptography have $O(1)$ space time-complexity. Although space might be critical such as in embedded devices, there is not much value of space-complexity in general.
* On the other hand, the time-complexity is the critical factor of a cryptographic algorithm, especially in encryption/decryption. It should produce data fast enough. Authorized users should be able to retrieve the plaintext fast enough while adversaries do not have fast algorithms to decrypt the ciphertext.

# Answer
> 4 votes
To add to what Apass.Jack said, in most computational models (e.g. Turing Machines, maybe RAM as well, I don't know), space used is bounded by time : you need to do at least one operation per unit of memory to "use" it.

For example you won't find algorithms with $O(n^2)$ time complexity and $O(2^n)$ space complexity.

Space complexity is usually studied/mentioned when it is critical, for example when it is as big as the time complexity (e.g. Shank's algorithm with $O(\sqrt{n})$ time and space complexity in crypto)

# Answer
> 3 votes
If you are looking at theoretical results, they are theoretical.

If you are looking at practical results, the one that is more important is the one that keeps you from getting results. For the price of a small new car, I can buy a computer with $2 \cdot 10^{12}$ bits of RAM, which can perform about $5 \cdot 10^{15}$ operations per day. With that computer, the space needed MUST be below $2 \cdot 10^{12}$ bits, or I cannot solve that problem. The number of operations SHOULD be below $5 \cdot 10^{15}$, or I will have to wait quite a while for results - but for say $10^{17}$ operations I still have the choice between being patient or investing the time into improving the algorithm or the implementation.

---
Tags: algorithms, time-complexity, cryptography
---


# Question
Title: Why ambiguous grammars are allowed for operator precedence parser?
I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of operations like a-b-c now if we operate it with two different parse trees, say one like (a-b)-c and other like a-(b-c) there meaning changes.. So how can we allow ambiguous grammar in operator precedence parser? shouldn't it be the opposite?

# Answer
> 3 votes
An operator precedence parser usually has no ambiguity at all. However, the evaluation order is not determined by the parse tree, but by the operator precedences and associativities.

As a practical example, the Swift language doesn't *define* operator precedence or associativity in the language. It doesn't even define operators, except that the scanner knows which sequences of letters could be operators. The actual operators and precedence / associativity are define by the programmer, or as part of the standard library. As a result, a+b\*c\>d/e produces a parse tree that just consists of the five operands and four potential operators. The parse *is* unique, but doesn't tell how the expression should be evaluated.

The next phase checks that all the four potential operators *are* indeed operators. Then the priorities and associativity of the operators, as defined by the programmer or standard library, are examined. * and / have highest priority, + has lower, and \> has even lower priority. If you had a-b-c, then the two operators have the same precedence, and both are left-associative, so the order is also clear. If you had two or more consecutive operators with same priority and different associativity, or with no associativity, that would be an error.

You couldn't define a grammar to handle operators, because their precedence and associativity are not even known when you start compiling.

---
Tags: parsers, ambiguity
---


# Question
Title: Incentive for block creation in a private blockchain
Bitcoin miners are incentivized to produce valid blocks via a trasactional reward. But let's say I wanted to implement blockchain as part of my private data system. Who would my miner's be? I think could just have one automated miner (on a dedicated machine) with the proof-of-work difficulty being set to something very easy. But then I'm wondering, what's the point? Is there anything to gain by using a blockchain like this?

In other words, can someone please give an example---no matter how crude---of how someone could use a private blockchain to log transactions, or whether such a thing has any practical benefit to the users?

# Answer
The blockchain would no longer be completely decentralized. You would have a *dictator*, or a *central authority* that decides which transactions get processed and which do not.

At this point you could just as well skip the blockchain part of the transaction system as well.
> 1 votes

---
Tags: blockchain
---


# Question
Title: Using pumping lemma to prove irregularity of regular language - what is my error?
I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong?

L={ab}, assume the language is regular so by the pumping lemma there exists some n, and σ = αβγ and σ' = αβ^kγ ∈ L for all non negative k.

σ = aaabbb

α = aa

β = ab

γ = bb

then σ'= αβ^2γ for k=2, σ' =aaababbb

σ'∉ L, a contradiction, thus L is not regular.

L as described I know to be a regular language so I would expect to find ∈ L. This is due to my choice of β spanning across two characters but there is nothing I can find in the pumping lemma which forbids this.

# Answer
> 1 votes
The pumping lemma **gives** you a pumping length $n$ and $\alpha, \beta, \gamma$ under the conditions specified in it so that $\alpha \beta^k \gamma \in L$ for all $k \ge 0$. You **do not** get to choose $\alpha, \beta, \gamma$ as you please. Also, the pumping lemma works for all words *of length at least $n$*, not simply an arbitrary word $\sigma$.

The trick when using the pumping lemma, then, is picking a word longer than the pumping length and such that *any* decomposition into $\alpha, \beta, \gamma$ (obeying the conditions specified in the lemma) can be used to derive the contradiction that you need.

# Answer
> 0 votes
Take $n=3$. Since there are no words of length $\ge n$, trivially all such words can be pumped.

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


title: P is contained in NP ∩ Co-NP?

text:
# Question
Title: P is contained in NP ∩ Co-NP?
How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$?

I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.

# Answer
> 7 votes
A language $L$ is in $P$, we have an algorithm $A$ that runs in polynomial time that recognizes it.

It is easy to show that the complement of $L$, $\bar{L}$, is in $P$. The algorithm to recognize it is to simulate $A$ but just invert the answer.

As long as $\bar{L}$ is in P (thus in NP), $L$ is in $co-NP$.

# Answer
> 3 votes
P can be defined as a set of problems that can be decided by a deterministic Turing machine in polynomial time.

NP can be defined as a set of problems whose solutions can be accepted by a *non*-deterministic Turing machine in polynomial time. Similarly co-NP is a set of problems whose non-solutions can be accepted by a non-deterministic Turing machine in polynomial time.

Since every deterministic TM is also a non-deterministic one, if a problem is in $P$, you can use its decision TM to check solutions and non-solution in the definition of NP and co-NP.

# Answer
> 0 votes
There is already an answer addressing the NTM definition of $\mathbf{NP}$, so let me address the equivalent definition based on proof systems. (For a proof, check your favorite computational complexity textbook.)

$\mathbf{P}$ is the class of problems solvable by a TM in polynomial time (in the length of the input). $\mathbf{NP}$ is the class of problems such that for every such problem $P$ there is a TM called a *verifier* $V$. As input, $V$ receives, in addition to the standard input $x$, a *witness* $y$ whose length is bounded by a polynomial in $|x|$ (i.e., $|w| \le p(|x|)$ for some polynomial $p$). For $V$ to be a verifier, it must satisfy the following two requirements:

1. *Completeness*: If $x \in P$, then there exists a witness $y$ (with polynomially bounded length) such that $V(x, y) = 1$, that is, $V$ accepts when given input $x$ and $y$.
2. *Soundness*: If $x \not\in P$, then $V(x, y) = 0$, that is, $V$ rejects for any witness $y$.

In addition, $V$ must run in time polynomial in $|x|$.

Now, notice that, in this setting, $\mathbf{P} \subseteq \mathbf{NP}$ is also a pretty basic fact: Any TM solving a problem $P \in \mathbf{P}$ in polynomial time can be made a verifier simply by giving it the empty string as witness.

On the other hand, $\mathbf{coNP}$ is the set of problems such that their complement is in $\mathbf{NP}$. If $P \in \mathbf{P}$, then its complement $\bar{P}$ is also in $\mathbf{P} \subseteq \mathbf{NP}$ (see also Alex Grilo's answer). It follows that $\bar{P} \in \mathbf{coNP}$.

---
Tags: complexity-theory, np, polynomial-time
---


# Question
Title: Building heaps and heapsort using linked list
I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.

One of the answers here (https://stackoverflow.com/a/14584517/5841727) says that heap sort can be done in O(nlogn) using linked list which is same as with arrays.

For building a heap, I think that heapify operation would cost O(n) time in linked list and we would need (n/2) heapify operations leading to time complexity of O(n^2). Is it correct?

Also, can someone please tell how to achieve O(nlogn) complexity (for heap sort ) using linked list ?

# Answer
doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list. merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.
> -1 votes

---
Tags: algorithms, algorithm-analysis, data-structures, time-complexity, heaps
---