# Question
Title: Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Let $$L\_\emptyset = \\{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L\_\emptyset$?

It seems that the same technique used to show that $\\{A \mid A \text{ is a DFA and } L(A)=\emptyset\\}$ should work here as well.

# Answer
> 10 votes
$A$ is undecidable because of Rice's Theorem, which states that non trivial properties of partial functions are not decidable.

1. There is a TM which doesn't accept any string. (Which directly goes to the reject state).
2. There is a TM which accepts every string. (Which directly goes to the accept state).

This means that the functions computed by elements of $A$ have a non trivial property. Hence $A$ is not decidable.

$E$ is decidable only under the assumption that DFAs are encoded in a special way like state transition table or etc. (we cannot decide whether a TM only accepts regular languages, because of Rice's Theorem!). In this case Rice's Theorem is not applicable because the particular encoding of an element is required to decide on $E$. So we don't just decide on partial functions.

(That is to say if the problem were, deciding whether a particular TM is a DFA -- or DFA computable -- and the language accepted by it is empty, $E$ would be undecidable through Rice's Theorem. Notice that in this case $A = E$.)

# Answer
> 9 votes
By marking, you probably mean reachability analysis - looking for a path from the initial state to an accepting state. Indeed, the language of a DFA is empty iff there is no such path.

Let's start with an example as to why this fails in TMs. Consider a TM that, in $q\_0$, ignores it's input, but writes $a$ on it's tape, moves the head right and goes to state $q\_1$, then in $q\_1$ it again ignores the input, writes $a$, moves the head left and goes to $q\_2$. In $q\_2$, if it reads $a$, then it writes $a$, moves the head right and goes back to $q\_1$.

That is, the machine just writes $a$ and alternates between two states ($q\_1$ and $q\_2$) and always has two adjacent $a$'s on the tape.

We now add a transition from $q\_2$ that when reading $b$ goes to an accepting state and halts.

The language of this machine is empty. Indeed, the run always gets stuck in the $q\_1-q\_2$ loop, and will never get to the accepting state. Yet, there is a state-path to an accepting state. So what went wrong?

Well, intuitively, the \`\`state'' of a TM is not informative enough to describe the continuation of the run. In order to have all the information, you need the *configuration* of the TM, which includes the state, the position of the head, and the contents of the tape. If you find a configuration-path (which is called a *run*) to an accepting configuration, then indeed the language is non-empty, and it is an iff condition.

The problem with using reachability analysis on the configuration graph, is that it may be infinite. This is why deciding language emptiness is undecidable.

This is also why language non-emptiness is recognizable - you can perform a BFS on the infinite configuration graph. If there is a path to an accepting state, you will find it eventually. If there isn't, however, then you may get stuck in an infinite search.

# Answer
> 6 votes
Another hint: Try reducing the halting problem to $L\_\emptyset$.

(The original hint is to use Rice's theorem, but in this case a direct proof is also pretty simple.)

# Answer
> 2 votes
**Lemma 1**: If L is undecidable then so is the complement of L.

We know that the halting problem, $H\_{TM}$ is undecidable. Therefore, according to **Lemma 1** complement of halting problem, $H\_{TM}^c$ too is undecidable.

$H\_{TM}$ = $ \\{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \\} $

$H\_{TM}^c$ = $ \\{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \\} $

$E\_{TM}$ = $ \\{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \\} $

Assume that $E\_{TM}$ is decidable. We will reduce $H\_{TM}^c$ to $E\_{TM}$ – in other words we will show how to construct a Turing Machine $M\_{H\_{TM}^c}$ that decides $H\_{TM}^c$ using the TM, $M\_{E\_{TM}}$ that decides $E\_{TM}$. This gives us a contradiction, because we know that $H\_{TM}^c$ is undecidable, and so $M\_{H\_{TM}^c}$ cannot exist. The word “reduce” simply means solving a given problem by converting it into another problem which we already know to solve. So, the Turing Machine for $H\_{TM}^c$ can be constructed as follows:

$M\_{H\_{TM}^c}$ = “on input $\langle M,x \rangle$

$\qquad$ 1. Construct the code for a TM, $M\_1$ that does the following:

$\qquad$ $\quad$ $M\_1$ = "on input $w$

$\qquad$ $\quad$ 1. Simulate $M$ on $x$.

$\qquad$ $\quad$ 2. Accept if $M$ halts."

$\qquad$ 2. Run $M\_{E\_{TM}}$ on $\langle M\_1 \rangle$

$\qquad$ 3. Accept if $M\_{E\_{TM}}$ accepts, reject otherwise."

It is crucial to understand that the TM $M\_1$ is never actually simulated – such simulation could go into an infinite loop. All we are doing is constructing the code for $M\_1$.

$M\_1$ is constructed such that on any input $w$ given to it, it will simulate $M$ with input $x$. $M$ can halt or loop on $x$ and hence there can be two cases:

$\quad$ 1. $M\_1$ accepts all inputs $w$ if $M$ halts on $x$. $M\_{E\_{TM}}$ will reject $M\_1$ as $L(M\_1) \neq \emptyset$.

$\quad$ 2. If $M$ loops on $x$, $M\_1$ will also loop for every input $w$ given to it. Anyway, as $M\_{E\_{TM}}$ is a $\quad$decider it will reject and halt on input $M\_1$ as $L(M\_1) = \emptyset$.

$Correctness$: Since $M\_{E\_{TM}}$ always halts (by our assumption), $M\_{H\_{TM}^c}$ also always halts. $M\_{H\_{TM}^c}$ accepts if $M\_{E\_{TM}}$ accepts, that is if $L(M\_1) = \emptyset$ which happens if $M$ loops on $x$.
$M\_{H\_{TM}^c}$ rejects if $M\_{E\_{TM}}$ rejects that is $L(M\_1) \neq \emptyset$ which happens if $M$ halts on $x$. Thus, $M\_{H\_{TM}^c}$ decides $H\_{TM}^c$ which is a contradiction as $H\_{TM}^c$ is undecidable.

---

$Nb: $

Let **R** be the reduction from $H\_{TM}^c$ to $E\_{TM}$.

The reduction gives:

i) $\langle M, x \rangle \in H\_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E\_{TM}$

$\qquad$ **M** loops on input **x** iff the language recognised by $R(\langle M,x \rangle)$ accepts nothing

ii) $\langle M, x \rangle \notin H\_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E\_{TM}$

$\qquad$ **M** halts on input **x** iff the language recognised by $R(\langle M,x \rangle)$ accepts something

# Answer
> 0 votes
Proof by contradicting $A\_{TM}= \\{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\\}$, (which we know is undecidable).

Assume the existence of $R\_{TM}$, a TM that decides $L\_\emptyset$

Use can then use $R\_{TM}$ in the construction of a TM $S\_{TM}$, which is a decider for $A\_{TM}$

$S\_{TM}=^{definition}$ "On input $\langle M,w\rangle$, where $M$ is the encoding of a TM and $w$ is a string:

1. Modify $M$, taking into account the input $w$, such that the new $M$ (call it $M\_1$) rejects all input which is not equal to $w$, where $w$ is built into its description. If the input is equal to $w$, then $M\_{1}$ runs $M$ on $w$ and outputs whatever $M$ outputs.
2. Run $R\_{TM}$ with the input $\langle M\_1,w\rangle$
3. Output the opposite of $R\_{TM}$s output."

The assumption that there exists a Turing Machine deicer for $L\_\emptyset$, allows us to construct a decider for $A\_{TM}$, which is a contradiction.

# Answer
> -2 votes
**E={ | M is a TM and L(M)=Φ}. Is E Turing-recognizable?**

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language.

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E. Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything. Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.

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


# Question
Title: How many languages exist over the following alphabets?
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.

For the first two alphabets in (a), we know that there are countably infinite words: $$|\Sigma| = |\mathbb{N}|$$

For the alphabet in (b) we know we have $k^n$ number of words.

Now I need to find the number of languages that exist for the symbol set $(a)$ and $(b)$.

I think the number of alphabets is also countably infinite, so it has the same size as the power set of $\Sigma$ which has a cardinality $|\Sigma| = |\mathbb{N}|$, therefore there are $2^{|\mathbb{ℕ}|}$ languages.

Now my question is, does this $k^n$ have a role in this $2^{|\mathbb{ℕ}|}$; does it change anything?

# Answer
A language over an alphabet $\Sigma$ is any subset of the set of all finite strings with elements in $\Sigma$. If $\Sigma$ is finite or countably infinite, and not empty, then the set of all finite strings with elements in $\Sigma$ is countably infinite ($\aleph\_0$) and the set of all languages over the alphabet $\Sigma$ has the same cardinality as the real numbers ($\aleph\_1$). (Not calling it just "uncountable", because the set of languages is indeed uncountable, but there are uncountable sets with higher cardinality).
> 1 votes

# Answer
A language over a set of words $S$ is just a subset of $S$. So the total number of such languages is $|P(S)| = 2^{|S|}$.

If we take $S$ to be $\\{0\\}^\*$ then indeed $|S| = |\mathbb{N}|$, and the total number of languages is $2^{|\mathbb{N}|}$. The same goes for $S = \\{a,b\\}^\*$.

If $S$ is the set of all words of length $n$ over an alphabet of size $k$, then $S$ has $k^n$ elements. So the number of languages over $S$ is $2^{k^n}$.
> 0 votes

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


# Question
Title: Decide whether a DFA accepts the empty language
Let $X = \\{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\\}$ where $\langle M \rangle$ is an encoding of the machine $M$. Is $X$ Turing decidable? Why or why not?

# Answer
Re-read your textbook chapter on DFAs and NFAs -- you'll find everything you need to know there.

See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):

Next time, tell us what you have tried, to solve the exercise on your own.
> 4 votes

# Answer
Emptiness problem for DFAs: Given a DFA $D$ determine if $D$ accepts any strings at all, i.e. if $L(D) = ∅$.

The language:

$\qquad E\_{DFA}$ = {$\langle D \rangle$ | $D$ is a DFA and $L(D) = ∅$}

Idea for the Turing Machine for $E\_{DFA}$:

$\qquad$ Check if any of the accept states are reachable from the start state.

Algorithm for $E\_{DFA}$ on input $ D=(Q,Σ,δ,q\_0,q\_A)$:

$\qquad$ 1) If $D$ is not proper encoding of DFA, reject.

$\qquad$ 2) Mark the start state of $D, q\_0$.

$\qquad$ 3) Repeat until no new states are marked:

$\qquad$ $\qquad$ a) Mark any states that can be δ-reached from any marked state.

$\qquad$ 4) If no accept state is marked, accept. Else reject.

Hence, $E\_{DFA}$ is decidable as there exists a valid algorithm for it.
> 4 votes

# Answer
So the question you are asking is basically, is there an algorithm that can decide is a DFA accepts no word. I assume you know something about minimizations of DFAs. And you probably know a method how to get from a DFA to a minimal DFA. Such a method can be carried out by a TM.

Now ask yourself, what is the minimal DFA $Y$ for $\emptyset$. Got it? You are left with finding an algorithm that compares the minimization of $ X $ with $Y$, but thats not too hard.

As a remark, the minimization trick works in general if you want to check if two DFAs accept the same language.
> 3 votes

# Answer
Show that an NFA accepts at least one word if and only if there is a (directed) path from the initial to an accepting state.

Then it's easy to decide the property, e.g. by BFS from the initial state.
> 2 votes

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


# Question
Title: Can the complement of a non-recursive language be RE
I've got a problem where I need to check the *validity* (i.e to say whether it's true or false) of the following statement:

> **Complement of a non-recursive language can NEVER be recognized by any turing machine.**

How I've thought of this is that, if a language $\mathcal{L}$ is non-recursive, there is no turing machine that accepts the language. That is, there's no TM that halts for every string in $\mathcal{L}$. But there could be a TM $M\_1$ that halts for some of the strings in $\mathcal{L}$.

Now suppose, the proposition is $\ false$. So there could be a TM ${M\_2}$ that recognizes the complement of $\mathcal{L}$. So ${M\_2}$ halts and accepts every string that is **NOT** in $\mathcal{L}$ and may or may not halt for strings in $\mathcal{L}$.

Intuitively, It appears that ${M\_1}$ and ${M\_2}$ could be same, which makes my assumption $\ true$. That is the the proposition is $\ false$.

But I'm not certain about the arguments I've made (as the equivalence of $M\_1$ and $M\_2$ is based on intuition). Can someone verify whether I'm correct or correct me otherwise.

# Answer
> 2 votes
From your question I believe there is some confusion of the terms being used here. A recognizable language L is one such that a turing machine exists accepting it, halting on every yes instance. There are also co-recognizable languages, those are languages whose complements are recognizable. Now, if a language happens to be both recognizable and co-recognizable, it is recursive, or decidable (why?). So a language can be non-recursive, but it may still be recognizable or co-recognizable. What can you say about the emptiness problem for turing machines $E\_{TM} = \\{\left \< M \right \>\ :\ \mathcal L(M) = \varnothing\\}$ ?

# Answer
> 1 votes
The given statement can be proven false by the following example:

The emptiness problem for a TM is non-recursive(even non-recognizable) but it's complement is recognizable.

$\qquad E\_{TM}$ = {$\langle M \rangle$ | $M$ is a TM and $L(M) = ∅$}

$\qquad E\_{TM}^c$ = {$\langle M \rangle$ | $M$ is a TM and $L(M) \neq ∅$}

$E\_{TM}$ \- Set of all TM's that accept nothing.

$E\_{TM}$ \- Set of all TM's that accept something.

---
Tags: computability, undecidability
---


# Question
Title: Is the language of all TMs accepting all strings starting with 010 decidable?
I am trying to figure out if this language is decidable: $$ \\{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\\}. $$

My intuition is that it is. Whatever string $w$ starts with 010 it accepts, and if it doesn't it rejects.

# Answer
According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.

$\qquad$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $M\_1$ and $M\_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M\_1 \rangle ,\langle M\_2\rangle \in L$ or $\langle M\_1 \rangle ,\langle M\_2\rangle \notin L$.

Property 2 (Non-trivial) − There exists $M\_1$ and $M\_2$ such that $\langle M\_1 \rangle \notin L$ and $\langle M\_2 \rangle \notin L$.

Now,

$\quad$ 1) For any two TMs, $M\_1$ and $M\_2$ with $L(M\_1) = L(M\_2)$ either both $M\_1$ and $M\_2$ both accept all strings starting with 010 or both don't accept.

$\quad$ 2) There exists TMs that accepts strings starting with 010 and not accepting strings that starts with 010.

Therefore, the property of the language of a TM to start with 010 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$L$ is recognizable as TMs that accepts when given as input strings starting with 010 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).
> 1 votes

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


# Question
Title: A,B decidable: proof that A\B is decidable too
For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.

My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is decidable because A\B=A.

If B is not empty and intersects with A, A\B is just a smaller subset of A and therefore decidable.

I have a feeling that this is either the wrong idea or not formalized enough. I would really appreciate any hints regarding that.

---

EDIT: A subset of a decidable language is NOT always decidable too, this was a misconception.

Thanks in advance

# Answer
> 0 votes
Let $M\_A$ and $M\_B$ be deciders for $A$ and $B$ respectively. You can construct a TM $M$,

$M$ = "On input x,

$\qquad$ 1. Simulate $M\_A$ on x.

$\qquad$ 2. Reject if $M\_A$ rejects. Else simulate $M\_B$ on x.

$\qquad$ 3. Accept if $M\_B$ rejects. Else reject."

$Correctness$:

$\qquad$ $M$ always halts as $M\_A$ and $M\_B$ always halts. $M$ accepts if $M\_A$ accepts and $M\_B$ rejects i.e, $x \in A$ and $x \notin B$. $M$ rejects otherwise.

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


# Question
Title: Decidability of Turing Machine accepting exactly 14 words
Would you say that the following problem is undecidable? $$L\_1 = \\{\langle T \rangle \mid T \text { accepts 14 words}\\}$$ My intuition says that this must be undecidable, and I want to try to reduce it from the emptiness problem for Turing Machines. If we can tell whether or not a TM accepts 14 words, then we should be able to tell if it accepts 0. Since we know EMPT is undecidable, I have been trying to do reduce EMPT to this problem, but I am not sure exactly how to do it.

Can anyone confirm if this is actually a valid starting point, and if it is, any hints on how to formulate a formal reduction?

# Answer
> 1 votes
Your intuition is correct. Probably you can reduce emptiness (or maybe its complement) to this language but it's not the way I'd do it. Instead, think about how you prove that emptiness is undecidable.

You want to know if $M$ halts on input $w$ so you produce a TM that accepts everything if $M$ accepts $w$ and rejects everything if $M$ rejects $w$. A slight modification of that proof will show that your language is undecidable.

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


# Question
Title: How do you correctly write this sentence as a CTL formula?
Sentence: From every reachable state it is possible to reach a state where $p$ is true.

How do you write this sentence as a CTL formula? So far I only dealt with CTL syntax and trees but maybe it will also be asked in a test how you convert a sentence to a CTL formula..

So I've read that $AX$ means *all next*.

Then $AXp$ should mean *in all next states $p$ is true*.

Now I only need the first part of the sentence: *From every reachable state it is possible to reach*

But how would this be expressed and how do you connect it with the $AXp$ I got?

I hope you can help me because on the internet I couldn't find some example like that? : /

# Answer
> 4 votes
You can learn a lot about CTL at Wikipedia page.

The sentence you need to write, expressed more closely in the vocabulary of CTL operators, would be
*Along all paths starting from current state, it always has to hold that there exists at least one path where $p$ eventually is true.*

I think you can take it from there, but comment if you have troubles.

---

**hint:** The operators you will need to use are $F$, $A$, $E$ and $G$.

---
Tags: logic, model-checking, temporal-logic, computation-tree-logic
---


# Question
Title: Why all problems are not in P complexity?
İf Somebody wants to play perfect chess.I consider for finding solution to this problem,possible minimum data compression method which describes with 10 bit maximum possible data is in the range of 2^10.Then with some formula which can take input as next move in the chess,There should be some formula that can change all equations which are in the chess solving algorithm.Therefore ,if we assume in the chess.There should be 10^120 possible games.With approximately 400 bit with if conditions we can calculate all possible game's best strategy and with same thinking way all math problems can be solved with P complexity.Why there are differences with complexity classes?Short answer:İn karnaugh map some variation cannot be described shortly. I understood my mistake vote to delete.

# Answer
Chess is a fixed, finite problem. Because there's no input, you can solve it in a constant amount of time.

Computational complexity considers problems with inputs and looks at how the cost of the computation increases as the input gets longer. For example, you could generalize chess from an $8\times 8$ board to an arbitrary $n\times n$ board and ask how the time taken to compute which side can force checkmate varies as a function of $n$. Certain versions of this problem (it depends on exactly what rules you take) have been proven to require an amount of time that is exponential in $n$, which implies that they can't be solved in only a polynomial amount of time.
> 2 votes

---
Tags: complexity-classes
---


# Question
Title: $L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1
$L\_n = \\{x \in \Sigma^{\*} | \exists w, y, z \in \Sigma^\*, x = ywz, w^R = w, |w| = n \\}$

Informally x is palindrome of length n

where $\Sigma = \\{0,1\\}$

---

I'm having a hard time understanding this could someone please explain.

For $n = 1$

$L\_1 = (0+1)^\*(0+1)^\*$ (Why? What does this mean?)

$L\_1^c = ?$ (What would the compliment mean)

For $n = 2$

$L\_2 = (0+1)^\*(00+11)(0+1)^\*$

$L\_2^c = (10)^\*(\epsilon + 1) + (01)^\*(\epsilon + 0)$

I get how regexes work I just don't understand how $L\_1$ is the regex for palindrome of length one. Not sure what the compliment means. Same for $L\_2$

# Answer
According to the description $w$ is a palindrome of length $n$, and not the complete string $x$. A palindrome is a string that will be the same when reversed. For each length $n$ there are of course finitely many palindromes (as there are only finitely many strings of that length).

The language consists of all palindromes with given length, with arbitrary strings before and after. The palindromes can be listed, and "hard-wired" in the expression.

$L\_1 = (0+1)^\*(0+1)(0+1)^\*$, $L\_2 = (0+1)^\*(00+11)(0+1)^\*$, $L\_3 = (0+1)^\*(000+010+101+111)(0+1)^\*$, ...

The complement is added to see how many strings are *not* of the given form. Any nonempty string will contain a palindrome of length 1 of course. Hence $L\_1^c= \\{\varepsilon\\}$.

Strings that do not contain $00$ or $11$ must have alternating $0$ and $1$'s,hance the $(01)^\*$ etc.
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: Why aren't recognizable languages and co-recognizable languages not reducible to each other?
While learning to prove undecidability of problems, I came across a statement that you can't reduce a recognizable language to a co-recognizable language and vice-versa to prove undecidability. Why is it so?

Eg: Halting problem of TMs can't be reduced to Emptiness problem of TM

$\qquad$ $H\_{TM}$ = {$\langle M,x \rangle$|$M$ is a TM and $M$ halts on input $x$}

$\qquad$ $E\_{TM}$ = {$\langle M \rangle$|$M$ is a TM and $L(M)= \emptyset$}

# Answer
Suppose that $L\_1$ is recognizable, $L\_2$ is co-recognizable, and there is a computable reduction from $L\_1$ from $L\_2$. The computable reduction shows that $L\_1$ is also co-recognizable, and so decidable.

We conclude that if $L\_1$ is recognizable but not decidable, then it cannot be reduced to any co-recognizable language.
> 1 votes

---
Tags: computability
---


title: Prove or disprove L is regular

text:
# Question
Title: Prove or disprove L is regular
There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$

My explanation and work:
I know that we can prove with **pumping lemma** that a language is not regular.
I know that if $L\_1 \subset L\_2$ and $L\_2$ is regular, then $L\_1$ maybe regular or not so in this example, $0^n1^n \subset L$ but we can't say that this language is not regular.
next, I think that $L$ is regular because grammar $A$ can produce anything but after a little try, I found that $A = 0^\*1^\*$ and $110101$ is not a part of language, so it can not be $(1 | 0)^\*$ which is regular.
at this point, I don't know is it regular, or not. $S$ grammar can produce strings which has equal 0 and 1 at the start and end, but maybe $A$ grammar can produce something that make language regular.
Is it possible to help me? can you give me any idea?

### Idea (from comment):

if we say that $L$ is regular, then we get intersection of it and $0^\*1010101^\*$.
for accept a string in this language, there is two state.

1) not equal number of $0$ and $1$ at the start and end of string:
suppose number is form of $0^n1010101^{n+k}$ for $k \gt 0$ (we can prove same for $0$). use $S \to 0S1$ to create $0$ at the start and $1$ end, after some level we get to $0^nS1^n$ but we can't use any $S \to 0S1$ or $S \to 1S0$ anymore so we must use $S \to AA$ and $A = 0^\*1^\*$ and we can't match string. we couldn't construct it if we start with $S \to AA$. so $L$ can't produce this kind of strings.

2) equal number of $0$ and $1$ at the start and end of string:
now our string is form of $0^n1010101^n$ and we can construct it with only $S \to 0S1|1S0$.

so intersection of $L$ and $0^\*1010101^\*$ is $0^n1010101^n$ which is easy to prove that is not regular. so our hypothesis is not correct and $L$ is not regular.

Thanks for idea. Is it true?

# Answer
Your grammar generates the following language: $$ L = \\{ w0^\*1^\*0^\*1^\*\bar{w}^R : w \in \\{0,1\\}^\* \\}, $$ where $\bar{w}$ is obtained from $w$ by switching 0s and 1s. Consider now $L' = L \cap 0^\*1010101^\*$. It is not hard to check that $L$ contains all words of the form $0^n1010101^n$ (take $w = 0^n1$ and $0101 \in 0^\*1^\*0^\*1^\*$). Conversely, if $0^n1010101^m \in L'$ and $n \neq m$, say $n \> m$, then the decomposition $0^n1010101^m = wx\bar{w}^R$, where $x \in 0^\*1^\*0^\*1^\*$, must satisfy that $\bar{w}^R = 1^k$ for some $k \leq m$; but then $x = 0^{n-k}1010101^{m-k} \notin 0^\*1^\*0^\*1^\*$. We conclude that $$ L' := L \cap 0^\*1010101^\* = \\{ 0^n1010101^n : n \geq 0 \\}. $$ It is not hard to check that $L'$ is not regular (for example, the words $0^n$ are pairwise inequivalent), and so $L$ also isn't regular.
> 2 votes

# Answer
You can shorten your reasoning in the "idea from the comments":

Note that for any positive integers $n$ and $m$, $0^n1010101^m$ is not in $L$ if $m \> n$, and is in $L$ if $n = m$. (using your "1" and "2" statements)

Therefore, the strings $0^{n}101010$ for all positive integers $n$ are in distinct equivalence classes as used in the Myhill-Nerode theorem, and therefore $L$ is not regular.
> 1 votes

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


title: How to add decimals to formal grammar?

text:
# Question
Title: How to add decimals to formal grammar?
I have a formal language that describes digit production like

```
<digit> ::= 0|1|2|...|9

```

and I need to intruduce fraction to write decimals like `3.14` and so on

What did I do:

```
<frac> ::= <digit><frac> | .<digit><frac> | <digit>

```

I feel that the `.<digit><frac>` part is wrong, as every time we go this production we can substitute this part and get more than a single dot for the decimal part, which is wrong? What is the proper way to handle this?

# Answer
> 2 votes
To properly produce a formal grammar, you should designate a non-terminal for each different part of a decimal. Here is a sample grammar in Backus–Naur form that also uses square brackets for optional items.

```
            <decimal> ::= [<sign>]<nonnegative_decimal>
               <sign> ::= - | +
<nonnegative_decimal> ::= <nonnegative_integer>[<fractional_part>]
<nonnegative_integer> ::= <positive_integer> | 0
   <positive_integer> ::= <nonzero_digit>[<digits>]
    <fractional_part> ::= .<digits>
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

It can be made more compact as the following.

```
            <decimal> ::= [ - | + ]<nonnegative_decimal>
<nonnegative_decimal> ::= <nonnegative_integer>[.<digits>]
<nonnegative_integer> ::= <nonzero_digit>[<digits>] | 0
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

Please note that the above grammar defines a decimal as a string that starts with a possible sign followed by an integer, possibly followed by a dot and some digits, where only 0,1,2,3,4,5,6,7,8 and 9 are allowed in an integer or digits and where an integer must not start with 0. Many other kinds of decimals are used, too.

# Answer
> 1 votes
A decimal number is either a sequence of digits, or a sequence of digits followed by a decimal point and a second sequence of digits.

Your analysis of your attempt is wrong: it matches things like `.1.2.3.456`.

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


# Question
Title: What's the difference between environment and memory in terms of programming languages?
I've been reading up on programming languages to better my understanding with the textbook *Essentials of Programming Languages (3e) - Friedman & Wand*.

In a chapter regarding the states of languages (i.e. when we account for the effects that a computation may have rather than the immediately evaluated value), I've noticed that the terms **environment** and **memory** are used frequently, but I'm not sure how to grasp the difference.

> According to the text, **"an environment associates a value with each element of a finite set of variables,"** and **"memory is a finite map from locations to a set of values called stored values."**

Does this mean that environments are a part of memory? The part that especially confuses me is when we **"extend the environment."**

To give a short example, if I had a procedure such that

```
let f = proc (x) (x + 1) in
  f (1)

```

then the text states that we "extend our environment" so variable `f` points to a location (say, `l1`) and argument `x` points to `l2`.

`l1` in turn points to the procedure tuple `(x, (x + 1), empty_env)`, and finally `l2` points to the actual argument `1`.

We update the location contents according to the procedure, which means we update `l2` with `2`, and the program finally returns `2`.

Thank you.

# Answer
> 5 votes
# Functions

The terms "*associate*" and "*map*" together with "finite" indicate that both definitions refer to *finite mathematical functions*.

A (mathematical) **function** is a *relation* that *associates* each *element* of a *set*, the **domain** of the *function*, to a *single element* of another *set* (possibly the same *set*), the **codomain** of the *function* \[Wikipedia\].

Another way to put this, for **finite functions** are: a *finite set* of *ordered pairs*.

**Map** is usually *defined* as a synonym to *function*.

Thus the definitions could be rewritten as follows:

---

## Environment

An **environment** is a *finite function* that *associates* each *element* in the *finite set of variables* (**domain**), to a *single element* in the *finite set of values* (**codomain**). The **range** would be the *set of all possible values* (possibly *infinite*).

## Memory

A **memory** is a *finite function* that *associates* each *element* in the *finite set of locations* (**domain**), to a *single element* in the *finite set of stored values* (**codomain**). The **range** would be the *set of all possible values* (possibly *infinite*).

---

# Sets

> Does this mean that environments are a part of memory?

Since this is about *sets*, if you by *part* mean **subset**, then the answer would be no.

However, the *codomains* are definitely related, if a *variable* is *associated* with a *value* in the *environment*, a *location* must also be *associated* to a *stored value* in the *memory*, that corresponds to the *variable value*.

---

# Extending the Environment

> The part that especially confuses me is when we "extend the environment."

It seems the aim of the text is to build an *interpreter*. You start out with no *variables declared* (including procedures), i.e., an **empty environment** and then you *interpret/parse/analyze* the *code* to make these *associations*, i.e., **extending the environment**.

---

# In Practice

It might be helpful to think of the **memory** as the *values stored* somewhere in the *physical memory* and the **environment** as the *values* that the *interpreted process* currently knows about.

---

---
Tags: programming-languages
---


# Question
Title: Leftist Heap doesn't support DecreaseKey operation?
I'm studying data structure. When I read the chapter of heap, something really confused me. DecreaseKey's time complexity of the binary heap is O(lgn). However, I found somewhere on internet claimed that Leftist Heap doesn't support DecreaseKey operation. But I wonder why? Can't we simply treat leftist heap as binary heap to perform DecreaseKey?

# Answer
Indeed, the right solution of DecreaseKey for leftist trees seems to be hidden on the internet. (My book by Weiss has a solution, but in the chapter on amortized analysis, and I do not quickly understand the argumentation.)

First, we *cannot* treat DecreaseKey as in binary heaps. There one repeatedly swaps the node with its parent until a parent is found which is actually smaller than the new value. This operation works in leftist trees, but may take linear time. In leftist trees there is no bound on the length of paths to the left, and indeed such a tree can be just one long linear leftmost tree.

The solution is to cut the node $q$ that is decreased (with its subtree), to change the value of $q$ to the new value, and merge it with the remainder $T$ of the original tree. Before we can do that we should bring $T$ back into leftist form, and restore the null-path-length values that are changed by cutting the subtree. As we cut $q$ from the tree, only the nodes from the parent $p$ upwards to the root have to be checked. (Unfortunately this may be a linear number of nodes, as we have seen.)

The solution is that the new null-path-length values we asign upwards in the tree are always *one larger than the value at the previous level*. This process stops when we are in a left child which has new value $\ell$ and its right sibling has value $r$ with $\ell \ge r$. Then the parent already had value $r+1 = \min\\{\ell,r\\}+1$ and we are done.

We know (from the basic property that makes leftist trees efficient) that a null-path-length value of $\ell$ means that there are $2^\ell-1$ nodes in that subtree, making the operation logarithmic.

The fact that the values upwards in the new tree are always one larger is essential here, that was not (necessarily) true along the path in the original tree.
> 2 votes

---
Tags: data-structures
---


title: Searching in a Binary Search Tree

text:
# Question
Title: Searching in a Binary Search Tree
I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.

For example, let S = \[17, -10, 7, 19, 21, 23, -13, 31, 59\].

Binary Search Tree for S, with S as root:

How many comparisons is needed to search this tree for the presence of each of the elements in I = {-13, 31}?

Search for -13:

Since -13 is less than 17: Go to left Child Is -13 \< 17?

Comparisons = 1

Since -13 is less than -10: Go to left Child

Comparisons = 2

Item (13) found with two comparisons.

Search for 31:

Since 31 is greater than 17: Go to right Child

Comparisons = 1

Since 31 is greater than 21: Go to right Child

Comparisons = 2

Sincer 31 is greater than 21: Go to right Child

Comparisons = 3

Item (31) found with three comparisons.

Total number of comparisons to find the presence of each item in I: 5.

Is my understanding correct?

# Answer
Yes... You can also practice with an implementation of your own. I have created such an implementation and a good test is to compile this with different optimization levels in gcc:

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    int node_id;
    int data;
    char *name;
    struct node *left;
    struct node *right;
} node;

node *newNode(int data, char *name, int node_id) {
    node *new_node = malloc(sizeof(node));
    new_node->data = data;
    new_node->name = name;
    new_node->node_id = node_id;
    new_node->right = new_node->left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id, char *name) {
    if (root == NULL)
        return newNode(data, name, node_id);
    else {
        node *cur;
        if (node_id < root->node_id) {
            cur = insert_node(root->left, data, node_id, name);
            root->left = cur;
        } else if (node_id > root->node_id) {
            cur = insert_node(root->right, data, node_id, name);
            root->right = cur;
        }
    }
    return root;
}

node *find_node_data(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else if (root->node_id > node_id)
        return find_node_data(root->left, node_id);
    else
        return find_node_data(root->right, node_id);
}

void print(node *np) {
    if (np) {
        print(np->left);
        printf("(%d, %d, %s)", np->node_id, np->data, np->name);
        print(np->right);
    }
}

int main() {
    int T = 1000; //test case 1000 nodes
    int data, r2, r;
    int node_id = 0;
    //printf("Input number of nodes:");
    //scanf("%d", &T);
    node *root = NULL;
    srand(time(NULL));
    while (T-- > 0) {

        //scanf("%d %d", &data, &node_id);
        r = (2 + T) * rand() % 100; //node id
        r2 = (2 + T) * (rand() % 100); // data
        printf("Input data. %d:\n", r2);
        printf("node id. %d:\n", r);
        root = insert_node(root, r2, r, "foobar");
    }
    print(root);
    // printf("\n");
    // printf("Find data at node:");
    // scanf("%d", &T);
    print(find_node_data(NULL, node_id));
    T = r;
    printf("node data %d %s", find_node_data(root, r)->data, find_node_data(root, r)->name);
    root = NULL;
    // find_node_data(root, T)->data;
    print(root);
    return 0;
}

```
> 1 votes

---
Tags: binary-trees, binary-search-trees, binary-search
---


# Question
Title: Why is reflexivity enough in this HoTT formulation of quotient types?
In this formulation of quotient types in cubical type theory I was able to implement an eliminator and use that to implement basically curried function application. However, in all this, the only requirement on the factoring relation is that it is reflexive.

I find this surprising. I would have expected transitivity and symmetry to also be needed somewhere along the way. Is there an intuitive explanation for why reflexivity is enough?

# Answer
> 4 votes
Your `Quot` construction is a set-truncated quotient by an *arbitrary* relation $R$ since you never use the reflexivity assumption in the construction. That is, you don't even need the reflexivity of $R$ to perform the quotient and derive its basic properties.

As the HoTT book explains in Section 6.10, it is perfectly possible to make set-truncated quotients by an arbitrary relation because reflexivity, transitivity and symmetry are taken care of by the paths themselves (because there are identity paths, paths can be reversed, and composed). That is, the quotient $A/R$ is equivalent to the quotient $A/\overline{R}$ where $\overline{R}$ is the equivalence relation generated by $R$.

There is one property that you will *not* get, namely that (using the notations from your file) $(x : A) \to (y : A) \to \mathsf{point}\\;x = \mathsf{point}\\;y \to R\\;x\\;y$. For that you need the fact that $R$ is a proposition and an equivalence relation.

---
Tags: homotopy-type-theory
---


# Question
Title: What is the minimum pumping length of the union of two languages?
If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them?
Does it differ if either of them contains just one string like 001?

# Answer
> 2 votes
Consider the following two languages: $$ L\_0 = 1(0+1)^\* + 0^{n\_0}, \\ L\_1 = 0(0+1)^\* + 1^{n\_1}. $$ The minimum pumping length of $L\_0$ is $n\_0 + 1$, and that of $L\_1$ is $n\_1 + 1$. Yet $L\_0 \cup L\_1 = (0+1)^+$ has a minimum pumping length of 1.

What does hold is that the pumping length of $L\_0 \cup L\_1$ is at most the maximum of the pumping lengths of $L\_0,L\_1$. In fact, it can be any number between 1 and that maximum. Indeed, suppose that $1 \leq a,b \leq c$, and consider the languages $$ \begin{align\*} L\_0 &= 1(0+1)^\* + 0^{a-1}, \\ L\_1 &= 0(0+1)^\* + 1^{c-1} + 2^{b-1}. \end{align\*} $$ The maximum pumping length of $L\_0$ is $a$, that of $L\_1$ is $c$, and that of $L\_0 \cup L\_1 = (0+1)^+ + 2^{b-1}$ is $b$.

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


# Question
Title: Chinese postman problem, but criteria = visit each vetex at least once
Chinese postman problem, but where the postman have to visit each vetex at least once.

Is there a name for this problem?

What is the ideal algorithm to solve this problem?

# Answer
> 1 votes
Let $G$ be an edge-weighted graph. Create a new graph $G'$ in which the weight of the edge $(x,y)$ is the cost of the shortest path between $x$ and $y$ in $G$. The problem you are interested in is the traveling salesman problem (TSP) on $G'$.

---
Tags: algorithms, graphs
---


title: Minimum cost node cut

text:
# Question
Title: Minimum cost node cut
I am interested in solving the following problem:

> Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph.

Is there any known algorithm solving this problem?

---

Here is an attempt at a solution (in python), using network flow:

```
deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1

st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))

nodes = ['s','t']
edges = []
for i in r:
    nIn = (str(i)+'in')
    nOut = (str(i)+'out')
    nodes.extend([nIn,nOut])
    edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
                  (nOut,'t',{'capacity':math.inf,'weight':0})])

for edge in Complement_G.edges:
    print(edge[0],edge[1])
    edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
                  ((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])

print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)

mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)

```

# Answer
Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are **equal**, then it is equivalent to the vertex-connectivity problem.

The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough.

The simplest approach is the following. Consider all pairs $s$, $t$ of nodes in the graph. For each such pair, we are going to compute the minimum cost, call it $c\_{st}$, of separating that pair, that is, the weight of a minimum vertex-weighted $s$-$t$ cut. Then the set you look for will be the set achieving the minimum cost $c\_{st}$ over all pairs $s$, $t$.

For a given pair $s$, $t$, the minimum weight cut can be computed with network flow by first replacing every edge $\\{u,v\\}$ with a directed pair of edges $(u,v)$, $(v,u)$. Then you need to expand your graph by splitting every vertex $v$ into a pair $(v^-, v^+)$. An arc $(u,v)$ is replaced by an arc $(u^+, v^-)$ and an arc $(v,u)$ is replaced by an arc $(v^+, u^-)$. Moreover you add arcs $(v^-, v^+)$ with capacity equal to the weight of $v$; all other arcs have unbound capacity ($\infty$). This complication is necessary to properly model the vertex removal costs. After creating this new instance, you just call the network flow subroutine with source $s^+$ and sink $t^-$. The amount of flow shipped from the source in the solution will tell you $c\_{st}$. (To find the **set** of vertices disconnecting $s$ from $t$, look for all vertices $v$ such that $v^-$ is reachable from $s^+$ in the residual flow network while $v^+$ is not.)

All in all, you need to call the network flow subroutine $n(n-1)/2 = O(n^2)$ times. In fact, there is also a less intuitive but somewhat faster algorithm that allows you to call the network flow subroutine $m$ times instead of $n^2$, where $m$ is the number of edges. This could be much better if the graph if sparse. See the reference below for more details about this faster version.

You can also substantially reduce the time complexity if you know for sure some vertex $s$ that is **not** going to be one of the nodes that will be removed from the graph. Then you can just try all other nodes $t$ and follow the same strategy as above, only this time you will need to invoke $n-1$ times the network flow subroutine, because $s$ is fixed.

Reference: A. Schrijver, Combinatorial Optimization, Section 15.2. Springer, 2004.
> 2 votes

---
Tags: graphs, python, ford-fulkerson
---


title: Prove hash family is 3-wise independent

text:
# Question
Title: Prove hash family is 3-wise independent
Let $q$ be a prime number and let $\mathbb{Z}\_q = \left\\{1,\dots,q-1\right\\}$; I need to prove that the family $\mathcal{H} = \left\\{h\_s \colon \mathbb{Z}\_q \rightarrow \mathbb{Z}\_q\right\\}\_{s \in \mathbb{Z}\_q^3}$ is 3-wise independent, where $h\_s$ is defined as:

$$h\_s(x):=h\_{s\_0,s\_1,s\_2}(x):=s\_0 + s\_1 x + s\_2 x^2 \bmod q$$

How could I do it? My intuition would be proving that it is 1-wise independent and use the property $$x\_1,\dots,x\_t \in \mathcal{X}, \quad y\_1,\dots,y\_t \in \mathcal{Y}, \quad \Pr\[h\_s(x\_1)=y\_1 \wedge \dots\wedge h\_s(x\_t)=y\_t \mid s \leftarrow \_\\$ \mathcal{S}\]=\frac{1}{|\mathcal{Y}|^t},$$ but I'm not sure how to do that.

# Answer
> 0 votes
Let's assume that $\mathbb{Z}\_q$ is the field of size $q$. In order for your family to be 3-wise independent, we need the following condition to hold: for every $x\_1,x\_2,x\_3,y\_1,y\_2,y\_3 \in \mathbb{Z}\_q$ where the $x\_i$ are all different, $$ \Pr\_s\[h\_s(x\_1) = y\_1 \land h\_s(x\_2) = y\_2 \land h\_s(x\_3) = y\_3\] = \frac{1}{q^3}. $$ Since your family consists of $q^3$ functions, this is the same as the following property:

> If $x\_1,x\_2,x\_3 \in \mathbb{Z}\_q$ are all different, then for every $y\_1,y\_2,y\_3 \in \mathbb{Z}\_q$ there exist unique $s\_0,s\_1,s\_2 \in \mathbb{Z}\_q$ such that $$ s\_0 + s\_1 x\_i + s\_2 x\_i^2 = y\_i, \quad i \in \\{1,2,3\\}. $$

This is a property that you can prove using linear algebra.

---
Tags: cryptography, hashing
---


# Question
Title: BST - Sufficient condition for connecting a node to a parent
Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.

I want to prove that if I insert a node X into the tree and node X is greater than node Y and less than the successor of node Y then X will be added as the right child of Y.

Intuitively, this makes sense to me but my question is how do we prove this formally?

# Answer
> 1 votes
Due to the lack of definitions in the question, let us pick up a couple of definitions that are needed for a formal proof.

> A binary rooted tree is a BST if its nodes are visited in its natural order by the inorder traversal. Inserting a new node into a BST means adding a new edge so that the new node becomes the child of some old node and the tree remains a BST.

---

Let us prove a useful lemma.
(**Uniqueness of insertion into BST**) Let $T$ be a BST. Let node $X$ be a new node that is not equal to any node in $T$. Then there exists a unique way to insert $X$ into $T$ so that $T$ remains a BST with the same root, where the insertion must add one edge to $T$ (without modifying the existing edges).

Proof by mathematical induction on $n$, the number of vertices in $T$.

* The base case when $n=1$. If the new node is less than the root node, it has to inserted as the left child of the root node; otherwise, it has to be inserted as the right child of the root node.
* Assume the lemma is true for BST whose number of vertices is smaller than $n$. Suppose $T$ is a BST of $n$ vertices with node $R$ as its root node. Suppose $X$ is a new node that is not equal to any node of $T$. There are two cases.
    + $X$ is less than $R$. If $R$ has no left child, then $X$ has to be inserted as the left child of $R$. Otherwise, $R$'s left subtree is a BST (because of the recursive nature of the inorder traversal). $T$ has to be inserted into $R$'s left subtree. By induction hypothesis, there exists a unique way to insert $X$ into $R$'s left subtree.
    + $X$ is greater than $R$. Just switch every "left" to "right" in the above case.

Proof is done. As you have indicated, this is intuitively so obvious!

---

Now let us prove a proposition that is slightly more general than what you want to prove.
(**Right child insertion**) Let $T$ be a BST with node $Y$ that does not have a right child. Let node $X$ be a new node larger than $Y$ such that any node that is larger than $Y$, if exists, must be larger than $X$. Then node $X$, if inserted, will be inserted as the right child of $Y$.

Proof. Let $T'$ be the binary tree obtained from $T$ when $X$ is added as the right child of $Y$. Compare the inorder traversal on $T$ and that on $T'$. By the definition of inorder traversal, the difference between them can happen only when each traverses the subtree rooted at $Y$.

Both traversals will visit the same left subtree of $Y$ first. Then both will visit $Y$. When it is time to visit the right subtree of $Y$, the former traversal has nothing to do since $Y$ has no right child in $T$ while the latter traversal will visit one more node, $X$ since $Y$ has $X$ as its right child in $T'$.

Since the nodes in $T$ is visited in its natural order by the former traversal, the nodes in $T'$ is visited in its natural order by the latter traversal as $X$ is the very next node that is larger than $Y$. By definition, $T'$ is a BST. According to the above uniqueness lemma, $X$ must be inserted as the right child of $Y$. Q.E.D.

# Answer
> 0 votes
Maybe this is not the "proof" you're looking for, but here's an attempt to convince anyone that $X$ will be inserted in the binary-search tree (BST) as $Y$'s right child.

The "proof" relies on the binary-search tree property and on the definition and correctness of the "insertion" and "successor" functions of a BST.

You start with the definition of a *successor* of a node $y$ in a BST:

> 1. If a node $y$ has a right subtree, then the successor of $y$, call it $z$, is the minimum node of that right subtree
> 2. Otherwise, it is the first ancestor of $y$, lets call it $z$, such that $y$ falls in the left subtree of $z$.
> 3. If $z$ is not found in the previous two points, then $z$ does not exist, which implies that $y$ is the greatest element in the BST.

However, we also need to look at the pseudocode of the insertion function.

```
function insertion(T, x):
    // T is the binary-search tree
    // x is the element which needs to inserted in T
    if is_empty(T):
        T.root = x
    else:
        c = T.root  // c is the current node.
        p = c.parent  // p is the parent of c

        while is_not_null(c):
            p = c
            if x < c:
                c = c.left
            else:
                c = c.right
        if x < p:
            p.left = x
        else:
            p.right = x
        x.parent = p

```

Since, in your case, we know that $T$ is not empty, then the `else` block will be always executed in any run of the `insertion` algorithm. In the `while` loop, we go down the tree, until we find a node that is null (and `c` represents this `null` node). However, note that we keep track of the parent of that null node `c`, i.e. `p`. We know that `p` is going to be the parent of `x`, but we still do not know if `x` needs to be the left or right child of `p`, given that `x` could either be respectively smaller or greater than `p`. Once that is determined, using the `if`-`else` block after the while loop, we can also set the parent of `x` to be `p`.

I will not prove that this insertion algorithm is correct, that is, it maintains the BST property. We assume it is correct. Here's the "proof" then.

> We know that $Y$ does not have a right child, but it has a successor. Therefore, the successor must be the first ancestor of $Y$, call it $Z$, such that $Y$ falls in the *left* subtree of $Z$. We know that $Z$ exists (by assumption). If you insert $X$ in the binary-search tree $T$, such that $Y \< X \< Z$, then $X$ will be the next successor of $Y$ (by definition).
>
> Given that $Y \< X \< Z$, at some point during the `insertion` algorithm, the condition `x < c` is false (because $X \> Y$), where `c` is $Y$ and `x` is $X$. This must be true because there is no node between $Y$ and $X$ in the tree. Hence, in that case, $X$ will consequently be inserted in the tree as $Y$'s right child.

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


# Question
Title: context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Let $L\_{n} = \\{x \in \Sigma^\* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \\}$

Generate a cfg of $L\_n$

For n = 1, 2, 3

---

Informally, x is in $L\_n$ means some palindrome of at least length n is a substring of x that occurs exactly at the midpoint of x.

for $n = 1$

$S \to 0S0 | 1S1 | 0S1 | 1S0|0 | 1 | 00 | 11$

for $n = 2$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | \epsilon$

for $n = 3$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | 00 | 11 | \epsilon$

would this be right?

Say I changed it to $|y| \> |z|$ or $|y| \< |z|$ how would this differ?

# Answer
When $n=1$, the language $L\_1$ consists of all words of the form $ywz$, where $|y|=|z|$ and $w$ is a non-empty palindrome. We can generate all non-empty palindromes as follows: $$ P \to 0P0 \mid 1P1 \mid 0 \mid 1 \mid 00 \mid 11 $$ Given that, we can generate $L\_1$ by capturing also the outer part: $$ S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid P $$ For larger $n$, all we need to change is the "base cases" for $P$.

Further observation reveals that we can actually assume that $|w| \leq 2$ (for $n = 1$), and so we can use alternatively the following productions for $P$: $$ P \to 0 \mid 1 \mid 00 \mid 11 $$ This allows us to eliminate $P$ from the grammar, reaching the following grammar: $$ S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid 0 \mid 1 \mid 00 \mid 11 $$ These steps can also be extended to larger $n$.
> 1 votes

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


title: Primitive recursive plus Ackermann

text:
# Question
Title: Primitive recursive plus Ackermann
Let us consider the class $\cal F$ of functions that contains

* all constant functions
* all projections
* the successor function
* the Ackermann function

as basic functions, and that is closed under composition and primitive recursion.

(If we remove the line with the Ackermann function from this definition, then this is the standard definition of the class of primitive recursive functions.)

> **My question:** What function class $\cal F$ do we get by adding the Ackermann function as basic function? Do we get all $\mu$-recursive functions, or do we get some strange sub-class?

# Answer
A very nice question!

You just ventured into a large body of knowledge and research in computational theory around the concept of relative primitive recursiveness and hierarchy of total recursive functions such as fast growing hierarchy, which are full of interesting and mind-boggling facts.

> What function class $\cal F$ do we get by adding the Ackermann function as basic function?

Well, that is one of its own kind.

> Do we get all $\mu$-recursive functions?

No. What we get are far far from all $\mu$-recursive functions since all functions we get are still total recursive functions as primitive recursion preserves totality. Recall that $\mu$-recursive functions means partially recursive functions or, what is equivalent, all functions that can be computed by Turing machines.

You might ask, then, do we get all total recursive functions?

The answer is still no. What we get are far from all total recursive functions. For example, a "Ackermann modification of Ackermann function" is not included. Here is a version of that "doubly Ackermann" function.

Let us start from the usual two-argument Ackermann–Péter function. $$A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m \> 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m \> 0 \mbox{ and } n \> 0. \end{cases}$$ Let $f(n)=A(n,n)$ be the Ackermann–Péter function of a single-argument. Now let us define $$D(m, n) = \begin{cases} f(n) & \mbox{if } m = 0 \\ D(m-1,1) & \mbox{if } m \> 0 \mbox{ and } n = 0 \\ D(m-1, D(m, n-1)) & \mbox{if } m \> 0 \mbox{ and } n \> 0. \end{cases}$$

Then $D(m,n)$ is a doubly Ackermann function, which cannot be obtained from composition and primitive recursion of Ackermann functions and all primitive recursive functions. This is not surprising, since a single Ackermann modification accelerates the growth of a strictly increasing function faster than arbitrarily finitely many compositions and primitive recursions.

You may continue to ask, what if we add that doubly Ackermann function? Then we are missing the "triply Ackermann functions". If you keep asking, then you will be building a growing hierarchy by Ackermann modification. Even if you have asked $\omega$ times this way, where $\omega$ is the first infinite ordinal, the growth rate of any function thus obtained is still dwarfed by most of functions in the fast growing hierarchy.

> or do we get some strange sub-class?

You may call it some strange sub-class as you like. However, as you might have expected, it is not unusual at all in the field of computation theory. Here is an excerpt from paper *The Ackermann functions are not optimal, but by how much?* by H. Simmons, slighted edited.

> 5.1 DEFINITION. For each set $\Theta$ of functions, let $PR(\Theta)$ be the clone of those functions that can be obtained from members of $\Theta$ by primitive recursion. $PR(\Theta)$ is also called a primitive recursive degree. The primitive recursive degrees measure the complexity of functions up to primitive recursive equivalence.

The "strange sub-class" of yours is just $PR(\alpha)$, where $\alpha$ is the set of primitive recursive functions and the particular versions of Ackermann function you have in mind. In that paper, "by taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees."

Hopefully, I have shown you a glimpse of the fascinating theory around recursiveness and growth of total recursive functions. You may want to read some of the following articles as well as raise more interesting questions like this one.

Mind blown: the fast growing hierarchy for laymen — aka enormous numbers
Ackermann function
Higher-Order Recursion, How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking
> 6 votes

# Answer
The limitation of "primitive recursive" functions is that for all loops, the iteration count must be calculated before the loop starts iterating, and must be calculated within the limitations of primitive recursive functions. You can't run loops that run for arbitrary long (but finite) time.

The Ackermann function on the other hand grows faster than can be calculated using any primitive recursive function. With your addition, you *still* can't run loops that run for arbitrary long (but finite) time, but you can run loops whose iteration count has to be calculated before the loop starts iterating, where the calculation can involve use of the Ackermann function.

So many functions that require *huge* iteration counts, so huge that they cannot be calculated with primitive recursive functions but can be calculated involving the Ackermann function, can now be computed.

I have no idea how difficult it is to define an "Ackermann-squared" function that grows too fast to be calculated using this model.
> 0 votes

---
Tags: computability, computation-models, primitive-recursion
---


title: Meta Programming Operators

text:
# Question
Title: Meta Programming Operators
I have a basic understanding how operators work (bitwise, logical, unary, ternary, etc.), but I am confused how you define what the operator does so the machine knows how to treat the operator when you use it in your code base. Are operators predefined by the compiler and is there a way for me to access the source code of an operator's definition?

# Answer
> 2 votes
The language specification defines what the operator does, and the compiler produces the appropriate machine instructions to implement this. In general, there's no reason to assume that the operator is implemented as a sequence of statements in the language that's being compiled (e.g., operators in C aren't first translated into longer expressions in C).

In many cases, (e.g., addition and multiplication), the appropriate machine instructions will be just one instruction.

---
Tags: programming-languages
---


# Question
Title: Alternative formulation of complexity class $BPP$
In Aurora and Barak, they give the following alternative definition of $BPP$:

What is the meaning of the subscript to $Pr$? Is that $Pr\_{r \in\_R \\{0,1\\}^{p(|x|)}}$? My guess is this is supposed to represent $poly(|x|)$ many coin toss results, but what is $R$? And why is this a subscript to $Pr$?

# Answer
> 0 votes
The subscript to $\Pr$ denotes which random variable the probability is over. In this case the probability is over $r$, which is samples uniformly at random (this is what is conveyed by $\in\_R$) from $\\{0,1\\}^{p(n)}$. You can think of $r$ as representing a sequence of $p(n)$ many random coin tosses.

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


# Question
Title: Turing machine to output enumeration of a language
I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$.

So for example it should output the following to the first tape: `e`,#,0,1,#,0,0,1,1,#,0,0,0,1,1,1 etc.

Here `e` means empty, i.e., to leave that index blank.

I can't figure out how to display this as a Turing machine with states and transitions.

# Answer
Here is one way to approach this problem. Program a machine that acts as follows:

* Initialize the tape with $\\#01$ (or $\epsilon\\#01$).
* At each step, write $\\#$, then go back to the previous $\\#$ and copy the string written there, say $0^n1^n$.
* Change the first $1$ to a $0$, add two $1$s at the end, and go to the next step.
> 1 votes

# Answer
Honestly, this is going to be painful. The Turing machine probably has an uncomfortably large number of states.

The best way to proceed would be to write out an algorithm in pseudocode. Then iteratively rewrite it so that the steps of the pseudocode look more and more like steps of a Turing machine. Then implement it formally as a Turing machine.

Actually, I tell a lie. The best way to proceed would be to not produce this Turing machine at all. If it's an exercise that you have been set, it's a terrible exercise because it's impossible to do without making mistakes and impossible to mark. If it's an exercise that you've decided to do yourself, I suggest doing something else, because this one won't teach you much at all. Maybe design a Turing machine for the decision version of this problem.
> 0 votes

---
Tags: turing-machines, enumeration
---


# Question
Title: How to check if a given point is inside a polygon with holes?
How to check if a given point lies inside or outside a polygon with holes?

Does the below algorithm works for polygon with holes?

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

# Answer
Yes, basically.

That algorithm is called ray casting algorithm, also known as the crossing number algorithm or the even–odd rule algorithm.

Why is it correct? "The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two 'border crossings' the moving point goes outside. This observation may be mathematically proved using the Jordan curve theorem." Note this reasoning works in all basic situations, whether the polygon is convex or not and whether the polygon has holes or not.

However, you should be aware of the degenerate cases as well as the case of a hole inside a hole. For an example of degenerate case, consider a degenerated polygon that are two triangles intersecting only on their only common vertex. Then the algorithm may fail when the ray goes through that common vertex. For the case of a hole inside a hole, you have to define the area inside the smaller area is inside the polygon so as to not invalidate the algorithm.

It is actually not easy to make a rigorous statement mathematically about the general situations when the ray casting algorithm works. For this particular question, let me just say the ray casting algorithm will work for a polygon with separate polygon holes inside it where all line segments of the outer polygon and inner polygons do not intersect each other.
> 2 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Calculate the average length of the linked lists in a hash table
I am learning hash tables, and I would like to know how to determine the average length of the linked lists.

For example: A hash table holds about 10,000 employee records. Each record is indexed by the 2-character initials of the employee name, transformed into integers using the mapping: A=01, B=02, C=03, and Z=26. On average no more than 8 comparisons is made every time a search is requested.

How would you determine determine the actual average length of the linked lists, in the hash table, that is pointed to by the hash value slots?

# Answer
since the hash is constructed such that the input element has an equal chance to be in any of the bins of the hash table, then the average number will be (number of imputed elements) / (size of the hash table)
> -1 votes

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


# Question
Title: Lempel-Zilv-Welch Algorithm Decoding Question
Hello i am studying about LZW algorithm by watching this video: https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s

I couldnt fully understand decoding process. At current 258,how does 116 come at add to dictionary part ? At current 256,how does 101 come at add to dictionary part ?

# Answer
> 0 votes
Let us look at the very first line. There is a `104` at the end of the line. Where does that `104` come from? It is the first number of the number(s) that are represented by `104` in the `next` column. Since 104 is in the 0-255 range, `104` just represents itself.

**The same procedure** happens on the line at the end of which you see a `106`. Where does that `106` come from? That `106` is the first number of the number(s) that are represented by `256` in the `next` column. How? Since 256 is outside of 0-255 range, we have to consult the dictionary we have built. As given by the last column of the first line, `256` represents for two numbers, `116 104`, of which `106` is the first one.

I will let you figure out why the above procedure is correct, where `101` on the last line come from and why the numbers in the `output` column are correct.

By the way, it should be helpful if you can also take a look at the encoding procedure at the nearby lines when you try to understand the decoding procedure.

---
Tags: algorithms, lempel-ziv
---


# Question
Title: Do data points mean Eigenfaces in higher dimensional space?
I saw the following animation at making sense of PCA , which shows blue data points.

I am reading a paper on Eigenfaces which says that:

> "a typical image of size 256 by 256 becomes a vector of dimension 65536 or equivalently a point in 65536 dimensional space"

The paper is available at the following link: Eigenfaces for Recognition

My question is that in the context of Eigenfaces is each blue point an image?

Somebody please guide me.

Zulfi.

# Answer
> 1 votes
Each blue data point in the animated picture stands for an image of a face whose dimension is much higher in the context of *Eigenfaces for Recognition*. They are the original data points. It does NOT mean Eigenfaces.

When the long swinging black solid rod becomes still under the "viscous friction" exerted by the red lines, its direction is the most significant eigenface in that context, which is defined as an eigenvector of the biggest eigenvalue of the covariance matrix of the face images. The projection of the blue points onto that long black rod viewed as vectors starting from the center of the blue points is the first principal component.

---
Tags: machine-learning
---


# Question
Title: Finding loop invariant of Lowest common multiple function
So I have the following function:

```
def lcm(a,b):
    x = a
    y = b
    while x != y:
        if x < y:
            x += a
        else:
           y += b
    return x

```

I'm not sure how I will go about finding the loop invariant of this question. I know I have to find some sort of relationship between $x$ and $y$ but nothing seems to hold or is helpful in actually proving correctness.

# Answer
Well, a possible loop invariant is "$x$ is a multiple of $a$ and $y$ is a multiple of $b$".

Then this *almost* proves partial correctness, because we know that after the loop terminates $\neg(x \neq y) \to x = y$, thus $x$ must be a multiple of both $a$ and $b$.

What this loop invariant *doesn't* show is that $x$ is the smallest possible such number.

To solve this, we must complicate our loop invariant:

1. If $x \geq y$, $x$ is the smallest multiple of $a$ that is bigger than or equal to $y$.
2. If $y \geq x$, $y$ is the smallest multiple of $b$ that is bigger than or equal to $x$.

Now it's up to you to prove that this invariant is correct.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, correctness-proof
---


# Question
Title: Algorithm to find non-overlapping intervals that minimize standard deviation
I am looking for the name of an algorithm category, or even specific algorithms, that solve the following problem.

I have noisy data. For simplicity, let this data be represented by numbers. I have the full data set in RAM. In this noisy data, I want to find signal. Signal is an interval of contiguous numbers that are close-enough to each other. In other words, their standard deviation is below some threshold. At the same time, I don't trust the signal if it is too short-lived, so it must be at least *n* contiguous numbers long.

In other words, I want to find non-overlapping intervals of values, where each interval has at least *n* values, and those values have a standard deviation of at most *sd*.

The intervals do not need to be contiguous. (Signal is intermittent in all the noise.)

I want to minimize *sd* in these intervals, so given a choice of one interval with a higher *sd* or two intervals with a lower *sd*, I prefer the latter. (As long as both intervals have at least *n* values, as I said earlier.)

For example, suppose I configure a minimum interval size of 5, and I have the following list:

> 7, 7, 8, 7, 7, 4, 5, 5, 5, 4, 6, 6

The *sd* for this whole interval is 1.31. If we split it into

> 7, 7, 8, 7, 7

then drop the middle 4, and continue to the next interval,

> 5, 5, 5, 4, 6

then drop the final 6, we get *sd* of 0.45 and 0.71, which intuitively seems optimal to me.

Had we kept the middle “4” in the second interval, that interval’s *sd* would have been 0.82. Had we kept the final “6”, that interval’s *sd* would have been 0.76. We could have decreased *sd* even further by removing more elements, except intervals in this example must have at least 5 elements.

(Note, I came up with this particular split intuitively, so it may not be the optimal split.)

What algorithm(s) can solve this problem?

# Answer
> 1 votes
Let the $n$ numbers be $x\[1..n\]$, and the minimum interval size $k$.

## Formulating an objective function

There's a conflict here between two goals: Reporting more intervals will often mean reporting *worse* intervals. We need an unambiguous way to decide which set of intervals is "best". A good way to resolve this is by assigning some score value to any interval that includes two terms: a positive term (perhaps dependent on the length), as well as a negative term for the "quality" (here, standard deviation). The goal is now to choose a set of nonoverlapping intervals that maximises the sum of scores. For example, we could say that the score $s(i, j)$ of the interval $i..j$ is $10 + j - i - 7\*StdDev(x\[i..j\])$.

## A quadratic-time dynamic programming algorithm

The following dynamic programming algorithm takes $O(n^2)$ time and $O(n)$ space to find a solution having optimal score (there may in general be more than one such), and works for any scoring function $s$ that depends only on the beginning and end positions of the given interval (so you may certainly tweak my example function until you get results that look good). It seems likely to me that a faster (linear or at least log-linear) algorithm exists for simple scoring functions, but in any case the following is flexible and will certainly handle $n$ up to 10000 in well under a second on any modern-day computer.

For any $1 \le i \le n$, let $f(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals *on the subproblem consisting of just the first $i$ elements of $x$.* So in particular, $f(n)$ will be the maximum sum of scores achievable on the entire dataset. For now, let's imagine that we have an algorithm to compute $f(i)$, and use that to compute a related quantity for an "end-inclusive" variant of the problem: let $g(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$ *that places the final ($i$-th) element inside an interval*. We can compute $g(i)$ as follows:

$g(0 \le i \< k) = -\infty$

$g(i \ge k) = \max\_{0 \le j \< i}(f(j) + s(j+1, i))$

The first equation expresses that there can be no valid end-inclusive solution if there are fewer than $k$ items in total. Using negative infinity is essentially a trick to ensure that this value is "ignored" by any $\max$ expression it happens to find itself in. You wouldn't need to actually represent negative infinity in a program; any sufficiently large negative number would work.

The second equation says that **we can always form an optimal solution to the length-$i$ end-inclusive subproblem by taking an optimal solution to *some* length-$j$ subproblem (which may or may not be end-inclusive), and appending a final interval to it containing every element after the $j$-th, up to the $i$-th -- specifically, whichever choice of $j$ yields the highest combined score.** This is the core insight of the algorithm; it's worth taking the time to convince yourself that this is really true.

From here, it's simple to compute $f(i)$:

$f(0) = 0$

$f(i \ge 1) = \max \\{g(i), f(i-1)\\}$

The first equation is obvious. The second says that we can always form an optimal solution to the length-$i$ unrestricted subproblem by taking either the optimal solution to the corresponding end-inclusive variant of this subproblem (which puts $x\[i\]$ in an interval), or an optimal solution to the one-shorter unrestricted subproblem (which doesn't) -- whichever has higher score. Again, it's worth checking that this is indeed true.

## Memoisation

You can turn each of the above equations into program code to get a working, but exponential-time recursive program that can calculate $f(n)$, the maximum score achievable. To speed this up to quadratic time only requires *not recomputing answers to subproblems that we have seen before.* This can be as simple as using an array $m\[0..n\]$, initially filled with some placeholder value like -1, to record answers just before you return them: When $f(i)$ is called, we first check whether $m\[i\]$ contains a non-placeholder value, and if so immediately return that. This approach to dynamic programming is called *memoisation* (that's right, there's no "R" in there).

## Actually computing a solution

You may have noticed that until now, the things we have been computing ($f(\cdot)$ and $g(\cdot)$) are not actual solutions to the problem but just the *scores of* those solutions. Fortunately, an actual solution can be recovered without much effort using a technique called *traceback*.

The key idea is that $\max$ function evaluations encode the "decisions" made by the algorithm. We start at the end with the final total score value $f(n)$, which we know to be optimal, and work backwards, at each step determining which argument to a $\max$ function "won" (was highest): this tells us which subproblem to consider next, and (implicitly) describes one piece of the optimal solution. (Actually there may be multiple highest-equal arguments to a $\max$; convince yourself that choosing any of them will lead to an optimal solution.) We must do this for both $f$ and $g$.

For example, suppose that $n=1000$ and that in the very first step we have $f(1000)=150$. From looking at the second equation defining $f$, our first question is whether this 150 value arose from $g(1000)$ (indicating that $x\[1000\]$ is in an interval) or from $f(999)$ (indicating that it isn't). Suppose $g(1000)=150$ and $f(999)=133$: then the former wins, so it must be that $x\[1000\]$ is in an interval in every optimal solution. The next step is to determine which $j$, in the range 0-999, gave rise to the value $g(999)=150$; this will implicitly tell us the *length* of this final interval, and provide the next subproblem to consider.

Often tracing back is sped up by storing the index of the "winner" in an extra array during the initial forward pass, but it can also be accomplished by recomputing the $f(\cdot)$ or $g(\cdot)$ function value at each step during the backward pass (which is slower, but not asyptotically so).

---
Tags: algorithms
---


# Question
Title: AVL Tree rotations : How to balance below AVL Tree with imbalance at root node
How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the double rotations still ends up producing a tree with imbalance as indicated above.

Do you mean the below solution?

# Answer
Oh, my goodness. That AVL tree tutorial at tutorialspoint is so misleading that it is the reason why you became confused. Please ignore that tutorial.

Please study the AVL tree insertion article at GeeksForGeeks instead. Or check some textbook such as *Introduction to Algorithms* by By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. This recommendation should be one of the best help you can get from asking a question.

In the graph you last uploaded, https://i.stack.imgur.com/0HivT.png, the change from the first tree directly to the last tree is called a right rotation by almost every textbook, tutorial and articles I have seen. The tree in the middle never appears. The tree in the middle is just an extra unnecessary distracting step.
> 1 votes

---
Tags: binary-trees, binary-search-trees
---


# Question
Title: Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
> I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each other?

*(I'm not sure if following thoughts are correct and formal enough and I'm glad if you spot mistakes and improve my algorithm.)*

Let $a$,$a'$ be regular expressions. Now, we want to determine: $$\bigg(L(a)=L(a') \text{ or } L(a)\neq L(a') \text{ and } \Big((L(a)\subset L(a') \text{ or } (L(a')\subset L(a)\Big)\bigg)$$

In order to do that, we will "convert" the regular expressions $a$ and $a'$ into DFA's $M$ and $M'$. Those automatons have minimal and non-redundant states $K=\\{q\_1, \cdots ,q\_n\\}$ and $K'=\\{q\_1, \cdots ,q\_m\\}$ with $n,m \in \mathbb{N}$.

Now, we can simply determine, whether $K=K'$ with showing $K\subseteq K'$ and $K' \subseteq K \implies K=K' \implies L(a) = L(a')$. If the above equation is not true, then we can imply that $K\neq K' \implies L(a) \neq L(a')$. Furthermore, with $K\neq K'$ and $K \nsubseteq K'$ and $K'\subseteq K \implies K' \subset K \implies L(a')\subset L(a)$.
Analogue: $K\neq K'$ and $K' \nsubseteq K$ and $K\subseteq K' \implies K \subset K' \implies L(a) \subset L(a')$ .

Is this enough or do I need to compare final states, transfer function and the alphabet in order to be sure $L(a)=L(a')$ etc.?

# Answer
If behaviour of the automaton didn't depend on the final states, transition function and alphabet, why would we define automata to have those useless things?
> 2 votes

# Answer
Assuming (as you do) that we can take the problem of turning a regular expression into a DFA as a solved problem and ignore its complexity,(\*) then there's a relatively simple algorithm for comparing the languages generated by two regular expressions:

Add to your alphabet two new symbols $\\$\_1$ and $\\$\_2$, and form a DFA for the regular expression

$$ ((a)\\$\_1 + (a')\\$\_2) $$

All accepting nodes of this DFA will have no outgoing edges, and so may be merged (if you form the minimal DFA, you'll only have a single accepting node, but except for merging all the accepting nodes you don't need to perform further minimization). Furthermore, all incoming edges to this merged accepting node will be labeled with $\\$\_1$, with $\\$\_2$, or both.

Examining the edges into this accepting node will tell you everything you wanted to know about the relationship between $L(a)$ and $L(a')$.

If every edge leading into the accepting node is labeled with both $\\$\_1$ and $\\$\_2$, then you have equal languages. If every edge is labeled with $\\$\_1$ but only some are labeled with $\\$\_2$, then $L(a) \supset L(a')$ (and vice versa). If there are some with $\\$\_1$ only and others with $\\$\_2$ only, then neither inclusion relationship holds.

(\*) I believe that the DFA for a regular expression with $n$ symbols can have a state space that is $O(2^n)$, or at least is some exponential function of $n$.
> 0 votes

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


# Question
Title: What's the difference between transdichotomous model and RAM?
In Wikipedia, it says

> the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size.

However, a random access machine is by definition a register machine, whose registers can store any non-negative number.

In addition, the concept of "word" is even not mentioned in the Wikipedia page of random access machine.

So what's the difference between transdichotomous model and RAM?

# Answer
The transdichotomous model is first proposed by Michael Fredman and Dan Willard \[1\]. They wrote the motivation as

> ... On the other hand, with the inclusion of division and Boolean operations, they obtain a linear time algorithm. This linear time algorithm, however, suffers from an abuse of the unit cost assumption. In particular, the algorithm generates operands during the course of its computation whose individual lengths are $N^2$ times the length of the largest of the $N$ numbers to be sorted.
>
> What seems to be needed is a computational model that avoids the potential abuses of the unit cost random access machine, but allows for unit cost operations among operands of “reasonable” size, i.e., operands of size commensurate with the sizes of the numbers to be sorted. Accordingly, we consider a reformulation of the sorting problem wherein our machine has a $b$-bit word size, and each of the $N$ input numbers is assumed to be a non-negative integer less than $2^b$ (and hence each tits into one word). Moreover, it is desirable that a sorting algorithm use only $O(N)$ words of memory.

That is to say, in contrast with RAM model, the transdichotomous model is less powerful because it does not allow unit cost operations on arbitrary large number. For example, in the sorting problem where the largest number is $m$, the transdichotomous model only allows unit cost operations on numbers no more than $m$.

---

\[1\] Fredman, M. L., & Willard, D. E. (1993). Surpassing the information theoretic bound with fusion trees. *Journal of computer and system sciences, 47*(3), 424-436.
> 0 votes

---
Tags: computation-models
---


# Question
Title: Strings which are not in a language generated by a Grammar
I have the following question and its solution

***Here T -\> XTX since T -\> X and X-\>b S -\>XbX since X-\>a S-\>aba***

So,why is option 3 not accepted ?

# Answer
> 1 votes
Read the question again, this time focus better. Take the grammar of the question, not the grammar in your mind.

I only need to see the rules for S to know that the strings in (3) are not part of the language.

S is the start symbol. Look at the rules for S. Think why I'm saying that aba and aa cannot possibly be in the language, without me having to look at any other rules whatsoever. You should be able to say "Looking at the rules for S, it is obvious that all strings in the language either xxx or yyy".

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


# Question
Title: minimum number of nodes that traverse all the graph
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover problem nor dominating-set problem since we don't need to select node 3. We say that, if we select node 0, we can go to node 1 from there and if we select node 2, we can go to node 3 and then node 4 from there.

Also, the number of nodes can be up to 10^5 and the algorithm's runtime must be 1 second or less. Any suggestion would be useful.

# Answer
> 1 votes
Try combining Tarjan's strongly connected components algorithm with a topological sort.

---
Tags: graphs, algorithm-analysis, data-structures, runtime-analysis
---


# Question
Title: How does this answer for automata and Hamming distance not lead to inconsistencies?
**I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.**

The problem:

The Hamming distance ("distance") of a word w to v of the same size is the number of positions wherein they differ. The distance between a w and L is the smallest such distance from a word chosen among L.

Let k be a natural number, and L a regular language. L' is the set of words w at a distance not greater than k from L. Show that L' is regular.

The way to go about this was to construct an automaton for such an L', and to do induction on k. If k = 0, then L' = L0 = L, and M0 = (Q0, E, delta0, q0, F0).

In general

* Q is the set of states for an automaton accepting words with a distance at most k.
* E is the alphabet among all machines and languages.
* d is the tranisition function of Mk,
* q0 is the start state for Mk
* F is the set of final states for Mk.

The answer, according to the TA:

Assuming that the construction is valid for all i \<= k, we can form M' as follows:

```
Q' = Q x {0, 1}, and **q'** is an element of Q'

q0' = (q0, 0)

d'((q, 0), a) = {(d(q, a), 0)} u {(d(q, b), 1) | b element of E}

d'((q, 1), a) = {(d(q, a), 1)}

F' = {q' = (q, t) | t = 0 or t = 1}

```

I really don't get this. To me, it seems that if I start off with less than k+1 errors then I'll be in a state (q1, 0) for some q1, and if I read 1 error then I'm put in a state (q2, 1) for some q2. If I am in a state (q1, 1) for some q1 and read anything, then I'll be in a state (q2, 1) for some q2.

If I start with reading the first letter of any input, then I start in (q0, 0), and if I read one error then I'm in (q1, 1), and if I read 50 errors then I'm in (q, 1) for some q, but if we wanted k to be, say, 5, then I've surpassed that.

I'm really confused here. I'd appreciate any help.

Thank you.

# Answer
> 2 votes
Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it.

The transformed automaton generally works as follows:

* The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet".
* The state $(q, 1)$ means "the underlying automaton is in state $q$, and we have made a single error".
* From any state $(q, 0)$, we can make the "correct" transition, or make *any* "incorrect" transition (a transition meant for any other symbol) and change the $0$ to a $1$.
* From any state $(q, 1)$, we can only make the "correct" transition. In other words, once we've made one mistake, we can't make any more!
* If we reach either $(a, 0)$ or $(a, 1)$, where $a$ is an accepting state, then we accept.

Hopefully this makes sense; let me know in the comments if it doesn't.

Now the key is, this works for *any* base automaton. So if we want $k=2$, we can just apply this transformation once, and then apply the transformation again!

The states now look like $((q, 0), 0)$. If we reach the state $((a, 1), 1)$, then we've made exactly two errors. And once we've made exactly two errors (there are no more zeroes to turn into ones), we're not allowed to make any more errors, we have to follow the base automaton exactly.

And then you can apply the transformation again for $k=3$, and again for $k=4$, and so on, for any natural $k$. Induction! QED.

(Another way to prove it is to allow errors in every state $(q, \psi)$ as long as $\psi \< k$. This way doesn't involve induction, and might be a bit easier to grasp, since you have a straightforward "error counter".)

---
Tags: formal-languages, automata, hamming-code, hamming-distance
---


# Question
Title: In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?
I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array).

I am having trouble seeing why in the inner `while`-loops, the condition $i \leq j$ is needed in addition to checking $M\[i\] \leq p$ (or $M\[i\] \> p$).

What I've tried:

* I tried running through several examples with equal elements, ordered elements etc.
* I have compared this implementation to the ones given in *CLRS Introduction to Algorithms* in hope for hints.

What I've found out so far:

* In the implementation given here, the Hoare partitioning scheme is used. However, the pseudocode given in the Wikipedia article does not seem to do this additional check.
* There is a potential problem in the given implementation that if all elements in $M\[l+1..r\]$ are les than $p$, the first while loop would not terminate when not checking for $i \leq j$. However, that does not explain the necessity of checking $i \leq j$ in the second inner while loop.

I don't expect a complete answer but I would be very thankful if someone could point me in the right direction.

# Answer
> 1 votes
> I am having trouble seeing why in the inner while-loops, the condition $i\le j$ is needed in addition to checking $M\[i\]\le p$ (or $M\[i\]\gt p$). The pseudocode given in the Wikipedia article does not seem to do this additional check. There is a potential problem in the given implementation that if all elements in $M\[l+1..r\]$ are less than $p$, the first while loop would not terminate when not checking for $i≤j$. However, that does not explain the necessity of checking $i≤j$ in the second inner while loop.

**As you suspected, it is not needed to check the condition $i≤j$ in the second inner while loop.**

One usual way to prove that condition is not needed is by analyzing all possible cases and establishing various invariants as well as employing the powerful tool of mathematical induction, which will probably convince anyone who can follow through the proof with enough patience. Although I have done that below, it is actually not convincing to myself because of the subtlety in the Hoare's quicksort as shown in Hoare's quicksort is deceptively simple, the devil in selecting element at index hi as pivot, a slight modification of Hoare's partitioning, what happens if both indexes land on the pivot. Even if I have checked my proof tens of times, it might still miss a corner case or two. As shown/implied by many answers at why is writing down mathematical proofs more fault-tolerant than writing computer code?, a traditional mathematical proof for a moderate computer program is probably far from fully satisfactory or fully correct in general. It is more like how we can understand/believe the program is correct in a high level.

Instead, I have written a program that tests the implementation of Hoare's quicksort with that condition removed.

## Here is the testing program.

That program tests the sorting algorithm against every permutation of every possible way $n$ competitors can rank in a competition, allowing for the possibility of ties, up to a certain number of competitors.

What are all possible ways $n$ competitors can rank in a competition? Here is an example for $n=3$. There are four different sorted ranks, \[1, 1, 1\], \[1, 2, 2\], \[1, 1, 2\] and \[1, 2, 3\]. If a comparison sorting algorithm can sort all permutations of each of those four arrays, which counts to 13, it will sort any array of size 3 correctly. By the way, the number of ways $n$ competitors can rank in a competition is the Fubini numbers.

If a simple sorting algorithm like the current one does not work, it should fail for an array whose size is smaller than 8. For extra insurance, I have run that program against arrays size up to 11. These testing proves that condition is not needed.

---

## A brief mathematical proof

Since many people would prefer a traditional proof, here is a sketch of a mathematical proof of **the correctness of the implementation either with or without that additional check**.

Let us assume `l < r`. Throughout the method, `M` is a constant reference to the array while `l` and `r` are constant indices. The pivot `p = M[l]` is constant, too. All we need to prove is that at the end of outer while loop, `M[l]` is the pivot, followed by elements not bigger than the pivot up to index `j` inclusively or no elements if `l >= j`, followed by all other elements, which are bigger than the pivot. (Then by mathematical induction on `r - l`, we can prove easily that the method does sort the subarray of M from indice `r` to `l` inclusively.)

* We can establish the following invariant at the end of each iteration of the outer while loop.
    + Elements from `l + 1` to the smaller of `i` and `j` are not bigger than the pivot
    + Elements from `j + 1` to `r` are bigger than the pivot.
* The first inner loop, `while ( i <= j && M[i] <= p) { i = i + 1; }` will find the smallest index `i` such that `i <= j && M[i] > p` or `i == j+1`.
* The second inner loop, either `while (M[j] > p) { j = j - 1; }` or `while (i <= j && M[j] > p) { j = j - 1; }` will find the largest $j$ such that `M[j] <= p`.

Why is the condition `i <= j` not necessary? Let us elaborate as here is the crux of current question.

There are two cases at the start of this loop depending on the result of above inner loop.

1. `i <= j && M[i] > p`. As we are looking for an element that is not larger than the pivot going from index `j` to smaller indices, the latest time we will succeed must before current `i`. That is, `i <= j` will always be satisfied throughout the loop. That is, the condition `i <= j` is not necessary.
    2. `i == j+1`. The first inner loop must have missed the above case, since j is smaller than j + 1. That means `M[j] > p` was not satisfied. So at the start of current loop, we have both i \> j and M\[j\] \<= p. Using either version of the second inner while loop, we will break the loop right away.
* `if (i < j) { swap(M, i, j);}`. This swap extends both the left hand side of elements that is not bigger than the pivot and the right hand side of elements that is bigger than the pivot.

To tell the truth, I used program to double check various invariants and propositions in the mathematical proof.

---

**Many further questions** can be raised, which go much beyond the scope of the current question.

* How to improve the performance of the testing problem?
* How to reduce the number of test cases needed for a specific size?
* Is there a way to determine rigorously an upper bound of the size of the array that need to be tested to prove the correctness of a sorting algorithm given its description?

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?
Let $A$ be an event divided into 4 events $A\_i$ with the same probability. Why does the quantity of information of $A\_i$ satisfy $$ I(A\_i) = I(A) + \log (4)?$$

# Answer
> 0 votes
I believe that the correct formula is $$ I(A) = \log \frac{1}{\Pr\[A\]}. $$

In this case, we have $$ I(A\_i) = \log \frac{4}{\Pr\[A\]} = \log \frac{1}{\Pr\[A\]} + \log 4 = I(A) + \log 4. $$

---
Tags: probability-theory, information-theory, mathematical-foundations
---