# Question
Title: When should genetic algorithm's variation operators be specialized?
Genetic algorithm (GA) is *general purpose* metaheuristic often used in computational science, e.g. computational physics. However, some authors of computational physics software, e.g. \[1\], tend to *specialize* GA to the given problem on the level of variation operators. I do appreciate this approach and their work, but I wonder if it is really necessary to specialize GA's variation operators instead of relying on canonical ones easily available in GA litearature. In other words, I wonder if it is perfectly fine to limit GA specialization to genetic representation (genotype) and genotype/phenotype mapping only.

My questions:

1. Should variation operators be ever specialized to the problem?
2. \[Optionally\] Is there any criterion to know *a priori* if variation operator specialization is necessary?

Could you please *optionally* support your answer with literature reference(s)?

\[1\] David C. Lonie and Eva Zurek. "XtalOpt: An open-source evolutionary algorithm for crystal structure prediction". *Computer Physics Communications* **182**.2 (2011) pp. 372-387 DOI: 10.1016/j.cpc.2010.07.048

# Answer
> 1 votes
It's usually better to customize your approach to things that you know about your specific problem. NFL (the No Free Lunch theorems) applies here, so on average across all possible problem instances, everything performs equally. This implies that there are some problems where approach A will outperform approach B, and then on the complement of that set of problems, B will outperform A. And we don't know a lot about how to construct those sets. So there's not a lot of formal theory to guide you here.

In practice though, solving a specific problem is usually easier than solving a general one. Small search spaces are usually easier to work with than larger ones. There are multiple ways to think about that general idea, but the gist is something like this. Let's say I have a problem I've encoded solutions for as a 128 bit string that I decode into whatever parameters. If I know from domain knowledge that the best solutions are likely to start with 16 consecutive ones, I can build my operators to generate such strings more often than uniform random chance would do, and my algorithm will probably work better. If I have a knapsack problem where I know that taking too many items will put me over capacity making for an infeasible solution, my algorithm will virtually always perform better if I make my search operators favor sparser candidates that are under or near the capacity limit.

You have a fixed budget of computational resources to apply to evaluating possible solutions. Customizing your search operators is a way to force the algorithm to spend more of that budget looking at solutions that are plausibly useful.

It's not impossible that an off-the-shelf search algorithm outperforms a customized one. We're not perfect and can make mistakes that lead to the customized algorithm doing specifically *bad* things. And sometimes the world just works out that way. Maybe you have a problem where you really need to spend more time out in the weeds because there's some information out there that's vital to exploit. But it's not what I'd expect most of the time. The advantage of an off-the-shelf search method is that it's quick and easy to deploy, and it may be good enough. I'd usually expect to be able to beat it with careful thought put towards operator design though.

# Answer
> 1 votes
It's not *necessary*. But customizing the operators might yield better results (either faster convergence, or higher-quality solutions). In some cases this kind of customization can help a lot. In others it might not help much, or at all.

There's no surefire way to know a priori whether customization will help. The only way to know is to try it and see. Or, you can search the academic literature: if you can find someone who has tried solving a similar problem and published their work, then you can learn from their experience.

---
Tags: optimization, genetic-algorithms
---


# Question
Title: Intuition for Sipser's proof of PDA to CFG
I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two. He splits the proof (Lemma 2.27, page 121) in 4 parts:

1. Modify the PDA so there's 1 start state, 1 final state and every transition increments or decrements the stack height by one. This part is straightforward.
2. Generating rules.
3. Proving: If Apq generates x, then x can bring P from p with empty stack to q with empty stack.
4. Proving: If x can bring P from p with empty stack to q with empty stack, Apq generates x

First, I don't understand what the rules accomplish. Then I don't understand how the last 2 proofs show that PDA can be converted to CFG. I watched youtube lectures (including EasyTheory's), the diagrams in the book and some notes online but failed to gain the intuition for what's happening in the proof. I would appreciate if someone could demystify it for me.

# Answer
The secret of the PDA to CFG proof is recursion. CFG's are by definition good in recursion.

Sipser explicitly constructs a CGF and the Lemma's are provided to show his construction works. His CFG has nonterminals of the form $A\_{pq}$ and the intuitive meaning is that they correspond to "computations of the PDA starting in state $p$ ending in state $q$ where at the start and at the end the stack is empty". The proof shows that the CFG generates strings on nonterminal $A\_{pq}$ when the PDA reads the same strings on computations of the $A\_{pq}$ type.

Here are the productions that should make this work.

(1) Choose any two matching instructions as follows. One instruction from state $p$ to state $r$ which pushes a stack symbol $u$ and reading $a$ from input, and one from state $s$ to state $q$ popping same $u$ reading $b$. Then $A\_{pq} \to a A\_{rs} b$.

Any computation of a PDA that pushes $u$ must later pop that symbol where the stack below has not been touched. That is recursion: the computation $A\_{pq}$ is replaced by the computation $A\_{rs}$ which is inside the original computation, but has now additional $u$ on stack, from state $r$. We compute until $u$ is popped, and this is possible in state $s$.
This is for specific $p,q,r,s$ that have matching push and pop instructions.

(2) The computation from $p$ to $q$ from empty stack to empty stack might have an empty stack on the way. Then we have to introduce an intermediate state $r$, more or less in order to continue from there. (We push and pop our first stack symbol, and now need to continue with the next stack symbol.) Thus $A\_{pq}\to A\_{pr}A\_{rs}$. This is for all $p,q,r$ in order to continue a computation.

(3) The empty computation is also of the right form, so we have $A\_{pp} \to \varepsilon$ as it generates nothing.

I like to note that Sipser has a somewhat nonstandard proof. Most books have a similar recursive construction, but also include the nonterminal that is put on the stack. Hence its nonterminals are of the form $\[p,u,q\]$ meaning a computation from state $p$ to state $q$ with only $u$ on the stack until that $u$ is popped. Same intuition, technically different as Sipser "predicts" the final $q$ (it is chosen as a "pop" to match the initial "push") whereas many other books "guess" the state $q$ where the pop will occur.
> 1 votes

# Answer
Let's denote the start state as $s$ and accept state as $t$. To prove that every PDA $P$ can be converted to some CFG, we can:

1. for every PDA $P$ show an CFG $A$. This is part 2: show how to construct the CFG $A\_{st}$.
2. prove that the languages recognized by $P$ and $A$ are equivalent.

To prove the second point, we should show it in both directions:

1. $L(P) \subseteq L(A)$ (here $L(P)$ means the language recognized by $P$). Here is the goal of part 4: every string recognized by $P$, (i.e. can bring $P$ from $s$ with empty stack to $t$ with empty stack), can also be generated by $A\_{st}$.
2. $L(A) \subseteq L(P)$. This is the goal of part 3: every string generated by $A\_{st}$ can bring $P$ from $s$ with empty stack to $t$ with empty stack, i.e. be recognized by $P$.

Sipser proved the two points above inductively, so part 3/4 are more generalized version of the two goal above.

In fact, the final proof is often presented in the "opposite" direction of our thinking (i.e., the part of the proof that we end up thinking about may appear at the very beginning of the proof, while the most intuitive part is often hidden), so to catch the intuition is always difficult somehow.
> 0 votes

---
Tags: context-free, pushdown-automata, theory
---


# Question
Title: How to round numbers to its 0.5 superior in python
So basically my question is if i have for example 2.2 i need to create a python function to round numers to its higher 0.5 part, i mean 2.2 --\> 2.5 2.3 --\> 2.5 2.5 --\> 2.5 2.6 --\> 3 I cant use anything but maths operators ( +, \*, \**, //, %, - )

# Answer
The trick is to count in halves instead of units, i.e., double double the original number, round it the next integer, and finally divide back by $2$.

Rounding a number $x$ down previous integer using only the listed operators is quite easy: just use the integer division by $1$, i.e., `x//1`.

Rounding $x$ to the next integer is a bit more annoying (notice that you can't just add $1$ to `x//1`). What we can do is inverting x, rounding down, and then inverting the result again.

Putting all together: `-((-2*x)//1)/2`
> 0 votes

---
Tags: logic
---


title: Regular languages that seem irregular

text:
# Question
Title: Regular languages that seem irregular
I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated.

So far I've found two. One is $L\_1=\\{a^ku\\,\\,|\\,\\,u\in \\{a,b\\}^∗$ and $u$ contains at least $k$ $a$'s, for $k\geq 1\\}$, from this post, and the other is $L\_2 = \\{uww^rv\\,\\,|\\,\\, u,w,v\in\\{a,b\\}^+\\}$, which is an exercise (exercise 19 from section 4.3) in An Introduction to Formal Languages and Automata by Peter Linz.

I suppose the aspect of seeming to be regular depends on your familiarity with the topic, but, for me, I would have said that those languages were not regular at a first glance. The trick seems to be to write a simple language in more complicated terms, like using $ww^R$, which reminds us of the irregular language of even length palindromes.

I'm not looking for extremely complicated ways of expressing a regular language, just some examples where the definition of the language seems to rely on concepts that usually make a language irregular, but are then "absorbed" by the other terms in the definition.

# Answer
> 24 votes
My favorite example of this, which is often used as a difficult/tricky exercise, is the language: $$L=\\{w\in \\{0,1\\}^\*:w \text{ has an equal number of } 01\text{ and }10\\}$$ This has the strong flavor of the non-regular "same number of $0$ and $1$", but the alternation of $0$ and $1$ makes it regular nonetheless.

# Answer
> 10 votes
Here is another all time favourite language that looks very non-regular. All these questions refer to the same language.

Is the language of words with as many a's in the first as b's in the second part context-free?

Finite strings and relationships between words

DFA for the language L = { w=xy∈(a,b)∗∣|x|a=|y|b }

Is language {a,b}∗ same as language $\\{\\;xy\in \\{a,b\\}^∗ \mid |x|\_a=|y|\_b\\;\\}$?

How to check L is regular or not

# Answer
> 9 votes
For a different kind of example, consider the language consisting of the usual decimal representations of integer multiples of 7, namely $\\{ \dots, -14, -7, 0, 7, 14, 21, 28, \dots \\}$. This is a regular language. (And in fact, the same would be true with any other positive integer instead of 7; but 7 is a cool example because, unlike with the other small integers, there isn't a commonly-known way to tell if a string of digits represents a multiple of 7 other than doing the division and seeing if the remainder is zero.)

---

To see why this is a regular language, let's first focus on just decimal representations of *positive* integers. These representations can be grouped into seven sets: one for the multiples of seven (7, 14, 21, etc.), one for *one plus* a multiple of seven (1, 8, 15, etc.), one for *two plus* a multiple of seven (2, 9, 16, etc.), and so on. The important thing is that if we have a string $x$ representing a positive integer and a single digit $d$, then we can figure out which set $xd$ is in based only on $d$ and the set that $x$ is in. For example, if $...348$ represents *two* plus a multiple of seven, then $...3485$ has to represent *four* plus a multiple of seven (because if $...348$ represents $2 + 7n$ for some integer $n$, then $...3485$ represents $10(2 + 7n) + 5 = 25 + 7n = 4 + 7(n + 3)$). So we can create a DFA with a separate state for each of these sets (plus an initial state for the empty string), and simply set the "accept" state appropriately in order to have it detect decimal representations of positive multiples of 7.

Extending this to decimal representations of *arbitrary* multiples of 7 is straightforward; we just need an extra state for leading $0$ (which is an "accept" state with no outbound edges) and an extra state for a leading minus sign (which is equivalent to the initial state except that it doesn't have an outbound edge to itself or the $0$ state).

And likewise for any other positive divisors instead of 7, though obviously there are some divisors that can be handled with fewer states than that.

# Answer
> 6 votes
Multiples of three, expressed in binary, especially combined with a proof that powers of three, expressed in binary, is not a regular language. (Or in general: multiples of $n$ expressed in base $b$ are regular, whereas powers of $n$ expressed in base $b$ are a regular language iff there exist positive integral $p$ and $q$ such that $b^p = n^q$)

See also numbers (with decimal point, but finite expansion) written in base 10 greater than $x$. (or less than $x$) This is regular if and only if $x$ is rational. That "positive numbers with finite decimal representations less than $\sqrt{2}$" is not a regular language is probably not too surprising, but it might be surprising that "decimal numbers representing a value between $\frac{1}{7}$ and $\frac{2}{7}$" *is* regular.

# Answer
> 5 votes
You could get many examples from languages that are finite but don't look it. For example, the language of strings all of whose prefixes are decimal representations of prime numbers is regular because there are only 83 such strings (A024770).

The language of sequences of `0`s that appear in the decimal expansion of $π$ is regular. It showed up in a different context in this question.

The language of finite substrings of the decimal expansion of Chaitin's Ω is regular because Ω is provably normal.

---
Tags: regular-languages, reference-request
---


# Question
Title: Are both regular expressions correct for the given DFA with three states?
Are both regular expressions correct for the following automaton?

$$(\lambda+ a a^\*b(ab)^\*)(\lambda + b(a+b)^\*)\\ \ \\ (a a^\*b)^\*(\lambda + b(a+b)^\*)$$

The first one is the solution provided by the teacher. The second one is my solution that I found by the algorithm where we use a generalized transition graph and remove states (and where we can only have 1 final state).

# Answer
> 2 votes
There are general algorithms to determine whether two regular expressions represent the same language. A classic approach is described here.

---

The expression given by your teacher, $E=(\lambda+ a a^\*b(ab)^\*)(\lambda + b(a+b)^\*)$ does not correspond to the DFA shown. For example, string $aba^2b$ is accepted by the DFA. However, it is not in $E$.

By distributive law, $(\lambda+ a a^\*b(ab)^\*)(\lambda + b(a+b)^\*) = \lambda+ a a^\*b(ab)^\* + b(a+b)^\* + aa^\*b(ab)^\*b(a+b)^\*$

* $aba^2b\not = \lambda$
* A string in $a a^\*b(ab)^\*$ does not contain $a^2$ after the first $b$.
* A string in $b(a+b)^\*$ starts with $b$
* A string in $(a a^\*b(ab)^\*)b(a+b)^\*$ contains $b^2$ since a string in $(a a^\*b(ab)^\*)$ must end with $b$.

---

Your solution, $F=(a a^\*b)^\*(\lambda + b(a+b)^\*)$ is correct. The correctness is justified by the methodical procedure you have done.

For this simple case, we can also verify it by straightforward reasoning, which is basically paraphrasing the procedure.

An accepted string either ends up in state $q\_1$ or $q\_0$.

* A string ends up in state $q\_1$ iff the DFA will transition from $q\_1$ to $q\_2$ and back to $q\_1$ zero or more times, each time reading one or more $a$s followed by one $b$. That means $(aa^\*b)^\*$
* A string ends up in state $q\_0$ iff the DFA will reach $q\_1$, then transition from $q\_1$ to $q\_0$, then loop at $q\_0$ zero or more times.

+ Reaching $q\_1$ entails $(aa^\*b)^\*$.
    + Transitioning from $q\_1$ to $q\_0$ entails one $b$.
    + Looping at $q\_0$ entails $(a+b)^\*$.

Concatenating three pieces together, we get $(a a^\*b)^\*b(a+b)^\*$.

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


title: Simple Skolemization Question

text:
# Question
Title: Simple Skolemization Question
Is it correct that, under a certain signature S, two First Order Logic formulae F and G are equisatisfiable if (F is satisfiable under S iff G is satisfiable under S)? But in Skolemization I’m confused because the signature ends up changing when fresh functions are added (when you remove the for-all quantifiers), so how come the skolem form is equisatisfiable with the original formula if the signatures have changed? Any help is appreciated!

# Answer
I'm assuming we're talking about classical first-order logic here.

Consider two sets of formulas $\Gamma$ and $\Lambda$. If $\Gamma$ and $\Lambda$ are equisatisfiable, it means that $\Gamma$ has a model iff $\Lambda$ has a model. They don't even have to be the same model! So it's a pretty weak condition. And it's what allows two theories with different signatures to be equisatisfiable.

By the Soundness and Completeness theorems, we have for any $\Gamma$ that $\Gamma$ is satisfiable iff $\Gamma$ is consistent. From this we can conclude that if $\Gamma$ and $\Lambda$ are equisatisfiable, then $\Gamma$ and $\Lambda$ are equiconsistent.

So in the case of Skolemization, we've reduced the problem of equisatisfiability to the problem of equiconsistency. So all that's left is to show that Skolemization doesn't introduce any inconsistency.
> 1 votes

---
Tags: logic, satisfiability, first-order-logic, propositional-logic
---


# Question
Title: Optimal way to construct union automata of two DFAs
Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the combination of those states to the new automata and so on. So that I do not have to first take every possible combination of states and then fill the transitions and finally remove the inaccessible ones. Is this "faster way" correct?

# Answer
Yes, this works, as long as you do it right. If you do it right, you only explore the reachable states of the product automaton. Since the other states aren't reachable, it doesn't matter whether you include them in the resulting automaton or not.
> 2 votes

# Answer
That's basically the idea. It's effectively equivalent to the standard algorithm:

1. Construct an NFA with all the states and transitions of the DFAs being combined, plus a new state $q\_0$ with has ε transitions to each start state of the DFAs. The set of final states of the NFA is the union of the final states of the DFAs, and the start state of the NFA is $q\_0$.
2. Use the subset construction to create a new DFA from the NFA.

In fact, the above algorithm would combine NFAs as well.
> 0 votes

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


# Question
Title: How to make an algorithm to optimally make student groups without overlap
My sister (a high school teacher) came and asked me the following question:

> "Hi bro I'm having 28 new students in my class. They need to know each other. So I want everybody to work together in small groups. I'm thinking splitting them in groups of 4 and having 9 rounds. Then everyone meets 3 people in every round and after 9 rounds they have been in a group with everybody. Isn't that pretty. But I'm just missing an algorithm to set up the groups and you are a CS-master that must a be a job for you!"

I have been trying to figure it out, but the combinatoric search space is to big. Do you have a good suggestion for a way to create these groups.

# Answer
> 1 votes
You can solve it with satisfiability. Here i have created the SAT formula for you. Sorry i deleted this answer earlier because i forgot to add a formula, i fixed it, it should be correct now.

---
Tags: algorithms
---


# Question
Title: Give an example of a language $B$ is $NL-complete$ where $B^* \in L$
I need to give an example of a language $B$ is $NL-complete$ where $B^\* \in L$.

I know $PATH$ is $NL-complete$ (but not limited to using other languages).

I am clueless about that. I know $L$ is not closed under $^\*$ so there must a language like that.

Any help would be appreciated.

# Answer
Let $\Sigma=\\{0,1\\}$. Take any NL-complete language $C \subset \Sigma^\*$ and consider $B = C \cup \\{0,1\\}$. Clearly $B$ is still NL-complete (since $|B \\, \Delta \\, C| \le 2)$ and you have $B^\* \supseteq \\{0,1\\}^\* = \Sigma^\*$, i.e., $B^\* = \Sigma^\* \in L$.
> 2 votes

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


# Question
Title: How do we know that Icosoku always has solutions?
This is a continuation of a question I asked here. The puzzle Icosoku is now described by Wikipedia as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin. The manufacturer asserts that there is a solution for each pin arrangement. The puzzle is shipped in a solved state. The pins are not suitable for children under three, but this toy is otherwise suitable for all ages."

My question is how can one prove that there is a solution for each pin arrangement, as the manufacturer asserts? There are 12 factorial ways of arranging the pins (less by a factor of 1/120 if one considers the symmetry of the icosahedron), so using brute force to prove this might be a bit challenging.

# Answer
> 1 votes
You are right, the author of the game did not provide any hint to why IcoSoKu always has a solution. The latest product page is quite cheeky:

> With the perfect geometry of an icosahedron, Icosoku can be solved every single try!

I don't know any mathematical proof, but Prof. Agostino Dovier and I solved the problem via brute-force, because you don't need to solve 12! instances:

* we can impose the first vertex (chosen arbitrarily) to hold pin 1;
* we can still rotate the icosahedron around the axis that goes through the first vertex (and the opposite one), so for the second vertex, an arbitrary neighbour of the first vertex, we can impose that it holds the pin with the smallest pin number between the neighbours of the first vertex;
* we can still mirror the icosahedron (think of it as playing by looking through an actual mirror), and **since the tile set is unchanged by this operation** (this symmetry-breaking argument wouldn't work otherwise!) we need to solve only one between any instance and its mirrored version.

You can read the details in the paper or in the repo for the software we developed, but I computed the unique 3 991 680 instances and their solutions, solving IcoSoKu I guess :)

---
Tags: proof-techniques
---


# Question
Title: Is $L=\{\langle M_1,M_2\rangle|L(M_1)\cap L(M_2)\neq \emptyset \}$ R, RE or coRE?
Below is the language, determine (R), (RE), (coRE). and prove your answer.

$L=\\{\langle M\_1,M\_2\rangle|M\_1,M\_2$ are Turing-machines and $L(M\_1)\cap L(M\_2)\neq \emptyset \\}$

**Attempt:** I Think the language $L\in RE$ Because we need to use $U-MT$ such that we check all the $L(M\_1)\cap L(M\_2)\neq \emptyset$ to see if all language in the Machines at least 1 accept to be not equal to the empty set so it can be infinity and the last one will be in both language in the machines.

I would like someone will verify and clarify the situation, and give me some steps to prove that.

Thanks!

# Answer
> 0 votes
First, $L$ is not recursive: there is an easy reduction from $L\_{ne}=\\{\langle M\rangle \mid \mathcal{L}(M) \neq \emptyset\\}$ which is a well known non-recursive language (for the reduction, just use a TM $M\_2$ such that $\mathcal{L}(M\_2) = \Sigma^\*$).

Now, $L$ is indeed recursively enumerable. The intuition behind this is the following ; considering inputs ordered lexicographically:

```
n ← 1
repeat:
    simulate n computation steps for the n first inputs for M1 and M2
    n ← n + 1
until:
    M1 and M2 accepts the same input x
return true

```

If $\langle M\_1, M\_2\rangle\in L$, then the previous algorithm will stop and return `true`. Otherwise, the algorithm will never stop.

Finally, since $L$ is not R but RE, it means that $\overline{L}$ is not RE, so $L$ is not coRE.

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


title: What is bottom-up pattern matching?

text:
# Question
Title: What is bottom-up pattern matching?
On the website for the book *Modern Compiler Design*, it is claimed that:

> \[The book\] recognizes lexical analysis, LR parsing and BURS code generation as instances of bottom-up pattern matching and explains them uniformly using dotted items, thus unifying three important techniques in compiler design, \[...\]

(BURS seems to stand for *bottom-up rewrite system*.)

**I would like to know what *bottom-up pattern matching* is**, but searching for that term did not give me too many results. One result is about *bottom-up tree pattern matching*, but it is unclear to me whether this is the same thing or not.

# Answer
> 1 votes
Matching is the same activity for regular expressions (and variants of them) as parsing is for grammars.

Top-down matching/parsing tries to expand parse trees for the input from the root downwards. Standard examples in compiler construction courses are *recursive descent* and *LL(k) parsing*.

With top-down parsing, while scanning the input, you maintain a single valid parse tree for the input up to that point.

With recursive descent, as soon as your parse is failing, you recursively back up and try the next alternative, until the parse is complete or all alternatives have been exhausted. This is guaranteed to produce a valid parse if one exists, but it may take exponential time in the length of the input.

If the grammar is LL(k), it guarantees that whenever multiple alternatives exist for continuing the parse, you can always decide which one to use by looking ahead no more than k characters in the input. So you'll never have to back up, and parsing can be done in linear time - provided you have an LL(k) grammar, which not all languages have.

Bottom-up matching/parsing tries to assemble parse trees from the leaves upwards. Standard examples in compiler construction courses are *Earley parsing*, *GLR parsing*, and *LR(k) parsing*.

With bottom-up parsing, while scanning the input, you maintain a representation of all valid partial parse trees for the input up to that point. So you'll never back up; instead, you construct all valid partial parse trees in parallel. While their total number can be exponential, for context-free grammars they can be represented and constructed in polynomial (cubic) time. Earley parsing, GLR parsing, and its variants make this work for arbitrary context-free grammars; LR(k) parsing is a less general method that, again, uses lookahead to always reduce the number of partial parses to consider to at most one, and only works for LR(k) grammars, which, again, not all languages have.

I can't find any examples of bottom-up matching directly on regular expressions; the custom is to convert them to nondeterministic or even deterministic automata and use those to do the matching.

---
Tags: parsers
---


# Question
Title: Is there a computationally efficient algorithm which can map back and forth a multi-dimensional real number (R^n) to a single dimensional real (R)?
I believe its possible to achieve this with natural numbers. The example below is for 2d to 1d conversions both ways, I do believe this generalizes to n-dimensions.

The mapping should work in a way that means that there is a total order of the elements on each side of the mapping, ie. moving through one space in order should move through the other space in order, i.e. between their corresponding min's and max's.

I think the question I'm asking is:

`Does there exist an f: R^n -> R, where f is invertible , a bijection and there are total orders on R^n and R, where there is a bijection between these orders`

I think would get the orders requirement for free if the invertible bijection exists?

I'm looking to apply this to the Real numbers. I realize the examples below use modulo which is not supported in Real arithmetic. Could this be possible for the reals as I believe there is a bijection between R^n and R. Is there an algorithm for this that exists already?

Assume width is the known length of one of the 2d dimensions.

1d to 2d integer:

```
y = index / width;
x = index % width;

```

2d to 1d integer:

```
index = x + width * y;

```

# Answer
The answer is of course yes. Take any bijection $f:\mathbb{R}^n \to \mathbb{R}$, and define a total ordering on $\mathbb{R}^n$ as follows: for each $x,y \in \mathbb{R}^n$, we define $x\<y$ iff $f(x)\<f(y)$. This defines a total order on $\mathbb{R}^n$, and now $f$ plus this total order meets your condition.

(See also Hilbert's space-filling curve.)

I suspect your formulation of the question doesn't match what you really want to know.
> 1 votes

---
Tags: algorithms, sets, real-numbers
---


# Question
Title: What are some algorithms with runtimes that involve a \log{n} term with a negative exponent?
Are there any (deterministic or randomized) algorithms that run in time $\operatorname{poly}(n)\log^p{n}$ for $p \< 0$? What are some examples?

# Answer
Consider the following algorithm:

```
Input: a natural number n
Output: the list of prime numbers ≤ n

lst ← []
for x from 2 to n do
    if x is not a multiple of any number in lst then
       append x to lst
return lst

```

Using the prime number theorem, it is not that difficult to prove that the algorithm runs in $\mathcal{O}\left(\frac{n^2}{\log n}\right)$.

Of course, this algorithm is quite inefficient, as the sieve of Erathosthenes runs in $\mathcal{O}(n\log \log n)$ (and some versions of it in $\mathcal{O}(n)$), but it is simple to implement, so it is an example as good as it is.
> 2 votes

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


title: Turing machine accepting mirrored words

text:
# Question
Title: Turing machine accepting mirrored words
I'm trying to make a Turing machine which accepts $ww^R$, for example $w = aababbabaa$ and I'm unsure as to how to make this work.

Below is an attempt for such Turing machine, but it gets stuck when the second to last b becomes B and the very last a becomes A.

# Answer
If I understand correctly the image you gave, it seems like the problem with your TM is that after it reads and convert an `a` to `A`, it searches and converts the rightmost `b` instead of an `a` (same goes when it reads a `b`).
> 2 votes

# Answer
Given, M(Q,T,B,£,¥,q0,F) T = Tape Alphabet = (a,b,X,B) B = blank symbol ¥ = transition function ( To simplify I just wrote imps) You can see the below link of image right!(reference image) Click to see the solution. PS: HOPE YOU LIKED THE ANSWER.... Don't forget to upvote;)
> 0 votes

---
Tags: turing-machines
---


# Question
Title: How to build a DFA that recognizes a language
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):

Build a **DFA** that recognizes the following language knowing that `E = {0, 1}, {w | w is any string except 11 and 111}`.

My solution is:

Is that correct? Thanks.

# Answer
> 0 votes
Initially build a finite automata of the language which generates only strings 11 and 111 And then by complementing the finite automata we will obtain the language which accepts all strings except 11 and 111 As we know that L(M)'=U-L(M)

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


# Question
Title: Show that an instance of PCP or MPCP has no solutions
I'm studying the Post Correspondence Problem (PCP) and understand the concept, although I have problems with proving how to show that an instance of a PCP or modified PCP has no solutions.

For instance, how could I show that the the instance $\ ((0,11,1), (001,1,11)) $ of an MPCP has no solutions? and what is the thought behind it?

# Answer
We know that the post correspondence problem and the modified post correspondence problem are undecidable.

It means for both of the problems, we may or may not get the solution depending on the question.

There is no certain procedure or algorithm for the pcp and mpcp problem. So we may not solve the problem in some cases.

Given a question ((0,11,1),(001,1,11)) and we need to find the modified post correspondence problem.

In the modified post correspondence problem, we need to start with the first domino of the question.

While solving the given problem, we will get an infinite loop and we can't get a finite solution.

So we can get

((0,0,1,0,0,1,11,0,0,1,0,0,1,11,.......), (001,001,11,001,001,11,1,001,001,11,001,001,11,1......))

In this,we can see that the dominos are repeating after some steps.

The repeating set of dominos are ((0,0,1,0,0,1,11),(001,001,11,001,001,11,1))

So this lead to the infinite state and can't be solved.

We can say that, this instance is undecidable.

So modified post correspondence problem is undecidable. Hence there are no solutions for the given instance of modified post correspondence problem.
> 0 votes

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


# Question
Title: Minimize the DFA(Deterministic finite Automata) given in the picture
How to minimize the DFA given in the picture

# Answer
> 0 votes
Add p and q and make them as a single state. Combine s and u because they Are final states. We cannot combine t and r because on the same input they go to different states. you will understand good when u see the minimized DFA given below Now we obtain 4terms {(p,q),r,t,(s,u)}

# Answer
> 0 votes
Here we can combine p and q to form a single state because p on 0 as input goes to state q and q on 0 as input goes to state p and both p and q go to state s on 1 as input.Similarly we can combine states s and u because state s goes to u on both inputs 0 and 1 and state u stays in the same state on inputs 0 and 1.We can't combine r and t as they don't reach same state on same inputs.The minimised DFA is having 4 states as follows:

---
Tags: finite-automata
---


# Question
Title: Universal Turing machine simulating the null Turing machine?
The definition of the universal Turing machine is

$$ U(\langle M \rangle,p)=M(p) $$

where U is a universal Turing taking two inputs $\langle M \rangle$, the binary encoding of a Turing machine, and $p$ a binary program.

What happens in the case where we feed the null Turing machine to the UTM.

$$ U(0,p)=?U(p)? $$

Will this give out the outputs that are specific to the given formulation of the UTM being run?

Also, is there any kind of general properties of $U(p)$ between the universal Turing machines? My intuition tells me $U(p)$ must be the same answer for all UTMs and all $p$, but I would like confirmation.

# Answer
Yes...your intuition to the problem approach is correct.Here are the properties from which you can gain much more clarity: Unsolvable Problems Stanford-Stanford University
> -1 votes

---
Tags: turing-machines
---


title: What is a CPU clock physically?

text:
# Question
Title: What is a CPU clock physically?
I can't seem to get a straight answer as to what a CPU clock is.

I know there are quartz crystal clocks that work by the bending of quartz that happens as an electrical current is passed through it. Do modern CPUs also use a crystal with the same property?

# Answer
> 38 votes
Modern clocks are originally generated by quartz crystal oscillators of about 20MHz or so, and then the frequency is multiplied by one or more phase-locked loops to generate the clock signals for different parts of the system. (such as 4GHz for a CPU core).

This is mostly a question of electronics design, though.

# Answer
> 7 votes
A CPU clock is a signal which is used for two related purposes:

1. Devices that are synchronous to a common clock agree that they will only look at signals from other such devices within a very short window after the clock changes.
2. Devices which are synchronous to a common clock agree that within that window they will never change any signals that are of interest to other such devices.

A very important feature of such systems is that there is never any ambiguity over which of two things happens first. Instead, either one will happen on an earlier clock than the other, or they will happen on the same clock in which cases they are *unambiguously tied*.

If computers would always process all operations in a fixed sequence that is decided in advance, it could have the circuitry that performs each operation wait until all preceding operations are done, without any need for a clock. Some parts of systems are sometimes designed that way, but in many cases some resources will be required to perform several operations, and it may be desirable to allocate the resource immediately to whichever operation is ready to use it first, and then have any later operation that needs the resource wait until the first operation is done with it. In systems that don't use clocks, however, this will create a problem.

If two operations that would need a resource become ready simultaneously, it is necessary that the circuits that would perform the operations both agree on which one should go first, before either proceeds. If each tasks thinks it should go first, the tasks will grab the resource simultaneously (oops). If each task thinks it should defer to the other, the tasks will deadlock waiting for each other to complete.

There are ways of resolving such situations in asynchronous systems by having both tasks recognize a window in which the other task might have beaten them, and will back off for an amount of time based upon how far they think were from the edge of that window, and then see if that results or one side or the other winning unambiguously (backing off again if it doesn't). Unfortunately, while the probability of a tie lasting for more than t microseconds would decrease exponentially with t, it's often difficult to parameterize how fast that will occur.

Having devices operate synchronously fixes this, since it makes it possible to design two circuits so that X will take a resource as soon as it becomes ready unless Y had been ready for it during the previous observation window, and Y will take the resource as soon as it's ready unless either X was ready for it in the previous window, or has become ready in the *current* window. While the likelihood that X and Y become ready "simultaneously" would be much greater than in the asynchronous system, such occurrences wouldn't cause problems.

While there are a variety of ways that a computer can generate the clock signal which is used to coordinate communication among the many components, an understanding of the purpose of the clock is far more important, especially from a computer-science perspective, than knowledge of the particular means used to generate it, and the principles involved are very similar to those involving long-range networking.

# Answer
> 6 votes
This is a picture of a DIY quartz clock:

This is (part of) a picture of a mainboard:

Note the component I have marked with an arrow. You can see they look identical.

Some caveats:

* Quartz crystals come in different packages, I have chosen two examples that happen to use the exact same package.
* They will have different frequencies: mainboards usually use 14.318 MHz (I think that's a relic of TV output in early PCs), quartz clocks usually use 32.768 kHz (this one uses 12 MHz probably because their microcontroller can't run on such a slow clock).
* The CPU does not use the 14.318 MHz directly but it is multiplied by a PLL circuit, possibly in one of the black ICs on the right side of the image.

# Answer
> -1 votes
I beleive modern cpus require a click source signal which is usually generated by a capacitor circuitry rather then a crystal. I Beleive crystals and other ics are used more for arm mcu. For CPU’s an llc circuit is used to deliver the clock source.

---
Tags: cpu, clocks
---


# Question
Title: Does NFA to DFA conversion give the minimal DFA as result?
When converting NFA to DFA, do I always get the minimal DFA or not?

# Answer
> 2 votes
No, it is not in general minimal. The standard determinization procedure, the subset construction, always converts an NFA with $n$ states to a DFA with $2^n$ states and there is no reason that this should be minimal.

In practical terms, if you convert an NFA, you'll often find that there are unreachable states in the resulting DFA, which immediately shows that the result is not minimal. For a more extreme example, take any DFA with $n$ states, call it an NFA and determinize it. You now have a DFA with $2^n\>n$ states that accepts the same language as it did before, so it's certainly not minimal. (This is a particularly strong example of the first case I mentioned. All states except subsets of size $1$ will be disconnected from the start state, and the states of size $1$ are a copy of the original DFA.)

# Answer
> 0 votes
If we take NFA with n states and convert into DFA with 2^n states then there are unreachable states in resulting DFA which gives the result as not a minimal DFA.so the NFA to DFA conversion thus not give the result ad minimal DFA.

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


title: DFA and equivalence relation

text:
# Question
Title: DFA and equivalence relation
I was studying Theory of Computation and I'm kind of lost in solving this problem.

> Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q\_1Rq\_2$ if $\delta(q\_1,a)=\delta(q\_2,a)$ for some $a\in\Sigma$.

> Is $R$ an equivalence relation? Prove.

So to prove that $R$ is an equivalence relation, I have to show that

* $R$ is reflexive
* $R$ is symmetric
* $R$ is transitive

But since it's related to DFA, I'm not sure how to approach this problem. Some help is much appreciated.

# Answer
Let me spell what $R$ being an equivalence relation means:

* Reflexivity: for all $q \in Q$ there exists $a \in \Sigma$ such that $\delta(q,a) = \delta(q,a)$.
* Symmetry: for all $q\_1,q\_2 \in Q$, if there exists $a \in \Sigma$ such that $\delta(q\_1,a) = \delta(q\_2,a)$ then there exists $b \in \Sigma$ such that $\delta(q\_2,b) = \delta(q\_1,b)$.
* Transitivity: for all $q\_1,q\_2,q\_3 \in Q$, if there exist $a,b \in \Sigma$ such that $\delta(q\_1,a) = \delta(q\_2,a)$ and $\delta(q\_2,b) = \delta(q\_3,b)$ then there exists $c \in \Sigma$ such that $\delta(q\_1,c) = \delta(q\_3,c)$.

Now it's no longer about DFAs. It's about functions $\delta\colon Q\times\Sigma \to Q$.
> 3 votes

# Answer
To prove R is a equivalance relation then R must be reflexive,symmetric,transitive

1. Reflexive: for all q ∈ Q then there exists a ∈ Σ then δ(q,a)=δ(q,a).
2. Symmetric: for all q1,q2 ∈ Q, if then there exists a ∈ then δ(q1,a)=δ(q2,a) then there exists b∈Σ then δ(q2,b)=δ(q1,b). 3.Transitive: for all q1,q2,q3 ∈ Q, if then there exists a,b ∈ Σ then δ(q1,a)=δ(q2,a) and δ(q2,b)=δ(q3,b) then there exists c ∈ Σ then δ(q1,c)=δ(q3,c). hence R is Equivalance Relation.
> -1 votes

---
Tags: finite-automata
---


title: How to design algorithm

text:
# Question
Title: How to design algorithm
I am a newbie to algorithm designing. I am working on user association and load balancing algorithm designing in millimeter wave wireless communications.

In this topic I am able to formulate the problem, but my query is how does one decide the algorithm after completing problem formulation.

Any help in this regard would be highly appreciated.

# Answer
> 2 votes
You start with simple algorithms, implement them successfully, and then you learn how to do more and more complex things. You need experience, and some built-in cleverness. Without both you will fail.

This is like asking a baker "how do you come up with new cake recipes" or an inventor "how do you invent new things".

---
Tags: algorithms, algorithm-design, combinatorial-design
---


# Question
Title: Regular expression for words that have the same number of 0s and 1s or contain 00 or 11
I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I can't figure out how to solve it.

Construct a regular expression that describe the following language given the alphabet $\Sigma = \\{0, 1\\}$, $$A = \\{w \in \Sigma^ * : |w|\_0 = |w|\_1 \\}\cup \Sigma^\*\\{00,11\\}\Sigma^\*.$$

Some examples that I think might be right:

`00011` belongs to the language.
`0`does not belong to the language.
`1`does not belong to the language.
`0011` belongs to the language.
`01010101` belongs to the language.
$\lambda$ belongs to the language because $|\lambda|\_0=0$ and $|\lambda|\_1=0$.

One solution that I found so far is the regular expression:

$$\alpha = ((0 \cup 1) \Sigma^\*)^\*$$

However, to be honest, I am really not sure if this one is correct.

Could someone clarify this one?

# Answer
> 3 votes
Your $\alpha$ matches all strings, and is certainly incorrect.

The language is a union of two sets, so you can consider the two parts respectively and construct the regular expression with the form $R\_1\mid R\_2$.

The $\Sigma^\*\\{00,11\\}\Sigma^\*$ part is easy.

The $|w|\_0=|w|\_1$ part is somewhat tricky. You cannot construct a regular expression for $|w|\_0=|w|\_1$ because this language is not regular. However, You can only care about the set $S=\\{w\mid |w|\_0=|w|\_1\text{but }w\notin\Sigma^\*\\{00,11\\}\Sigma^\*\\}$ instead of the set $\\{w\mid |w|\_0=|w|\_1\\}$. Now try to figure out what $S$ looks like and write a regular expression for it. This is not hard.

# Answer
> 1 votes
The language of strings containing either 00 or 11 is clearly regular; it's easy to recognise.

The language of strings containing the same number of 0's and 1's is not even regular. But the whole problem is a trick question: The trick is that you don't need the strings containing the same number of 0's and 1's, but the same number of 0's and 1's but not containing 00 or 11.

What do the strings not containing 00 or 11 look like? Obviously there are the three strings eps, 0 and 1 which are too short. But otherwise, if your string starts with 0, the next character must be 1, then 0, then 1 and so on, and practically the same for strings starting with 1. In addition, the number of 0's and 1's must be the same if there is no 00 or 01.

So the strings are:

```
(01)*, (10)* # Same number of 0 and 1, no 00, no 11
(0|1)* (00 | 11) (0|1)* # Contains 00 or 11

```

and the regular expression is

```
(01)* | (10)* | (0|1)* (00 | 11) (0|1)*

```

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


# Question
Title: Algorithm for allocating resources; one resource per one user who accepts it
I am looking for an algorithm for the following problem:

I have a set of users and a set of books.

Every user has their own set of favorite books, which may be empty, and is a subset the set of books.

We can assume that every book is a favorite book of at least one user.

**Ideally I want to distribute ONE book to every user that has at least one favorite book.**

**A user may only receive one of its favorite books.**

Sometimes it's not possible to distribute one book to every user, because there are more users than books, or because a user has no favorite books, or due to the specific details of users, books and favorite books.

One book cannot be distributed to more than one user.

Distribution A is better than distribution B if A distributes more books than B.

An "acceptable distribution" is one that follows the rules above, and cannot be improved without reallocating a book, i.e. taking a book away from a user that already got a book.

An "optimal distribution" is an acceptable distribution that distributes a maximum number of books.

I do not have a formal analysis whether this problem can be accurately solved in a polynomial time. So maybe the best polynomial-time alternative there is out there is something such as a probabilistic algorithm.

Ideally I would like to have a polynomial-time algorithm that would always find an optimal distribution.

If it's not possible to have such an algorithm, then I would like to have an alternative polynomial-time algorithm that would find an acceptable distribution that in high probability is quite close to an optimal distribution.

# Answer
Create a bipartite graph $G = (B+U, E)$, where $B$ is the set of books and $U$ is the set of users. The set $E$ contains an edge $(b,u)$ for every pair $(b,u) \in B \times U$ such that $b$ is one of the favorite books of $u$.

To find an optimal solution, you just need to find a maximum cardinality matching of $G$.

A way to do this is to modify $G$ as follows: direct the edges of $G$ towards $B$, add two new vertices $s,t$, add all edges $(s,b)$ for $b \in B$, and finally add all edges $(u,t)$ for $u \in U$. Now you can find a maximum flow $f$ between $s$ and $t$ using any polynomial-time algorithm and unitary edge capacities. An optimal matching contains all edges $(b,u) \in E$ such that $f(b,u)=1$.
> 1 votes

---
Tags: algorithms, sets, probabilistic-algorithms, protocols, optimal-strategy
---


# Question
Title: Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?
Assume we have a balanced binary tree.

On *each* node, we call:

```
def node_depths(root, depth):
    if not root:
        return 0
    return depth + node_depths(root.left, depth + 1) + \
      node_depths(root.right, depth + 1)

```

`node_depths` itself is O(n) time. But calling it on *each* node produces an O(nlogn) time algorithm.

Why is this? I would appreciate both/either an intuitive and a mathematical response.

# Answer
> 2 votes
It is not false that `node_depths` is $\mathcal{O}(n)$ time for a tree $T$ of size $n$, but it is imprecise.

To be more precise, `node_depths(x, d)` has a complexity $\Theta(|T\_x|)$ where $T\_x$ is the subtree rooted in $x$ (can you see why?).

To prove the $\mathcal{O}(n\log n)$ bound, I will consider $T$ to be a perfect tree (it is easier that way, and the principle is the same for a balanced tree). Suppose $T$ is a perfect binary tree of size $n$ and height $h$.

* there is $1$ node of depth $0$, its subtree is of size $n$;
* there are $2$ nodes of depth $1$, their subtrees are of size $\frac{n}2$;
* there are $4$ nodes of depth $2$, their subtrees are of size $\frac{n}4$;
*
* for $k\leqslant h$, there are $2^k$ nodes of depth $k$, their subtrees are of size $\frac{n}{2^k}$.

The total size of the subtrees is then: $$\sum\limits\_{k=0}^h 2^k \times \frac{n}{2^k} = n\times (h+1) \in \mathcal{O}(n\log n)$$

---
Tags: time-complexity, trees
---


# Question
Title: Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)
Exercise 3.4.9 of *The Dragon Book* defines *Fibonacci strings* as follows:

> 1. $s\_1 = b$.
> 2. $s\_2 = a$.
> 3. $s\_k = s\_{k-1}s\_{k-2}$ for $k\>2$.

Part (d) then poses the following question:

> Show that the failure function of $s\_n$ can be expressed by $f(1) = f(2) = 0$, and for $2 \< j \le |s\_n|$, $f(j)$ is $j - |s\_{k-1}|$ where $k$ is the largest integer such that $|s\_k| \le j + 1$.

For avoidance of doubt, the *failure function $f$* of a string $b\_1b\_2\ldots{}b\_n$ is defined for integer values $i$ satisfying $1 \le i \le n$ in order that $b\_1b\_2\ldots{}b\_{f(i)}$ is the longest proper prefix of $b\_1b\_2\ldots{}b\_i$ that is also a suffix of the latter. Thus $f(i)$ is the length of the longest proper prefix of $b\_1b\_2\ldots{}b\_i$ that is a suffix of $b\_1b\_2\ldots{}b\_i$ also.

I have struggled for a long time and cannot see how to solve this question: can anyone explain this? I can see that the failure function of $s\_{n-1}$ will be identical with that of $s\_n$ until $j \> |s\_{n-1}|$ but beyond this I have not managed.

# Answer
It is easy to use straightforward induction to prove the following two claims.

**Claim One**: $s\_n$ starts with $s\_k$ for $2\le k\le n$. In particular, $s\_n$ starts with $ab$ for $n\ge3$.

**Claim Two**: $s\_k$ ends with either $ab$ when $k$ is odd or $ba$ when $k$ is even for $k\ge3$.

---

**Claim Three**: $s\_ks\_{k-1}$ and $s\_{k-1}s\_k$ are the same except the last two letters, which are either $ab$ or $ba$ for $k\ge2$.

Proof: For $k=2$, $s\_2s\_1=ab$ and $s\_1s\_2=ba$ are the same except the last two letters, which are either $ab$ or $ba$.

Suppose $k\ge3$.
$s\_ks\_{k-1}=(s\_{k-1}s\_{k-2})s\_{k-1}=s\_{k-1}(s\_{k-2}s\_{k-1}).$
$s\_{k-1}s\_k=s\_{k-1}(s\_{k-1}s\_{k-2})$
Thanks to induction hypothesis that says $s\_{k-2}s\_{k-1}$ and $s\_{k-1}s\_{k-2}$ are the same except the last two letters, which are either $ab$ and $ba$, so are $s\_ks\_{k-1}$ and $s\_{k-1}s\_k$.

---

**Claim Four**: Let $f$ be the failure function of $s\_n$, $n\ge3$. Then $f(1)=f(2)=0$ and for $2\lt|s\_k|-1\le j\le \min(|s\_n|, |s\_{k+1}|-2)$, we have $f(j)=j-|s\_{k-1}|$.

Note that Claim Four is Exercise 3.4.9 stated in a slightly different way.

Proof: WLOG, suppose $n$ is large enough, thanks to Claim One.
$f(1)=0$ by definition.
Since $s\_n$ starts with $ab$, $f(2)=0$.

Let $w\[i\]$ mean the $i$-th letter of string $w$, i.e., $w$ is the sequence $w\[1\]$, $w\[2\]$, $\cdots$, $w\[\text{length of }w\]$.

Let $1\le x\le |s\_{k+1}|-|s\_{k-1}|=|s\_{k-1}| + |s\_{k-2}|$.
Since $s\_n = s\_k\cdots =s\_{k-1}s\_{k-2}\cdots$, we have $s\_n\[x\] = (s\_{k-1}s\_{k-2})\[x\]$.
Since $s\_n= s\_{k+1}\cdots = s\_ks\_{k-1}\cdots=(s\_{k-1}s\_{k-2})s\_{k-1}\cdots=s\_{k-1}(s\_{k-2}s\_{k-1})\cdots$, we have $s\_n\[|s\_{k-1}|+x\]=(s\_{k-2}s\_{k-1})\[x\]$.

Thanks to Claim Three, we have $s\_n\[x\] = s\_n\[|s\_{k-1}|+x\]$ if $x\le|s\_{k-1}| + |s\_{k-2}|-2$, which implies $f(j)\ge j-|s\_{k-1}|$ for $|s\_k|-1\le j\le |s\_{k+1}|-2$.

Now we can apply the standard algorithm that builds this failure function $f$ of KMP algorithm, where the base cases are easy and the length of match $f(j)$ always increases by $1$ when $j$ increases by $1$, unless at the time when $j$ increases to $|s\_{k+1}|-1$ for some $k$, as shown above.

At that time when $j$ increases to $|s\_{k+1}|-1$, $f(\cdot)$ does not increase by $1$ since $$\begin{aligned} s\_n\[j-|s\_{k-1}|\]&=(s\_{k-1}s\_{k-2})\[j-|s\_{k-1}|\]\\ &\not=(s\_{k-2}s\_{k-1})\[j-|s\_{k-1}|\]\\ &= s\_n\[(j-|s\_{k-1}|)+ |s\_{k-1}|\]\\ &=s\_n\[j\], \end{aligned}$$ where the inequality comes from Claim Two as $j-|s\_{k-1}|=|s\_{k-2}s\_{k-1}|-1$.

Hence, by the nature of the failing function, the most $f(j)$ could be is $f(f(j-1))+1$. Thanks to the induction hypothesis, $$f(f(j-1))+1=f(|s\_k|-2|)+1= |s\_{k-1}|-1=j-|s\_k|.$$ Since $|s\_{k+1}|-1\le j\le |s\_{k+2}|-2$, we have proved above that $f(j)\ge j-|s\_k|$. Hence $f(j)=|s\_{k-1}|-1=j-|s\_{k}|$ as wanted. $\quad\checkmark$.
> 1 votes

---
Tags: compilers, strings, exact-string-matching
---


# Question
Title: What is Turing's main argument in "Computing Machinery and Intelligence"?
I read Alan Turing's paper "Computing Machinery and Intelligence" a few times and it isn't clear what exactly is he arguing for. He proposes the imitation game, but doesn't form a concrete conclusion.

It seems like the current consensus is that passing the Turing test doesn't signify human-like intelligence or thinking. It is merely a metric that's easy to measure. Human-like intelligence must necessarily pass the Turing test, but the reverse isn't true.

My understanding is that the Turing test is like the digit recognition test in computer vision. It is an useful metric, but getting 100% on the digit recognition doesn't mean that a computer has human-like vision.

1. Is Turing arguing that it's possible for a machine to pass the Turing test? Isn't it easily conceivable that a machine could contain every possible question and every possible response? In which case, it could simply look up the appropriate response for any given question, without having to "think" at all. This machine would easily pass the Turing test.
2. Is Turing arguing that passing the Turing test signifies intelligence or thinking? My example above illustrates a machine that could pass the Turing test, but we wouldn't consider it intelligent or thinking.
3. Is Turing arguing that the passing the Turing test is merely an arbitrary metric that is easily measurable, since intelligence is too hard to measure? In this case, why is he responding to the objections? E.g. he brings up a theological objection, but that's not relevant if the Turing test is merely measuring Turing's arbitrary metric.

# Answer
> 4 votes
As I see it, the paper is not trying to do any of that. The introduction is explicit: instead of trying to definitely answer the question "Can machines think?", it suggests an alternative question we can ask that can be specified much more precisely. "Can machines think?" is vague and open to many possible interpretations; in contrast, the paper proposes a question that is less ambiguous.

(Implicitly, the implication is presumably that this shift of perspective might be interesting and help us think more clearly about the topic. But it's up to each reader to form their own opinion about whether they find this interesting or useful in clarifying their thinking.)

This purpose is explained in clear and direct terms in the essay, particularly in the first paragraph of the essay as well as the second section of the paper.

To answer your specific questions, here is how I read the paper:

1. No, the paper is not trying to definitively answer the question of whether it is possible for a machine to pass the Turing test. Rather, the paper is suggesting that the *question* "Can a machine pass the Turing test?" is an interesting question, worthy of our attention.

Think of this like a scientific paper that *proposes an experiment* -- it's not necessarily trying to persuade anyone about what the result of the experiment will be, but rather suggesting that the experiment would be an interesting one to carry out or to consider. That can be a useful, even ground-breaking, contribution.
2. No, the paper is not arguing that passing the Turing test necessarily signifies intelligence or thinking. As far as I can tell, it doesn't take an explicit position on that.

We could imagine that one position that is compatible with the essay would be to say "I'm not confident I could define exactly what counts as intelligence or thinking -- that seems hard to define -- but whatever the answer is, passing the Turing test seems like it would be a significant milestone." We could also imagine that another position that seems compatible with the essay would be "Yes, according to the way I personally define intelligence and thinking, passing the Turing test would signify intelligence and thinking."
3. No, I think it's pretty clear that Turing is not claiming that the metric is purely arbitrary. On the contrary, the essay tries to argue that investigating this metric is worthy of our time. See, e.g., section 2, which begins with "The new problem has the advantage of...." You might find this argument persuasive, or you might not -- you might find the paper's proposal worthy of our time, or you might not -- you might find the paper's proposal arbitrary -- but I don't think it's fair to say that *Turing* thought the question was arbitrary.

These are my personal opinions and interpretations of the paper. Others might vary.

Note that I've answered the question "What is the essay arguing?" I haven't tried to tackle the question "What did Turing think?" since it can be hard to know what someone is thinking, and it's easier to grapple with the intellectual ideas as expressed in a particular paper.

Separately, one might ask "What do many computer scientists think?" or "What views have many computer scientists taken away, after reading the paper and thinking about the subject?" or "How has this paper influenced the perspective of many computer scientists?" That's a separate question, with different answers, and potentially a bit more subjective. For instance, you might find that many computer scientists have formed the opinion that the Turing test is possibly the best way we have to formalize the informal question "Can machines think?" into something answerable in a scientific way, and that many computer scientists think that at least in principle it should be possible for machines to think, if we can surmount the engineering challenges (see the Church-Turing hypothesis).

You might also be interested in reading Human computing power: Can humans decide the halting problem on Turing Machines? and Would creating a complete computer simulation of the human brain prove the Church-Turing thesis? and https://philosophy.stackexchange.com/q/15460.

# Answer
> 0 votes
Extending the @D.W. answer, the approach to solve the imitation game will enlighten us on what intelligence is, or isn't. The experiment proposes a clear and objective way to progressing in solving intelligence, many previous researchers proposed tests to intelligence but when we solved those test we had no meaningful progress on understand intelligence.

Today we are closer from solving the imitation game, and by the process of solving it, we progressed in many aspects of understanding what is intelligence. The LaMDA model bring us the question, how do we know that a human brain is not "simply look up the appropriate response for any given question" given his bias in the same way as machines does? We had an immaculate view of the human brain, but now that we progressed in the Turing test we start to see the brain and "thinking" as a "less special" entity.

Summarizing: Turing test provided a clear path for progressing in AI development and with an objective experiment of what is "thinking" we could no longer say that "thinking" has some "special value" because we are almost perfectly mimicking it with machines.

---
Tags: artificial-intelligence, turing-test
---


title: Show that ALL DFA is decidable

text:
# Question
Title: Show that ALL DFA is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\text{ALL}\_{\text{DFA}} =\\{\langle A\rangle \mid A\text{ is a DFA and }L(A)=\text{Σ\*}\\}$$ prove that $\text{ALL}\_{\text{DFA}}$ is decidable.

The following is my solution:

```
On input <A>:
1. Build a DFA D such that L(D)=Σ*
2. Execute EQ DFA on <A, D>
3. Return the output

```

Can this be considered a valid solution?

# Answer
Your approach to the answer is absolutely correct. But you can make it in linear run time. steps: 1.First check for the unreachable final states and remove them. 2.from now you can solve from your approach.
> 0 votes

# Answer
Yes, it is a valid solution. Note that it is sufficient to check whether $L(D)\subseteq L(A)$. Also, note that since you can take D to be an accepting-sink, $q\_{acc}$, then checking language containment by checking whether the product $\\{q\_{acc}\\}\times A$ has a reachable state of the form $(q\_{acc}, s)$, where $s$ is rejecting, is essentially the same as checking if there is a reachable rejecting state in $A$. So this should give you a hint that there is no need to reduce your problem to language containment, as pointed out by others.
> 0 votes

---
Tags: turing-machines, computability, regular-languages, decidability
---


title: Complexity of DFS : O(m)

text:
# Question
Title: Complexity of DFS : O(m)
We say that dfs runs in $O(n+m)$ . For any connected graph $m \geq n-1 $. Therefore : $$m \geq n-1 \implies O(n+m) = O(m)$$

Do you agree ? Because, I have seen in many algorithms proofs this bound $O(n+m)$ but most of the times we are dealing with connected graphs .

# Answer
That's true for an undirected connected graph, but:

* sometimes, the undirected graph isn't connected;
* sometimes, it's a directed graph, and not all vertices are reachable from the starting vertex.

So $\mathcal{O}(n + m)$ (assuming $n = |V|$ and $m = |E|$ for a graph $G = (V, E)$) is always right, whereas $\mathcal{O}(m)$ is sometimes wrong.
> 4 votes

---
Tags: algorithms, complexity-theory, graphs
---


title: Turing machine with infinite states

text:
# Question
Title: Turing machine with infinite states
I want to ask about a turing-machine-like construct with an infinite number of states. in this post the claim is that every language is accepted: Can a Turing machine have infinite states?

I understand that we can scan over the input from left to right once, and end up at a unique state for each possible input string. but what if the language is a description like HALT' = {\< M,w \>|M don't halt on w}, can we know what input in our language? how can we know the encodes that not in our language? how can we know M wont halt on w in the first place?

In addition, can we decide any language with such a machine or just accept any language? for example can we decide HALT = {\< M,w \>|M halt on w} ?

# Answer
You can decide any language in linear time. Given a language $L \subseteq \Sigma^\*$, consider the following Turing machine:

* Create a state for every word $w \in \Sigma^\*$ and pick the tape alphabet $\Gamma$ as $\Sigma \cup \\{ \bot \\}$, where $\bot$ denotes the blank symbol. The initial state is $\varepsilon$.
* When you read an alphabet symbol $\alpha \in \Sigma$ transition from the current state $w$ to $w\alpha$ and move right.
* When you are in a state $w$ and you read $\bot$ move to an accepting state if $w \in L$ and to a rejecting state otherwise.
> 2 votes

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


# Question
Title: Efficiently sorting a list of integers depending on the index of said integers in a second list
**Introduction**

Hi everyone,

I am currently pondering how to efficiently design an algorithm for a sorting problem and hope that someone here may help me out a bit.

**The problem**

I have two lists of integers, let's call them the 'input' list and the 'position' list, and want to sort the 'input' list based on the position of each 'integer' in the position list. Which algorithm could I use to achieve this in the most efficient manner possible?

**Assumptions**

This Question assumes the following:

* accessing a list element by index and/or calculating the length of a list is possible in `O(1)`.
* the input list has `k` elements and the position list `n` elements. Both lists contain each element at most once, but may contain elements not in the other list. `n` will usually be greater than `k`.
* The behavior for elements present in the input list but not the position list is not important, but must be consistent (e.g. all sorted to the start). Discarding the integers not present in the other list is acceptable, but suboptimal. Integers present in the position list but not in the input list must be ignored.
* the input list is sorted by the integers themselves (lowest integer first), the position list is sorted by an unknown criteria
* 'efficiency' refers to both runtime complexity and memory complexity, but runtime complexity is more important

**Example of the problem**

Here is an example of the problem I am trying to solve:

```
input_list = [1, 3, 5, 7, 11, 13]  # the list to sort
position_list = [5, 6, 7, 1, 11, 12, 13, 3]  # the order of elements
sorted_list = sort_by_position(input_list, position_list)
print(sorted_list)
[5, 7, 1, 11, 13, 3]

```

**Potential solutions**

So far I've identified the following solutions:

* Simply using a regular sorting algorithm (e.g. merge sort, quick sort, ...), using a simple linear (`O(n)`) algorithm to determine the position of each element in the position list as comparison key. Even using the merge sort sorting methods this would be `O(k * log(k) * n)` at best.
* Iterating over the position list and utilizing binary search on the input list to determine presence of the elements in the input list, inserting each found element one after another. This could achieve `O(n * log(k))`, which is better.

I believe that there is probably potential for improvement here and would appreciate your help.

# Answer
> 0 votes
**Small input\_list:**

```
h = {}
for x in input_list:
    h[x] = 1
for x in position_list:
    if h[x] == 1:
        yield x
        h[x]=2

```

Note I'm not using exact python syntax, "if h\[x\]==1" should handle the case where "x not in h" but you get the idea. Now, let's do elements present in the input list but not the position list, these still have h\[x\] set to 1:

```
for x in input_list:
    if h[x] == 1:
        yield x

```

This places the input-only elements at the end of the result. To place them at the beginning, the result array needs to be moved in memory since the number of these elements is only known at the end. If there are no duplicates, a set could be used:

```
h = set()
for x in input_list:
    h.add(x)
for x in position_list:
    if x in h:
        yield x
        h.remove(x)

```

Variant: instead of a hashtable, binary search can be used on the input list since it is sorted. This will use less memory.

* Build zeroed byte array or bitmap b\[ len(input\_list) \]
* For x in position\_list, binary-search in input\_list. If found at position pos, set b\[pos\]=1 and output x.
* Iterate input\_list, if h\[pos\]=0, it means x has not been found in the position\_list, so output x

This version may also be faster, depending on what fit in cache. The second step of outputting the values not found in position\_list is also faster, so if there is a large proportion of those, it could beat the previous version.

If the ints are densely packed and the bounds are known, an array or bitmap can be used instead of a hash.

It only reads position\_list once sequentially, and ignores elements not present in input\_list. Hashtable size depends on input\_list only. So it allows an unlimited size of position\_list, but the size of input\_list is limited by fast memory for the hashtable.

**Small position\_list**

If position\_list is much shorter than input\_list, then building a hash/bitmap of the whole input list is a waste of time.

* Create a hashtable pos\[x\] which contains the position of integer x in position\_list
* Create an zeroed array out\[\] of the same length as position\_list
* for x in input\_array, if pos\[x\] exists, set out\[pos\[x\]\]=1. Else, output x.
* scan out\[\] and output the ints in order of position

This puts the input-only elements first in the output. It reads the input once, so if the position list fits in memory, there is no limit to the size of input\_list.

**Large input and position lists**

By large, I mean it doesn't fit in a practical amount of fast RAM, so hashtables and algos relying on random access are out. This is basically a huge database join, so the same strategies apply, for example:

* Scan position\_list and create a table t1 (x,pos)
* disk-sort t1 on x (for example block qsort + merge)
* Merge join with input\_list which is already sorted on x
* If x is present in input\_list but not in position\_list, output it. Otherwise, insert (x,pos) another table t2
* Sort t2 on pos
* output x values from t2

---
Tags: algorithms, sorting, efficiency, lists
---


# Question
Title: Is kernel essentially an implementation of system calls?
In essence, is kernel basically the code that implements a set of system calls?

# Answer
> 1 votes
It's probably more accurate to think of an operating system is an implementation of a virtual machine.

System calls are part of that; they are operations of the virtual machine callable by programs.

---
Tags: computer-architecture, operating-systems, os-kernel
---


title: EvoPathfinding - Stuck in local optimal

text:
# Question
Title: EvoPathfinding - Stuck in local optimal
I am using a Genetic Algorithm framework to solve a path-finding problem. Specifically, given the following 32x32 maze:

```
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                      |         X
X                      |         X
X                      |         X
X                      |     G   X
X                      |         X
X                      |         X
X                      |         X
X                      |         X
X                      |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |                       X
X        |                       X
X        |                       X
X    S   |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

I wish to reach point **G** by starting from point **S**. The fitness function that I am using here is based on the *manhattan distance* and for every individual, it goes as follows:

* if the individual crashes on a wall ('|') or an outer bound ('X') his fitness is 0
* if the individual final coordinates match point **G** his fitness is 100
* in any other case his fitness is `100 - manhattan_distance_from(G)`

The problem is, that the evolution process is halted after a maximum number of steady-state generations i.e., the fitness of the generated individuals is saturated and cannot improve further.

The best final solutions that are refined via the evolution process are like the one below:

### Best Solution

```
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                      |         X
X                      |         X
X                      |         X
X                      |    G    X
X    ******************|         X
X    *                 |         X
X    *                 |         X
X    *                 |         X
X    *                 |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |                       X
X    *   |                       X
X    *   |                       X
X    S   |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

This is to be expected though from the standpoint of my fitness function. Because in order to overcome the wall, the algorithm has to generate and maintain individuals by worsening their fitness values since the path has to go down and so the fitness value must get worse.

While I have tried to increase the impact of the mutation operators in order to generate and maintain diverse populations in my generations I did not manage to overcome the problem of this local optimal and so I am thinking of ways to improve my fitness function.

Are there any suggestions?

# Answer
Another fitness function you could try is the following:

Consider the final point of the agent (if it crashes into a wall or outer bound, this the point where it crashed). Then use `(100 - manhattan_distance_from(G)) * penalty` as the fitness function, where penalty is 1.1 if it crashed into a wall or outer bound, and penalty is 1 if it didn't crash.
> 0 votes

---
Tags: optimization, genetic-algorithms, path
---


title: Meaning of lambda-transitions in npda

text:
# Question
Title: Meaning of lambda-transitions in npda
It is for me unclear how I can derive from a npda whether the lambda-transition means “I don’t care which symbol I read” or “I have read all the symbols”. For example, see the following automata:

If I am correct, the red ones have the first meaning, and the green one the second.

Maybe I totally misunderstood lambda-transitions in npdas?

# Answer
Usually, the first symbol means what you expect to read from the input (1), the second what is the symbol at the top of the stack (2) and the third what will happen with the stack (3).

1. $\lambda$ or $\varepsilon$ means the empty string, so this transition can be used without consuming any symbol from the input, i.e., it is a spontaneous transition over the input;
2. $\lambda$ or $\varepsilon$ means "empty stack";
3. $\lambda$ or $\varepsilon$ means pop from stack.

In your model, both red and green marked lambdas means spontaneous transition over the input, but they have a condition related to the top of the stack. In the first red, the stack must be empty. In the second the top of the stack must be `X` and in the green lambda the top of the stack must be `+` (if I'm reading that correctly).

Honestly, I have the impression that your modeling is incorrect. Can you present the language you are trying to recognize with this NPDA?
> 2 votes

---
Tags: automata, context-free, nondeterminism
---


title: how to decide this language

text:
# Question
Title: how to decide this language
My problem is to build a machine that decide this language:

{〈A, w〉| A is a DFA and w is the longest word in L(A)}

I know that DFA has finite states and eventually for every word that i simulate on A ,i would get an answer (yes/no) and know if w is in L(A).

In order to know if w is biggest can i build a TM M that Non deterministically guess a word grater than W and reject if A accept it? otherwise M accept.

# Answer
Detect whether there is a cycle in the DFA containing a state $q$ such that $q$ is reachable from the initial state and $q$ can reach a final state (this can be done by deleting all states of $A$ that do not satisfy these requirements and looking for a cycle in the resulting graph).

If the answer is affirmative then $L(A)$ is infinite and you can reject without even examining $w$.

If the answer is negative then the pumping lemma ensures that all words in $L(A)$ have length at most $n-1$, where $n$ is the number of states of $A$ (since the path traced by any word in $L(A)$ having length at least $n$ must traverse some state two or more times). Then you can explicitly test all words in $\bigcup\_{i=|w|+1}^{n-1} \Sigma^i$ (or $\bigcup\_{i=|w|}^{n-1} \Sigma^i \setminus \\{w\\}$ if you are trying to decide whether $w$ is the **unique** longest word in $L(A)$).
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Does optimal page replacement cause the same number of faults for the reverse string?
Let $P\_1P\_2...P\_k$ be a page sequence that gives $n$ page faults with the optimal page replacement algorithm. Does the page sequence $P\_kP\_{k-1}...P\_1$ give the same number of page faults. This can be proved quite easily in the case of LRU, and disproved for FIFO. Does it hold for Optimal Replacement?

# Answer
> 1 votes
If we let $S^r$ be the reverse of a reference string $S$, then the page-fault rate for the OPT algorithm on $S$ is the same as the page-fault rate for the OPT algorithm on $S^r$. Similarly, the page-fault rate for the LRU algorithm on $S$ is the same as the page-fault rate for the LRU algorithm on $S^r$. Operating Systems - Galvin

More read - here

---
Tags: operating-systems, page-replacement
---


# Question
Title: Describing the Language of a DFA with 7 States
So in my attempt to convert the following DFA into a regular expression, I ended up with `((ba)*(ab(ab)*)*(aa(ba)*a)*)*`. The exercise I'm following wants me to convert the DFA into a regular expression then describe its language in plain English, however, I can't seem to come up with anything for the converted expression. Any hints on how to go from here?

# Answer
> 2 votes
To accept a string, you must start in $q\_0$ and end in $q\_0$ or in $q\_3$.
A path from $q\_0$ to $q\_0$ can make a cycle through $q\_5$ (so you can have $(ba)^\*$) or through $q\_1,q\_2,q\_3,q\_4$ (and so $a(ba)^\*a(ba)^\*a$), and then you can put these together to obtain $((ba)^\*+a(ba)^\*a(ba)^\*a)^\*$.
A path from $q\_0$ to $q\_3$ is a path from $q\_0$ to $q\_0$ and then a path that do not pass twice through $q\_0$ from $q\_0$ to $q\_3$, i.e. $ab(ab)^\*$.

Now, we can put all together: $$((ba)^\*+a(ba)^\*a(ba)^\*a)^\*(\varepsilon+(ab)^+)$$

A description of this language in plain English could be something like this: strings of the type $((ba)^\*+a(ba)^\*a(ba)^\*a)^\*$ or $((ba)^\*+a(ba)^\*a(ba)^\*a)^\*(ab)^+$. The first type if formed by strings starting either with $a$ or $b$, with no consecutive $b$s, such that the number $a$s exceeds the number of $b$s by a multiple of 3 (0 included), and ending with $a$; the second type if formed by strings of the first type concatenated with $(ab)^+$, so with a nonempty string starting with $a$, ending with $b$ and such that no two consecutive letters are equal.

Here is the simplest description: strings without consecutive $b$s such that the number $a$s exceeds the number of $b$s by a multiple of 3 (0 included).

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