# Question
Title: Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?
Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free languages as well?

# Answer
> 5 votes
Before giving the answers, some discussion on your direction for the proof:

It is highly unlikely that a proof of this claim would use the containment $REG\subseteq CFL$, since the pumping lemma is not an exact characterization, and if a language satisfies the regular pumping lemma, it doesn't proof that the language is regular.

Thus, the proof will have to go into the "guts" of the lemmas. Now for the proof:

Consider a language $L$ that satisfies the regular pumping lemma. Thus, there exists some $p\>0$ such that for every word $w\in L$, if $|w|\>p$, then there exists a partition $w=xyz$ such that $|xy|\le p$, $|y|\>0$ and for every $i$ it holds that $xy^iz\in L$.

We want to prove that there exists some $q\>0$ such that for every word $w\in L$, if $|w|\>q$, then there exists a partition $w=uvstr$ such that $|vst|\le q$, $|vt|\>0$ and for every $i$ it holds that $uv^ist^ir\in L$.

Seeing things stated as above, the rest is just "pattern matching": Let $q=p$, and consider a word $w\in L$ such that $|w|\>q$, then there exists a partition $w=xyz$ as above. Let $u=x,v=y,s=\epsilon,t=\epsilon$, and $r=z$. Clearly $uvstr=xyz=w$. Also, $|xy|\le p$, so $|vst|=|y|\le p$ and $|y|\>0$ so $|vt|=|v|=|y|\>0$. Finally, for every $i$ it holds that $$uv^ist^ir=xy^iz\in L$$ and we are done.

---
Tags: formal-languages, context-free, regular-languages, pumping-lemma
---


# Question
Title: How can a set offer better search performance than an array
While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "**Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership.**"

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of ***O*(n)**.

Am I missing something or is this just an incomplete statement?

# Answer
I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order. Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.
> 2 votes

---
Tags: data-structures, efficiency, arrays, sets, dictionaries
---


# Question
Title: Shortest Path problem(Single Source&Destination)
Given: A completely connected directed acyclic graph.

What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes?

Constraint:
1)The result should be optimal.
2) The cost between any two connected nodes is computed in time complexity of O(layer-no). For, e.g., if we consider the graph to be layered(Since its a DAG) then the cost between Layer 'K-1' & 'K' can be computed in a time complexity of O(K)

Known Solutions:
1) A\* - But heavily dependent on the heuristic function
2) Dynamic programming - requires to compute the cost of path for all possible path.

So, Is there any way to compute it more efficiently or with similar time complexity?

# Answer
Your goals are not achievable.

You want the running time to be $O(K)$, where $K$ is the number of layers (or the distance from the source to the destination, I'm not sure which). However, this running time is not achievable. Suppose we have only a handful of layers, but millions of vertices in each layer: say, $K$ layers, but $N/K$ vertices per layer, where $K$ is small and $N$ is large). Then there is no way to get a running time of $O(K)$, because any solution will have to look at every vertex in each of those layers. Therefore, the best you can hope for is a worst-case running time of $O(N)$; $O(K)$ isn't achievable.

So, there is no algorithm that will meet your constraints.

---

That's the bad news. The good news is that there *is* an algorithm that is efficient and has a running time that is asymptotically optimal. This is the standard algorithm for computing shortest paths in a DAG: you topologically sort the DAG, then visit the vertices in topologically sorted order, calling "Relax" on each edge. Any good algorithms textbook is likely to describe this algorithm.

The running time of this algorithm is linear, i.e., $O(V+E)$. One can also prove that this is the best worst-case running time one can hope for: it's not possible to do any better, in terms of asymptotic worst-case running time. So, from a theoretical perspective, the standard algorithm is excellent.

Now this doesn't rule out the possibility that clever implementation can improve the constant factors. Indeed, it is likely that careful consideration of things like the structure of your graphs and the memory hierarchy might yield speedups that are measurable in practice. But you shouldn't expect an improvement in the asymptotic running time.
> 3 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How to convert this type of languages to Context Free grammar?
As I've already asked my Question about the solving Context Free Grammar $L = \\{a^n b^m c^p \mid n = m + p + 2\\}$

Can this language be defined by a Context Free Grammar?

Now i have just changed `n = m + p - 2` and still can't figure out, Here is my attempt:

```
S -> Cc
B -> aBb | ^
C -> aCc | Bb

(In this Grammer i can't handle string like bb , cc , abbc , abcc etc)

```

How to make such type of grammars where `n = m + p - x` .Can anyone explain how to solve such kind of grammars:

$K = \\{a^n b^m c^p \mid n = m + p - 2\\}$

# Answer
> 1 votes
$K = \\{a^n b^m c^p \mid n = m + p - 2\\}$. This can be solved by observing the nesting structure (see "How to prove that a language is context-free?") and an extra trick.

Thus we have words of the form $a^{p'+m'} b^{m'}b^i c^j c^{p'}$, where $i+j=2$. We have set aside the two symbols that are not counted for $n$.

Apply nesting $S\to aSc$, $S\to Tb^i c^j$ (all 3 possibilities $i+j=2$), $T\to aTb$, $T \to \varepsilon$.

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


# Question
Title: Why is O(n log n) the best runtime there is?
I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good.

However, there are faster runtimes such as (from now on just assume it is in big o notataion), such as $1$, $n$, and $\log n$. I understand that it is almost impossible to have a algorithm in $O(1)$ as that is for trivial tasks such as adding or multiplication.

However, why is there no algorithm in $O(\log n)$ time? Mergesort is considered to be a great algorithm and in its best and worst case scenario it is $O(n \log n)$ (I could be wrong). Why is merge sort considered to be a great algorithm when $O(n \log n)$ is only faster than $n^2$, $n!$, and $2^n$?

Also, why is there no sort with a time of $\log n$? This is not a homework question by the way, I am just purely curious as to why no sorting algorithm is in $\log n$ time.

# Answer
Your confusion seems to stem from several misconceptions. I'll try to address some.

There are several ways an algorithm can be "best". Which is applicable depends on the context and on what you want to say.

* An algorithm is *provably the best one*, period. (Hint: impossible)
* An algorithm is *the best we know*. (Best in what metric?)
* An algorithm is *provably optimal*. (W.r.t. what metric? What about others? Proven under which assumptions?)
* An algorithm is *probably asymptotically optimal*. (W.r.t. what metric? What about others? Proven under which assumptions? What about the constant factor? What about small inputs?)

And probably more. Note that all these need an addition: "for problem P". Every algorithm solves some specific problem, and it does usually not make sense to compare algorithms for different problems.

Now, in the case of Mergesort, here are two facts.

* Mergesort takes $O(n \log n)$ operations to sort $n$ elements in the worst case.
* Sorting $n$ pairwise distinct elements (from an unknown range) by comparing element in a pairwise fashion requires $\Omega(n \log n)$ comparisons.

Hence, Mergesort is an *asymptotically worst-case-optimal* algorithm for *sorting pairwise distinct numbers* whose *range is unknown (or huge)*, among all *comparison-based sorting algorithms*.

However:

* On average (again, model assumptions apply), Quicksort is faster Mergesort.
* For some input classes, there are *linear-time* sorting algorithms.
* On small inputs, even Insertion Sort is faster.

As you see, Mergesort is "best" in a certain sense, but not universally.

Regarding your specific question in the end, proving an $\Omega(n)$ lower bound for general sorting is easy. Try to imagine an algorithm that *does not even look at* every input element. Can it sort the input?
> 8 votes

---
Tags: algorithms, efficiency
---


# Question
Title: How is the micro code executed within a processor?
How does the microprocessor convert the machine code to micro code? What part of the processor is at play?

# Answer
> 2 votes
The Control Unit converts machine instructions into micro-code.

There are two types of control units; Micro-programmed & Hardwired. Both work differently.

In micro-programmed control the control unit is an interpreter for the individual machine instructions. It runs in a loop interpreting instruction after instruction, generating the required micro-instructions and control & timing signals.

In hardwired control the control unit is a state machine which takes logic signals from the instruction and generates various control signals which run the hardware.

---
Tags: computer-architecture
---


# Question
Title: Push down automata what to do when there is no suitable transition
This is a question that has emerged from a recent quiz I have taken. In short

> Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the following inputs will lead the automaton to state p with the stack containing the string XXZ?

I am gonna write only the transitions from state q regardless of the input symbol:

```
 (q, 0, Z) -> (q, XZ)
 (q, 0, X) -> (q, XX)
 (q, 1, X) -> (q, X)
 (q, ε, Χ) -> (p, ε)

```

Now the thing we note here is that there is no transition from state q when there is an empty stack regardless of the input symbol. How does one answer that question assuming we start from an empty stack? I have omitted the inputs cause I don't really care about the answer to the quiz, all I want to know is how would someone start working on that?

# Answer
Starting with empty stack is not allowed.

A PDA is usually defined as (Q, Σ, Γ, δ, q0, Z0, F), where the symbols have their usual meanings. One of these is Z0, the stack start symbol. It is on the stack when the PDA starts.

So by definition you have Z0 on the stack at start. You need to find Z0 in your case and start with that.
> 3 votes

# Answer
Given the form of transitions, they cannot be applied when the stack is empty, since there is then no symbol to be read from it. Hence you cannot assume that you start with an empty stack: it would make no sense.

Actually the definition you use, that of wikipedia page on pushdown automata, uses $Z$ as initial stack symbol. Hence you should assume that at the beginning your stack contains $Z$ at its bottom.

Then any string from the regular set $0001^\*(0+1)$, for example $0001110$, can produce the desired result (non deterministically), i.e. being in state $p$ with XXZ on the pushdown stack. The fourth transition should be used last.
> 1 votes

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


title: Running time analysis of a segment tree

text:
# Question
Title: Running time analysis of a segment tree
Can someone provide an analysis of the **update** and **query** operations of a segment tree?

I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?

# Answer
> 4 votes
Those are my lecture slides, so I figured I'd chime in. :-)

The idea is to split apart the recursive calls being made into two different classes: recursive calls where the range being searched is the entire range of a node and recursive calls where the range being searched corresponds to just a part of the range. One of the observations you can make is that if you do a range search on a segment tree, after the initial split made in the recursive call, every recursive call made either spans the entire range given by a node or corresponds to a subrange that's flush up against one of the sides of the range given by a node.

As an optimization in a segment tree, any recursive call that's made for a range that completely spans a node doesn't do any further recursion; it just returns the cached value and stops. Therefore, the only recursive calls that fire off more recursive calls are ones where the range searched is flush against the side of the range spanned by a node. If you look at what happens in that case, you'll see that every recursive call made from that point either is over a full range (in which case it doesn't really count as a recursive call; we can charge that work back to the initial recursive call) or is to a flush against the side range. This means that while the recursion does indeed branch, one of those branches always immediately ends. Therefore, the work done obeys the recurrence

> T(n) = T(n / 2) + O(1)

where that O(1) term counts both the work for the recursive call and the (up to) one recursive call made on a full range, which terminates immediately. That solves to O(log n), as required.

Hope this helps!

---
Tags: data-structures, runtime-analysis, computational-geometry, binary-trees, search-trees
---


# Question
Title: Symmetric Difference of Turing Recognizable and Finite Languages
Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable.

My reasoning: B is finite, therefore the finite number of strings can be put through a DTM , M, such that L(M)= A. If M accepts, then remove that string from B and put it in a list, R. * Otherwise, leave it in B. The DTM for the symmetric difference just checks if it is either in B, which it accepts, R which it rejects or if M accepts.

I feel like I have simplified this somewhere, but I would appreciate any pointer in the right direction.

I am unsure how to determine the strings in both A and B. The way I have done it (above) would run forever, because if it is not in A and is in B, it would never halt. This would result in never getting past the * above.

How can it be determined if a string is in A and B?

# Answer
The symmetric difference $A\ominus B$ of a Turing Recognizable Language $A$ and a finite language $B$ is Turing Recognizable (i.e. recursively enumerable, or RE).

What you must do is prove that there is a Turing machine that recognizes $A\ominus B$, but you do not have to actually construct the machine. And that is very fortunate because, in general, you cannot.
<sub>\[More precisely you can build that machine, but you will have in general no way to know it is the right one, as explained below.\]</sub>

This is a sketch of the proof, which you should know how to complete.

First you prove that the union of a RE set $C$ and a finite set $D$ is a RE set $C\cup D$ (i.e. a Turing recongnizable set). That is pretty easy.

Then you prove that subtracting a finite set $D$ from a RE set $C$ produces a RE set $C\setminus D$. That is easily done by modifying the Turing machine that recognizes the RE set.

> You simply modify the Turing machine recognizing $C$ so that it loops or reject when the input is an element of $D$

Now consider the finite set $B$. It can be split into two parts:

* $B\_1=B\setminus A$ containg all elements of $B$ that are not in $A$,
* $B\_2=B\cap A$, the intersection of $A$ and $B$.

Since $B$ is finite, both $B\_1$ and $B\_2$ are finite too.

It is easy to show that the symmetric difference is

$A\ominus B= (A\setminus B\_2)\cup B\_1$

Since we have shown that RE sets are closed under union with a finite set, and under subtraction of a finite set, the set $A\ominus B$ is also RE, i.e. Turing recognizable.

Thus there is a Turing machine that recognizes $A\ominus B$, but this proof does not tell you which. The reason is that there is no general way to determine what part of $B$ is the set $B\_2$.

Actually you could construct $2^{|B|}$ Turing machines, each corresponding to one possibility for the set $B\_2$ as subset of $B$. One of these Turing machines is the one you want. But there is no general procedure to determine which.

This kind of proof is called non constructive, because you can prove that an answer exists (i.e. the recognizer for the symmetric difference), but you cannot actually tell what it is.
> 4 votes

---
Tags: formal-languages, computability, closure-properties, semi-decidability
---


title: DTM that halts on a minimum one input

text:
# Question
Title: DTM that halts on a minimum one input
I am trying to show that this is Turing Recognizable.

The language A, that is a DTM, T, that halts on a minimum of one input.

My justification is that of course it is because, you just need to check if an accept state is reachable. However, this seems like I am making it trivial.

Is there something larger I am missing?

EDIT: New Idea

Let M be a DTM that does this:

For every string w in the language, simulate w on T. if it halts, accept.

The only problem I see with this, is if a string causes it to loop forever, then it will never try the others.

# Answer
Hint: Use the technique of dovetailing, mentioned in several of the comments. The idea is to maintain a growing list of simulated Turing machines, all of them copies $T\_1,T\_2,\ldots$ of the input Turing machine $T$, operating as follows:

1. Initialize $T\_1$ with the $1$st possible input, and run $T\_1$ for one step.
2. Initialize $T\_2$ with the $2$nd possible input, and run $T\_1$ and $T\_2$ for one step each.
3. Initialize $T\_3$ with the $3$rd possible input, and run $T\_1,T\_2,T\_3$ for one step each.
4. And so on.

You get the idea. It is perhaps not obvious how to maintain the states of several Turing machines at once, but you can figure it out on your own.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How do I see SSL/TLS packet data in clear?
Hey all I have a weird question (first time poster so forgive me if this is super newb)...

I am wanting to see the inner workings of a SSL/TLS connection between a client and a server at the packet level (in the clear) in order to learn. Is there a way to do this where I will see all of the traffic including the handshake?

Should I just setup a webserver that uses SSL/TLS and then use ssl strip & tcpdump to grab the packet capture? Will that even work in order to grab the full connection in the clear?

I am not super familiar with the SSL/TLS stack and I would like to do this in order to learn how it works at a lower level.

# Answer
Sure. Yes, you can capture the packets and view them. That'll work. It's a useful, informative exercise.

You can use Wireshark (or some other packet capture tool) to capture the packets involved in the TLS handshake and view the captured packets. It'll show you the raw bytes, and also decode the handshake messages for you. Wireshark has a nice GUI that might make it easier to use, so I recommend that as your first choice, if you haven't done anything like this before.

I don't see any reason why you'd use SSL strip.
> 1 votes

---
Tags: network-analysis
---


# Question
Title: Algorithms for minimizing Moore automata
Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times of these algorithms if any?

# Answer
**The original DFA minimization algorithm was actually designed for Moore Machines**, guided by their apparently more observable behavior. But the algorithm presented here is a reconstruction from the DFA minimization, since I discovered the historical evidence after the fact.

After Wikipedia (with some notational changes):

> A Moore machine can be defined as a 6-tuple $(Q, q\_0, \Sigma, \Pi, \delta, \gamma)$ consisting of the following:
>
> * a finite set of states $Q$
> * a start state (also called initial state) $q\_0$ which is an element of $Q$
> * a finite set called the input alphabet $\Sigma$
> * a finite set called the output alphabet $\Lambda$
> * a transition function $\delta : Q \times \Sigma \rightarrow Q$ mapping a state and the input alphabet to the next state
> * an output function $\gamma : Q \rightarrow \Pi$ mapping each state to the output alphabet

From this definition, a Moore machine is a deterministic finite state transducer.

I have no reference for minimization of Moore automata. However it seems not too hard to imagine an algorithm, derived from the algorithm used for deterministic finite state automata.

The idea in DFA minimization is based on the Myhill-Nerode characterization of regular languages.

> Given a language $L$, and a pair of strings $x$ and $y$, define a distinguishing extension to be a string $z$ such that exactly one of the two strings $xz$ and $yz$ belongs to $L$. Define a relation $R\_L$ on strings by the rule that $x R\_L y$ iff there is no distinguishing extension for $x$ and $y$. It is easy to show that $R\_L$ is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.
>
> The Myhill-Nerode theorem states that $L$ is regular if and only if $R\_L$ has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing $L$ is equal to the number of equivalence classes in $R\_L$.

Indeed each state $q$ of the smallest DFA is such that $W\_q$ as defined above is one of the equivalence classes for the relation $R\_L$.

For a non-minimal DFA for the regular language $L$, it is easy to show that each set $W\_q$ contains strings that all belong to a same equivalent class with respect to $R\_L$.

Hence, the minimization of the DFA actually consists of merging states (considered as sets of equivalent strings), whenever it is shown that two distinct states contain equivalent strings.

Two reasonably fast algorithms exists for that purpose, Moore algorithm (1956) which is in time $O(n^2)$ and Hopcroft's algorithm (1971) in time $O(n\log n)$.

The extension to Moore automata is best understood in redefining the equivalence relation as $R\_T$ for a transducer $T$. The relation $R\_L$ was concerned with whether future input would lead equivalently to an accepting state. The $R\_T$ equivalence relation of Moore automata is concerned with whether future input will produce the same output.

Hence, given a transducer $T$, and two strings $x$ and $y$, we define a distinguishing extension to be a string $z$ such that $T(xz)=T(x)u$ and $T(yz)=T(y)v$ with $u\neq v$, i.e. such that the output behaviour of the transducer differs for $z$ depending on whther it is following $x$ or $y$.

Again, $R\_T$ is an equivalence relation, dividing all strings in $\Sigma^\*$ into equivalence classes. In the case of a Moore machine, these classes will again correspond to state of the minimal transducer.

**The following algorithm mimics the Moore algorithm for DFA minimisation.**

We define an initial partition $\mathcal P$ of $Q$ into classes of states $S\_e$ as follow:

$\forall e\in\Pi:\\; S\_e=\\{q\in Q\mid \gamma(q)=e\\}$

Then we split the classes in $\mathcal P$ as follows:

**repeat** successively for each class of states $S$, until none changes
$\ \ $ **repeat** $\forall a\in\Sigma,\\;$
$\ \ \ \ $ **If** $ \exists S'\in \mathcal P,\\; \forall q\in S,\\; \delta(q,a)\in S'$ **then** do nothing
$\ \ \ \ $ **else** split $S$ into subsets $S\_i$ such that
$\ \ \ \ \ \ $ for each subset $S\_i$, there is a different class $S'\in \mathcal P$ such that $ \forall q\in S\_i,\\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $ (the subsets $S\_i$ replace $S$ in $\mathcal P$)

When there is no class left that needs to be split, the remaining classes of states will form the states of the minimal Moore machine.

By construction, all states in a class have the same output which is the output for the class.

Similarly, for any input $a\in\Sigma$, all states in a class go to some state in the same other class, which defines the transition function for the minimal Moore machine.

**Complexity analysis:** Let $n=|Q|$ be the number of states, and $s=|\Sigma|$ the size of the input alphabet.
The main loop is executed at most $n$ times, since each iteration must split at least one class of states, and each class contains at least one state. Each iteration of the loop examines each state a finite number of times, and in proportion to the number of input symbols. Hence the complexity of the algorithm is $O(sn^2)$, the same as that of the DFA minimization algorithm that served as a guideline for this one.

I do not have any reference for this minimization of Moore machines. Possibly it is included in his paper:

> Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". *Automata Studies*, Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press) (34): 129-153.

This paper is the main reference introducing Moore Machines. It is also the reference for Moore's DFA minimization algorithm. It should thus be surprising if the adaptation of the algorithm to the minimization of Moore Machines were not at least suggested in that paper. I did check the paper, and the version of the minimization algorithm that is presented is actually for Moore machines, not for DFA. The paper is well written, but the style of the time makes it a bit harder to read. It is interesting to see that many of the ideas of the Myhill-Nerode theory of Finite State Machines are already sketched in this paper.

The more recent $O(sn\log n)$ algorithm due to John Hopcroft (1971) should be similarly adaptable to Moore machines. It is not clear that there was any reason to publish this adaptation anywhere, and the Hopcroft paper seems to have no reference to Moore machines.
> 6 votes

# Answer
A version of Brzozowski's algorithm using derivatives of regular expressions is given in \[2\], Chapter 12, Section 4, where it is credited to \[4\]. See \[1\] and \[3\] for the more general case of subsequential transducers (the terminology is a bit outdated and the term *sequential transducer* is probably more appropriate nowadays).

\[1\] C. Choffrut, Minimizing subsequential transducers: a survey, *Theoret. Comp. Sci.* **292** (2003), 131–143.

\[2\] S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974.

\[3\] J.-E. Pin, A tutorial on sequential functions. (Slides)

\[4\] G. N. Raney, Sequential functions, *JACM* **5** (1958), 177–180.
> 2 votes

# Answer
Brzozowski's algorithm is a bad starting point (if you are concerned with asymptotic worst-case runtime). Even Wikipedia tells you as much:

> As Brzozowski (1963) observed, reversing the edges of a DFA produces a non-deterministic finite automaton (NFA) for the reversal of the original language, and converting this NFA to a DFA using the standard powerset construction (constructing only the reachable states of the converted DFA) leads to a minimal DFA for the same reversed language. Repeating this reversal operation a second time produces a minimal DFA for the original language. The worst-case complexity of Brzozowski's algorithm is exponential, as there are regular languages for which the minimal DFA of the reversal is exponentially larger than the minimal DFA of the language,\[6\] but it frequently performs better than this worst case would suggest.

The algorithm has exponential worst-case runtime *even on DFA* because it computes an automaton for the reverse, which may have to be exponentially large. So your problem does not come from the extension to transducers.

Try to adapt another DFA-minimisation algorithm.
> 1 votes

---
Tags: reference-request, automata, optimization, finite-automata, transducers
---


# Question
Title: Combinatorial optimization - is there a formal name for this problem?
I am looking for a formal name and an algorithmic approach to the following problem.

Given is a set of services each coming with a price:

* {s1, 300}
* {s2, 400}
* {s3, 800}

Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:

* {p1, {s1, s2}, 600}
* {p2, {s2, s3}, 1050}
* {p3, {s1, s3}, 950}
* {p4, {s1, s2, s3}, 1250}

Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.

For example: Services to order :{s1,s2,s1,s3,s2,s3,s1}

possible Solutions:

* {p4, p4, s1} : 2800
* {p1, p1, p3, s3} : 2950

In this case the first solution would be the winner.

An exhaustive approach will quickly explode because it is O(n!) or even worse.

What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?

# Answer
> 1 votes
I don't know the name of your problem, if there is one.

But, concerning the complexity: The decision-version of your problem seems to be strongly NP-complete. You can easily reduce ExactCoverBy3Sets to it:

Given a ground set $X = \\{1, \ldots, 3q\\}$ and a set $\mathcal{C}$ of 3-element subsets $C\_i$ of $X$. Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ of disjoint subsets that cover $X$ ?

Assume we have $3q$ services $1,\ldots,3q$, each with a price of $q+1$. Furthermore, for each $C\_i$, we have a package of the corresponding three elements at a price of $1$. Now, given the list $1,\ldots,3q$ of services to order, there is a solution with cost at most $q$ if and only if there is a solution to the given instance of ExactCoverBy3Sets. Since there are no double orders and since "You can only use a package if you can completely fill it with services", the sets are disjoint and cover the whole ground set $X$.

So, you won't succeed in finding a polynomial (exact) algorithm or an FPTAS. However, you can search for approximation algorithms for the above problem and/or the related problems SetPacking and MinimumCover (cf. Garey/Johnson, "Computers and Intractibility", Problems SP2, SP3 and SP5).

---
Tags: optimization, combinatorics
---


# Question
Title: Formula for sufficiently lengthy encryption key?
As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many meaningful decryptions just by random chance and you won't be able to determine which was the original message.

As you add length to the message though, these meaningful decryptions become rarer until there is once again a small enough number of them left to figure out which is the right one (if you know what you're looking for, that is).

Has anybody figured out a way to estimate the required key length for this obfuscation by quantity to happen for more popular encryption algorithms?

# Answer
> 4 votes
That's not how security works. Sometimes you want to use encryption in circumstances in which there are two possible messages, and you want encryption to be secure even in these cases. That's because encryption is used as a building block in more complicated cryptographic protocols. Also, attacks could be based on multiple related (or even unrelated) messages.

Instead, security is based on the fact that *nobody* can try and decrypt a message with respect to all possible keys since there are too many, and *there is no better way of finding the key*. The second requirement is security of the cryptosystem, and currently there is no way to prove it. Instead, we use standard systems which are being researched and so far have revealed no weaknesses.

Suppose that our system is cryptographically secure. How can we guarantee that there are too many keys to try all of them? The standard approach is to agree on a key length in advance, usually 128 bits (or more). Classical (rather than quantum!) computation cannot run $2^{128}$ steps even if you parallelize it across atoms of the universe, and wait a million years. That's considered secure enough.

# Answer
> 1 votes
I very much doubt that anyone has done such an analysis. Trying every key isn't a plausible attack so it isn't worth defending against or studying its effectiveness.

Even if you can try a billion keys a second (i.e., roughly one key per clock cycle on a commodity PC), a $64$-bit key is too long to brute-force decrypt: trying all $2^{64}\approx 2\times 10^{19}$ keys would take nearly $600$ years. Every extra bit makes it take twice as long to try all the keys. In reality, keys are much longer than $64$ bits and are often hundreds or thousands of bits long. It would take many, many orders of magnitude longer than the current age of the universe to try every key.

# Answer
> 0 votes
Not quite sure I fully understand your question, but let me share some thoughts:

* Provably safe encryption requires a key of the same length `k` (in bits) as the message (`n`), with `2^n` possible keys and decryptions of the same ciphertext.
* If you take a key of length `k=n-1` instead, you'll have half as many keys and possible decryptions, and have `1` extra bit of the message to check for plausibility. Best case, you can discard half of the possible decryptions as implausible.
* If you take a key of length `k=n-2` instead, ... and so on.
* If you take a key of length `k=1`, you've got two possible decryptions, one of which is correct while the other is more or less recognizably incorrect.

The expectancy value for getting more than one plausible messages for a given key length then roughly depends on two factors:

a. `n-k`, and

b. the total number of plausible messages of length `n`.

Notice that, to detect if a decrypted message is plausible or not, there has to be redundancy in the plain text in the first place. If there were no redundancy in the plain text, it would be indistinguishable from pure random content. This redundancy may exist inside the message, like it is given in any natural language text for example, or it may exist outside of the message itself which is the case in the more general known plaintext attacks.

However, measuring the number of plausible messages may prove to be difficult, and definitely depends on the kind of message. The (typical) plaintext's entropy might give a rough estimate. This is a factor that's independent of the encryption algorithm or key.

---
Tags: cryptography, encryption
---


# Question
Title: Why decision problem definition ignores Gödel incompleteness theorem?
The following question assume that the decision problem definition (syntactic) has been written (and could be changed if it isn't able) to catch a concept (meaning, semantic) which has both nice implications and some models. So please don't answer "the definition is the definition".

Let be any usual proof system, let $x$ be an object and let $P\_{x}$ be a property. By Gödel incompleteness theorem, there are 3 cases :

1. $P\_x$ is true and there is a proof for this.
2. $P\_x$ is false and there is a proof for this.
3. $P\_x$ is unprovable and there is neither a proof of trueness nor a proof of falseness.

But, regardless those 3 cases, a decision problem is defined by its set of positive instances (which hasn't even to match with 1.). Consequently, we must give truth value (positiveness/negativeness) to statements which don't have any in our proof system, I know that such a completion isn't inconsistent but it doesn't make much sense in my opinion.

Defining a decision problem constructivly, the decision problem would be just the target property, would make more sense. What could be the problems of such an approach ?

# Answer
> 4 votes
A decision problem is a question of the form:

> *Does $x$ have property $P$?*

A solution to such a problem is a Turing machine $T$ such that:

1. For all $x$, $T(x)$ terminates.
2. If $x$ has property $P$ then $T(x)$ outputs `true`.
3. If $x$ does not have property $P$ then $T(x)$ outputs `false`.

Notice how formal systems play no role in the above. We are asking for a *machine* to corectly determine whether $P(x)$ is *true*. (The other possibiity is that $P(x)$ is *false*, and there is no third options, if you believe in excluded middle.) We did *not* ask for the machine to find a proof of $P(x)$! You should make sure to understand the difference between truth and provability.

There is an important class of decisions problems which have no solutions because of Gödel's incompleteness theorem. For instance, the decision problem

> *Does formula $\phi$ have a proof in Peano arithmetic?*

has no solution because there is no Turing machine that will correctly answer the question for all formulas $\phi$.

But in general decision problems are not directly linked to provability. For instance, the Halting Problem "does Turing machine $T$ stop on input $x$?" has nothing to do with any formal system. It is a question about machines.

---
Tags: computability, logic, decision-problem, incompleteness
---


# Question
Title: SimRank on a weighted directed graph (how to calculate node similarity)
I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that it applies to unweighted graphs.

It's easy to adapt the matrix representation of SimRank to use weighted edges:

$\mathbf{S} = \max\\{C \cdot (\mathbf{A}^T \cdot \mathbf{S} \cdot \mathbf{A}),\mathbf{I}\\}$

Just replace the entries in the adjacency matrix $\mathbf{A}$ with the edge weights. But I don't see how to derive the "iteration to a fixed-point" method from this formula.

$s\_{k+1}(a, b) = \frac{C}{\left|I(a)\right|\left|I(b)\right|} \cdot \sum\_{i \in I(a)} \sum\_{j \in I(b)} s\_{k}(i, j)$

Is the following method correct?

$s\_{k+1}(a, b) = C \cdot \sum\_{i \in I(a)} \sum\_{j \in I(b)} s\_{k}(i, j) \cdot w(i, a) \cdot w(j, b)$

My reasoning is that the original method is equivalent to this:

$s\_{k+1}(a, b) = C \cdot \sum\_{i \in I(a)} \sum\_{j \in I(b)} s\_{k}(i, j) \cdot \frac{1}{\left|I(a)\right|} \cdot \frac{1}{\left|I(b)\right|}$

so I replaced the trivially equal weights with the actual ones I have. Confirmation would be nice, though.

If there is a superior method to SimRank, I would like to hear about it. (I'm concerned with improvements to accuracy, not performance; this is a small data set.)

Edit: A different similarity metric that's nearly as accurate but performs a lot better would actually be useful too. My initial tests of SimRank are very slow, and the potential optimizations are not simple to code.

# Answer
> 4 votes
The paper "SimRank++: Query Rewriting through Link Analysis of the Click Graph" describes a weighted SimRank algorithm that is similar to my attempt. It uses this formula to update similarity scores:

$s\_{k+1}(a, b) = \text{evidence}(a, b) \cdot C \cdot \sum\_{i \in I(a)} \sum\_{j \in I(b)} s\_{k}(i, j) \cdot w(i, a) \cdot w(j, b) \cdot \text{spread}(i) \cdot \text{spread}(j)$

$\text{evidence}(a, b) = \sum\_{i=1}^{\left|I(a) \cap I(b)\right|} \frac{1}{2^i}$

$\text{spread}(i) = e^{-\text{Var}(\\{w(i, a) ~|~ a \in O(i)\\})}$

Note that the weights should be normalized to sum to 1, which I was already doing. SimRank++ also incorporates evidence scores (which account for the quantity of incoming edges) and spread (which accounts for variance of outgoing edge weights).

---
Tags: graphs, weighted-graphs, adjacency-matrix, sparse-matrices
---


# Question
Title: How to get the intersection of two regular languages?
I was trying to figure out the value of the following expression.

`(0 | 1)*00 ∩ (0 | 1)*01`

I tried drawing DFAs for`(0 | 1)*00` and `(0 | 1)*01` separately and combine them using a table.

Is it the approach I should use? or is there any better way?

# Answer
One simple way is to note that $(0 | 1)\*00$ is a set of strings that all end with the symbol $0$, while $(0 | 1)^\*01$ is a set of strings that all end with the symbol $1$.

Hence, no string can be in both sets, which implies that their intersection is empty: $$(0 | 1)\*00\cap(0 | 1)^\*01=\emptyset$$
> 5 votes

# Answer
One approach is to convert each regexp to a NFA, then use the product construction to compute the intersection of those two NFA, then convert back to a regexp if necessary. Whether this is better or not, I can't say, as that depends what you mean by "better". One advantage of this approach is that it uses only standard techniques that hopefully you've already learned in your automata theory course and doesn't require memorization of specialized algorithms.
> 5 votes

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


# Question
Title: Find the subset of k element between n that maximize the total distance
Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S\_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm.

$$S\_{max} = \arg \max\_S\sum\_{i,j \in S, i \ne j} d(x\_i,x\_j)$$

In my specific case, $Q\subset \\{ 0, 1 \\} ^m $, thus $d(\cdot,\cdot)$ is equal to the Hamming distance.

Is there any efficient way to solve this problem? Is it possible to rewrite it in another simpler way?

# Answer
> 0 votes
This problem smells like it might be NP-hard, though I have no proof. If you are looking for a proof of NP-hardness, my advice would be to go through Garey & Johnson (or some other list of NP-complete problems) and look for all problems that seem plausibly related: e.g., ones that involve the hypercube, bitvectors and the Hamming distance, clustering in general metric spaces, or total/average distance in some general metric space. Then, edit your question to list all of those known-NP-complete and plausibly-related problems in your question... and try to see if you can find a reduction from any of them to your problem.

If you are less concerned about theoretical results and instead are looking to solve this in practice as efficiently as possible, some of the techniques in Maximize distance between k nodes in a graph can be adapted to your problem. In particular, I'll suggest two candidate approaches: if you want an exact solution, try using ILP; if you want an approximate solution, try FPF.

You can formulate your problem as an instance of integer linear programming (ILP). Introduce variables $y\_i$, where $y\_i$ indicates whether the $i$th point $x\_i$ is included in $S\_{max}$, and $z\_{i,j}$, with the intended meaning that $z\_{i,j} = y\_i \land y\_j$. Constrain each of these to be zero-or-one integer variables. Add the constraints $\sum\_i y\_i \le k$ and $z\_{i,j} \le y\_i$ and $z\_{i,j} \le y\_j$ and $z\_{i,j}=z\_{j,i}$. Your goal is to maximize the objective function

$$\sum\_{i,j} d(x\_i,x\_j) z\_{i,j}.$$

You can optionally add the extra constraints $y\_i+y\_j-1 \le z\_{i,j}$ and/or $z\_{i,j}+z\_{j,k}-1 \le z\_{i,k}$ and/or $\sum z\_{i,j} \le k(k-1)$; this will increase the number of constraints, but might help the solver find a solution more quickly. Now give this ILP instance to an off-the-shelf ILP solver, and hope that it can find a solution efficiently.

If you want a fast heuristic to find an approximate solution, you could try using FPF, as described here. You could also try a greedy algorithm: at the $i$th iteration, select the vertex $x\_j$ that increases the total distance of all the vertices selected so far by as much as possible. Neither of these is guaranteed to find an optimal solution, and the solution they output probably won't be optimal, but if you're lucky, they might be not-too-much-worse than optimal.

---
Tags: algorithms, optimization, combinatorics, np-hard
---


# Question
Title: scale-free networks and adjacency matrix
Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the probability that there is a directed edge from $a$ to $b$).

Is it possible to have such probability distribution ?

Note that the case without the "scale-free" property is not a problem. I can define the probability of having an edge from $a$ to $b$ as $P((a,b))=1/2$ for all $a, b$, $a \neq b$ in the graph.

Thank you.

# Answer
The most popular generative model for scale-free networks is the preferential attachment model of Barabási and Albert. A graph is sampled using an iterative procedure. This is a different sampling procedure than you suggest, since the goal is not only to generate a certain degree sequence, but also to mimic other properties of real-life networks.

If all you're after is a certain degree sequence, you can use MCMC methods; see for example Stanton and Pinar. Such algorithms don't conform to your type of algorithm, however. If you want to use your type of model, you have to decide in advance which vertices will have high degree and which will have low degree, since otherwise you will get a degree distribution which is either roughly Gaussian or roughly Poisson, but definitely no power law.

If all you're after is a certain degree sequence and you really want to use your own generative model, here is one possibility. Use the preferential attachment model, the algorithm of Stanton and Pinar, or any other randomized algorithm to generate a graph $G$. Now your model is: given two vertices $x,y$, if $(x,y) \in G$ then connect $x$ and $y$ with probability $1$, otherwise connect them with probability $0$.
> 2 votes

# Answer
Your question is fairly unclear and it seems you lack basic understanding in the topic of scale-free networks. Congratulations! You now feel like almost every other PhD student ever. ;)

From how I understand your question, you would like to have a *probability distribution* over graphs such that you obtain a scale-free graph *with high probability* from this distribution. There are numerous ways of achieving that, and one of the most popular ones is the Preferential attachment model noted by Yuval.

It seems to me, however, that furthermore, you want to "grasp the individual edge probabilities by hand". Like the Erdos-Renyi random graph model $G(n,p)$, you want to basically know the $p$ for an edge given two nodes $u,v$. This is actually very hard to do for the preferential attachment model! (Though there exist results that do that).

But I have good news for you: This is possible! There are in fact several scale-free network models that give you exact edge probabilities and yet generate a scale-free graph in the end. The most famous one is probably the Chung-Lu Random Graph. The first hit on google seems to give a very good introduction to the topic. Here's the gist of it:

1. First, for each vertex $i \in \\{1, \ldots, n\\}$ choose a weight $w\_i$ for that vertex. There are several appropriate ways to do this, but if you want something concrete you can use $w\_i = \delta \cdot (n/i)^{1/(\beta - 1)}$. This will produce a scale-free network with power-law exponent $\beta$.
2. Second, connect two nodes with probability $p\_{i,j} := \min\\{1, \frac{w\_i w\_j}{\sum\_k w\_k}\\}$

I hope this helps. If you have any further questions, don't hesitate to ask.
> 1 votes

---
Tags: graphs, computer-networks, adjacency-matrix
---


# Question
Title: Data versioning in a relational database
I've been working on an industrial project where my job was to design a data model in-memory and in a relational database in such a way, that can capture the time-varying nature of the production planning of a factory. In other terms, there exist input data and whenever a planning occurs, I have to take a snapshot of the current state of the world and store it.

My solution was to add a header object/table for all relevant input data and output data and have them reference each other's header by its unique auto-incrementing id. Such headers are then considered final and immutable and I do a deep-copy only if something needs to change.

I believe this approach isn't new but I can't recall any (relational-) data modelling courses explicitly mentioning this. My PhD advisor (who is not into general CS) wants me to have a thesis point about this and I'm unable to convince him that either this isn't new or at most a trivial extension to some existing methodology. I've tried searching Google Scholar, but didn't find any articles, perhaps due to wrong keywords.

Can someone point me into the right direction?

# Answer
> 1 votes
I've seen a thesis on this subject, but that was long ago.

One thing to search for a combination of `relational databases` and `versioning`, which will produce things such as tuple versioning; another is temporal databases.

As far as I know, there really is no standard way to address your problem. How best to model it depends on what information you want to be in the snapshot and on how you want to use the information later.

For instance, if you never ever want to pose queries that combine information from different snapshots, you can save each snapshot to a different database. That allows you to use the same constraints and queries on your snapshots that you use on the live data.

If you never need to pose queries that combine information from your live operational state with information from your snapshots, you probably want to save the snapshots to a different database than the live information. That way, you can at least continue to use constraints and queries on the live data that do not take the extra snapshot information into account. On the snapshots, you will need to rewrite the constraints and queries. But it will be easier to pose queries that combine information from different snapshots.

To be honest, I don't understand what you mean by "add a header object/table for all relevant input data". If all of the snapshots are put into the same database, without creating separate tables for each snapshot, I expect to see one or two columns for every table whose tuples should be in the snapshot. The extra column(s) would contain a snapshot identifier: a timestamp or a foreign key into a new table with more information about snapshots. In case of two columns, they would indicate the first and last snapshot in which the given tuple is present. This can save space if you have many snapshots, but it can also make querying harder.

---
Tags: reference-request, databases, modelling
---


# Question
Title: Using dynamic programming to find the number ofl increasing subsequences
I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing sub-sequences for every index j, that end with Xj.

My solution should include a recurrence formula that solves this problem in O(n^2) and a correctness proof, I was only able to solve it using a nested for loop and I'm not sure if there's an O(n^2) recursion solution.

```
List a[1…n] <- [1…1]
 For j= 1 to n
    For i= 1 to j-1
       If xi<xj then
          a[i]= a[j]+a[i];

```

# Answer
> 1 votes
The recursive equivalent of what you wrote is:

```
function S(j) is
  r <- 1
  For i <- 1 to j-1
    if xi<xj then
      r <- r+S(i)
  return r

```

It is very similar to what you wrote, except that `a[1]` is replaced by `S(i`), i.e., a recursive call to the function, since it is the function that is supposed to compute the number of sequences that you store in `a[i]`. The array `a` is used to remember previous results, and the new result you are computing is obtained using the previous results.

This array is no longer needed, as it is replaced by the memoization of the dynamic programming interpretation of the recursive function. If I understood correctly what you are asking.

Now, to do the proof, you should explain why computing in this way is correct.

This works with the same costs as your algorithm, provided the recursion is interpreted with dynamic programming memomization, and you should be able to prove it easily.

Of course standard recursive execution of the function, without memoization of results, is a lot more costly.

---
Tags: algorithms, dynamic-programming, recursion, correctness-proof
---


# Question
Title: What techniques can I use to hand-write a parser for an ambiguous grammar?
I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a statically typed language, and my desired syntax for a function type renders the grammar temporarily\* ambiguous until resolved. I'd rather not use a parser generator, though I know that Elkhound would be an option. I know I can alter the grammar to make it parse within a fixed number of steps, but I'm more interested in how to implement this by hand.

I've made a number of attempts at figuring out the high-level control flow, but every time I do this I end up forgetting a dimension of complexity, and my parser becomes impossible to use and maintain.

There are two layers of ambiguity: a statement can be an expression, a variable definition, or a function declaration, and the function declaration can have a complex return type.

Grammar subset, demonstrating the ambiguity:

```
basetype
  : TYPE
  | IDENTIFIER
  ;

type
  : basetype
  | basetype parameter_list
  ;

arguments
  : arraytype IDENTIFIER
  | arraytype IDENTIFIER COMMA arguments
  ;

argument_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN arguments CLOSE_PAREN
  ;

parameters
  : arraytype
  | arraytype COMMA parameters
  ;

parameter_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN parameters CLOSE_PAREN
  ;

expressions
  : expression
  | expression COMMA expressions
  ;

expression_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN expressions CLOSE_PAREN
  ;

// just a type that can be an array (this language does not support
// multidimensional arrays)
arraytype:
  : type
  | type OPEN_BRACKET CLOSE_BRACKET
  ;

block
  : OPEN_BRACE CLOSE_BRACE
  | OPEN_BRACE statements CLOSE_BRACE
  ;

function_expression
  : arraytype argument_list block
  | arraytype IDENTIFIER argument_list block
  ;

call_expression
  : expression expressions
  ;

index_expression
  : expression OPEN_BRACKET expression CLOSE_BRACKET
  ;

expression
  : function_expression
  | call_expression
  | index_expression
  | OPEN_PAREN expression CLOSE_PAREN
  ;

function_statement
  : arraytype IDENTIFIER argument_list block
  ;

define_clause
  : IDENTIFIER
  | IDENTIFIER ASSIGN expression
  ;

define_chain
  : define_clause
  | define_clause COMMA define_chain
  ;

define_statement
  : arraytype define_chain
  ;

statement
  : function_statement
  | define_statement SEMICOLON
  | expression SEMICOLON
  ;

statements
  :
  | statement statements
  ;

```

Example parses:

```
// function 'fn' returns a reference to a void, parameterless function
void() fn() {}
// the parser doesn't know which of these are types and which are variables,
// so it doesn't know until the end that this is a call_expression
Object(var, var, var, var)
// the parser only finds out at the end that this is a function declaration
Object(var, var, var, var) fn2() {}
(Object(var, var, var, var) ())
(Object(var, var, var, var) () {})
// the parser could possibly detect the "string" type and figure out that
// this has to be a define statement or a function declaration, but it's
// still ambiguous to the end
Object(Object(string, Object), string[]) fn3() {}
Object(Object(string, Object), string[]) fn4 = fn3;

```

My basic approach has been to write functions that could parse the unambiguous components of this subset of the grammar, and then flatten the more complex control flow into individual functional blocks to capture state in function calls. This has proved unsuccessful, what techniques can one use to solve this kind of problem?

\*There is likely a better word for this

# Answer
This answer is based on the additional information you give that your problem might be **more non-determinism than ambiguity**, and that you think you could then solve it if you had some lookahead arbitrarily far away.

Since this case allows for quite different answer, I think it is clearer to answer it separately from my previous answer.

If unbounded lookahead is all you need, then you should investigate whether RLR parsing could do the job for you. The idea of RLR is that you use a finite state automaton to get information that can be arbitrarily far away. I am not sure about all the details of the technique in its general form, but it has been implemented in some freely available parser generators.

Given that you insist on a hand written parser, you might be able to apply that by hand to your own grammar.

The best way to explain it is on a well known example, because many languages actually need unbounded look ahead, but deal with the problem under the rug, so that you do not notice it.

The usual name for the rug is lexical analysis.

Suppose the grammar includes the following rules:

```
U -> X Y
V -> X Y id
M -> U id foo
N -> V bar
Z -> M | N

```

where `id` is any identifier, while `foo` and `bar` are language keywords.

and you have to parse `... xxxx yyy very_long_identifier foo ...`.

After reducing `xxxx` to `X` and `yyy` to `Y`, you have to decide whether to reduce `X Y` to `U`, or rather scan the coming identifier. It is quite visible that that depend on the keyword `foo` or `bar` that comes after the identifier. This can be easily dealt with with bounded lookahead, as the decisive keyword is only 2 tokens away when the decision is to be made.

But this assumes that the identifier is considered as a single keyword.

Some people assert that, since CF languages are closed under substitution by regular sets, lexical analysis is not really essential and CF parsers should be able to handle it with the rest of the CF syntax. This is true for a general CF parser (though disputable on practical grounds). But it requires some care and adaptation for classical deterministic parsing technology, because the theoretically unbounded length of identifiers raises lookahead problems.

In the example above, if the identifier has not been recognized as such by a lexical analyzer, then it is just an arbitrarily long sequence of alphanumeric tokens, so that the decisive keywords, `foo` and `bar` are unboundedly far away.

This shows that recognizing an intermediate structure through a pass with a simple finite state device can remove a problem such as unbounded lookahead, at least in some cases, which is all you ask for if you develop by hand a specific parser.

If is for you to analyze precisely your grammar to see what can be done, but the above suggest the following approach:

You state:

> I cannot know definitively whether a given string of tokens represents a function statement, expression, or define statement until near the end of any of those structures in the worst case.

So the question is (up to some probably modifiable details): can you recognize that a sequence of symbols is one of these two constructs of your language, and identify which (without producing a parse-tree) by means of a simple finite state automaton (FSA)? If the answer is yes, than whenever you encounter the beginning of such a sequence, you activate the corresponding FSA to determine quickly which kind of sequence it is, and then you use the result to make your parsing decision.
> 2 votes

# Answer
I did not read in detail your grammar which is far too large for my available time, and short of an example that you should provide (since you assert it is ambiguous) I will not not attempt to check whether it is, which is in general undecidable.

This said, as already remarked by user rici there are general context-free (GCF) parsers that will parse any CF grammar, whether ambiguous ot not. (I am ignoring very old depth first, recursive decent parser). GCF parsing takes in general a time $O(n^3)$ where $n$ is the size of the input sentence. However, it will be only $O(n^2)$ for unambiguous, but possibly non-deterministic grammars. And they are usually linear for many grammars, or for a significant subset of the language defined by the grammars (see below).

I think it would be abusive to qualify these parsers as using unbounded lookahead. Actually they try simultaneously all parsing possibilities in parallel, and abandon some when further information from the input becomes incompatible with the attempted parse. This is not the same as not attempting a parse using some known facts about the rest of the string, which is what lookahead is about. Indeed, several of these algorithm may try not to attempt some parses, based on bounded lookahead information: this is true of Earley's, GLL and GLR. Furthermore, the concept of lookahead is meaningful for on-line algorithms, which is not really the case for GCF parsers.

The best way to survey this technology is probably a fast historical overview.

The (almost) oldest of GCF parser is the well known CYK algorithm. It is pure dynamic programming constructed directly on the grammar. It is extremely simple, but not best in performance.

The next one is Earley's algorithm (1968). Contrary to what is often said, it is not simple, at least in its general form, and there is no standard reference that I know regarding the format of the produced parse-trees (parse-forest). It is not clear that its performances are the best one might expect. Earley's algorithm is actually derived in a somewhat ad hoc fashion from Knuth's LR(k) parser construction. This of course diminishes in no way the importance of its contribution to introducing new parsing concepts.

This was generalized by Lang (1974), who proposed a general dynamic programming interpretation of any PDA, that could be combined with any PDA construction technique, such as LR, LL or precedence, giving techniques known as GLR or GLL parsing. When the technique an yield a derterministic automaton, the GCF parser works in linear time.

Tomita realized the first implementation of this technique, applied to LR(k) PDA construction in 1984, thus implementing the first GLR parser. Then it was also used for LL(k) PDA construction, in this millenium.

Regarding performance, people have often tried to improve it by using sophisticated PDA construction techniques that have been designed to increase the number of grammars that can be parsed deterministically. This folk wisdom is apparently ill-advised, as analyzed by Billot and Lang (1989). That suggests that efficient GCF parsers can have a fairly simple structure.

All of these parser can work fast enough on modern computers. They produce all possible parse-trees, in a condensed form called parse-forest. One issue may be the representation of the parse-forest which may be more or less convenient depending on the implementation. Of course, if the CF grammar is unambiguous, there is only a single parse-tree, which may do away with this parse-forest problem.

A major difference with traditional deterministic parsers is that the production of the parses is online for deterministic parsers, producing the left part of the parse-tree in synchronization with the reading of the corresponding left part of the sentene being parsed. With the GCF parsers, it is more an offline behavior, as you may have to wait the very end of the parsing process before you know what parsing structure is relevant.

Another issue is that I do not know how well parsing errors can be handled by current implementation. I do know that some very interesting work has been done on that by the Natural Language community.

Regarding your own grammar, I think that trying to use these techniques in a hand written parser is just looking for trouble. You woud have to have an excellent mastery of the technology. There is just nothing to be gained. But, given the way you state your question, if you want a simple implementation that you can master, for testing purposes, you may try the CYK algorithm. It main advantage is that, like Earley's algorithm, it works directly on the grammar, which you may find more intuitive.

Many parser generation system now propose some form of GCF parsing, but I have no personnal experience with any of them, thus no recommendations.
> 4 votes

# Answer
It's not clear to me if your grammar is truly ambiguous or if it is simply unbounded lookahead, but I think it is the latter; all the comments in your example use the phrase "does not find out until the end" which implies that the parser can eventually uniquely parse any correct sentence.

The simplest parsing algorithm for context-free grammars (CFGs) requiring unbounded lookahead is probably the Earley algorithm, which runs in $O(n^2)$ for unambiguous grammars (It's $O(n^3)$ in the worst case if the grammar is ambiguous, but that doesn't include the time required to enumerate all possible parses.) It is particularly simple if you have no rules with empty right-hand sides; all of the complications you might read about in the literature have to do with nullable non-terminals.

In essence, the algorithm is simply a non-deterministic version of normal top-down parsing. It involves the same predict / scan / complete(reduce) steps, except that the prediction is not deterministic. At each step, more than one prediction may be possible; both possibilities (or all) need to be considered. The trick of the Earley algorithm is a (straight-forward) method of representing the possibilities which doesn't exhibit exponential blow-up.

The effect is that all possible parses are explored in parallel, making it a bit tricky to use recursive descent. (You'd need parallel stacks, one for each viable alternative.) Instead, the algorithm uses a classic dynamic programming structure. It maintains a vector of sets of parse states; the vector corresponds to the input sequence so each token in turn is associated with a set of states. Each state corresponds to a point in a hypothetical call stack, so it contains information about where it is (in some right-hand side) and where it would return to on completion of the right-hand side.

A similar technique is used in a Tomita GLR parser, but it is based on a bottom-up algorithm rather than a top-down algorithm. Again, instead of a single parser stack, the algorithm maintains a collection of stacks. In order to keep the performance guarantee (like the Earley algorithm, it is $O(n^3)$ for any CFG and $O(n^2)$ for unambiguous grammars), it uses a slightly complicated data structure which allows the parallel stacks to share common prefixes and suffixes. Implemented correctly, this allows deterministic (i.e. bounded lookahead) grammars to be parsed in $O(n)$. (The Earley algorithm can be modified to achieve this as well.) \[See note 1\]

As with the Earley algorithm, you'll find lots of references on the net about issues with the Tomita algorithm in corner cases; again, all of these have to do with nullable productions. If you can write your grammar without nullable productions, you'll find implementing it with either Earley or Tomita to be a simple enough exercise.

Having said that, I don't really see the point of doing so. There is no particular advantage to hand-writing a state machine if you've got a state machine compiler, and these days it's easy enough to find a parser generators which can cope with unbounded lookahead grammars. (Even the venerable `bison` has a perfectly usable GLR option.)

---

### Notes

1. In practice, unbounded lookahead is usually resolved in a reasonably small number of tokens. If it weren't, the (programming) language would be hard for human readers, which is generally considered bad style. For an unambiguous grammar, a GLR parser (or modified Earley parser) only incurs a high cost when presented with a text which requires lots of lookahead, so it is quite a practical parsing technique.
> 3 votes

---
Tags: compilers, parsers, ambiguity
---


title: Travelling with the most efficient path

text:
# Question
Title: Travelling with the most efficient path
A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.

The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.

For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.

You need to find the most efficient way to reach the destination.

What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.

Do you have any idea how to do it? Or any hints?

Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?

Some more thoughts:

* Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
* $1000$ and $50$ might be deliberately picked to avoid complex computation.
* Is there a greedy solution? I cannot think of any just yet.
* I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.

And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.

# Answer
The basic idea is to make $n$ trips, returning to the start and refueling on all but the last trip. On each trip but the last, you'll leave some fuel at a new dump. You want to know how far you can go on the last trip. To make calculations easy, we'll say that a full tank contains 1 (unit) of fuel and that amount will take you a distance of 1 (other unit) of distance.

**Example 1** ($n = 1$ trip). Trivial: drive until you run out of fuel. Distance covered $D(1)=1$.

**Example 2** ($n=2$). On the first trip, travel $x$ distance, so you'll have $1-x$ fuel remaining. Leave just enough fuel at dump 1 to allow you to return to the start. Leaving $1-2x$ at dump 1 will do the trick. On the second trip, starting with a full tank, go to the first dump (using $x$ of your fuel), top off your tank (taking $x$ from the dump, leaving $1-3x$) and drive until you run out of fuel. To maximize the distance we'll need the dump to be empty so $1-3x=0$, so $x=1/3$. The total distance you'll cover will be $D(2)=1+1/3$.

**The general case**. With $n$ trips, you'll hit dump 1 $2n-1$ times, dump 2 $2n-3$ times, dump 3 $2n-5$ times, and so on. To empty the dumps on the last trip, we'll place dump 1 at a distance $1/(2n-1)$, dump 2 at a further distance $1/(2n-3)$, and so on. Then the last trip will cover $$ D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1} $$ If we define the $m$-th harmonic number, $$ H\_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m} $$ then it's well known that $H\_m\approx\ln m$ and we can write our distance $$\begin{align} D(n) &= 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}\\ & = \left(1 + \frac{1}{2}+\frac{1}{3}+ \dotsm + \frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+ \dotsm + \frac{1}{2n-2}\right)\\ &=H\_{2n-1}-\frac{1}{2}H\_{n-1} \end{align}$$ This will take an amount of trips (and fuel) that are exponential in the desired distance. For example, to go a distance of $2$, it will take $n=8$ trips and to go a distance of $5$ will take $3093$ trips.

This (and a variant) is known as the **jeep problem** and is covered in more detail here.
> 5 votes

---
Tags: algorithms, complexity-theory, efficiency, applied-theory
---


title: Radix sort and changing bases

text:
# Question
Title: Radix sort and changing bases
I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime is $O(d(n+k))$ where $d$ is the number of digits in the numbers, and $k$ is the base. So shouldn't there be a permanent ratio between $d$ and $k$ so that the runtime is optimized? How should I choose the base in any other way?

# Answer
The asymptotic runtime ignores access times for the digits. On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number.

If you have multiple CPUs, you can more easily exploit parallel processing by using a larger base. The large base will spread the numbers across many buckets which can then be sorted in parallel.

Another reason to change bases is if you know your data has a bias (such as Benford's Law) that would cause the numbers to initially cluster into only a few buckets.
> 2 votes

---
Tags: runtime-analysis, sorting, radix-sort
---


# Question
Title: Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?
I'm currently reading the *elements of programming* book and have come across a section I don't quite understand

> A *computational basis* for a type is a finite set of procedures that enable the construction of any other procedure on the type. A basis is *efficient* if and only if any procedure implemented using it is as efficient as an equivalent procedure written in terms of an alternative basis. **For example**, a basis for unsigned *k*-bit integers providing only zero, equality, and the successor function is not efficient, since the complexity of addition in terms of successor is exponential in *k*

Given the successor function , wouldn't addition be *linear*? e.g. getting get the result of `a + b` the complexity would be `O(b)` starting from a? I know this is likely not the case as I'm sure the book knows more about what it's saying than me, but can someone explain *why* this operation would be exponential?

# Answer
> 10 votes
The complexity of getting "the result of `a + b`" would indeed "be `O(b)` starting from a".

However, `b` is a `log(b)`-bit integer, and `O(b) = O(2^(log(b)))`.

# Answer
> 5 votes
From the Wikipedia article on time complexity:

> In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

(Wikipedia references Sipser, *Introduction to the Theory of Computation*, for the above sentence.)

In your case, the "length of the string representing the input" is the number of bits representing $a$ and $b$, call it $k$. Since $O(b) = O(2^k)$, this is exponential time.

To put this into perspective, imagine you are a computer. Someone loads an algorithm into your CPU and you're just blindly working on the input bits that you are given. To you, it really doesn't matter what these bits represent; they could be numbers, sets, English words, doesn't matter. You're just following the step-by-step procedure. Thus when talking about running time, it only makes sense to consider the number of bits, not the potential numbers they represent.

It might now get confusing when you think of things like sorting. Why don't we consider the number of bits of the array elements when discussing the running time of a sorting algorithm? Well, we do, it's just that there is the implicit assumption that all the array elements can be represented by a constant number of bits (*e.g.*, 32-bit integers). Thus the asymptotic running time is unaffected.

# Answer
> 4 votes
The average magnitude $m$ of a number of $k$ binary digits is an exponential function of $k$ (because $k= \lfloor{\log\_2{m}}\rfloor + 1$, $ m\>0$). Using only zero, equality, and the successor function, the best you can get is an algorithm that is in $\Theta(2^k)$.

Fortunately, using other procedures you have algorithms that are much better than that.

---
Tags: algorithms, complexity-theory, efficiency, integers
---


# Question
Title: Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$
I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\\{ a^n b^n c^n \colon n\ge 0 \\}$ is not a CFL.

Now, in the book they do it in a way that I understand but I think it can be simplified, so here goes:

Assume by contradiction that $L\in CFL$ with pumping constant $p$ and let $\omega = a^p b^p c^p$. Clearly $\omega \in L$ and $\\| \omega \\| \ge p$. Let $\omega = uvxyz$ a division such that

1. $\\| vy \\| \> 0$
2. $\\| vxy \\| \le p$

Condition 1 stipulates that for every $i \neq 1$ pumping will actually change the substring $vxy$. Condition 2 stipulates that the substring $vxy$ is comprised of at most two type of alphabet symbols. For now we assume that these symbols are $a$ and $b$.

Combine these two facts and we see that for every $i \neq 1$ the string $uv^i xy^i z$ has a different number of $a$'s and $b$'s than $c$'s.

Again, the proof in the book is a bit more complexed, which leads me to think that I might have a mistake here.

Any thoughts? thanks!

# Answer
> 4 votes
Frankly, I think your argument works. As there is always one of the letters missing, the second condition forces the substring to be "short", pumping will not get equal amounts of $a,b,c$.

For didactical purposes authors in books take extra precautions to make sure the student understands that all cases must be covered. Hence they tend to avoid shortcuts.

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


# Question
Title: Global relabeling heuristic: Push-relabel maxflow
I have a correct, working implementation of the preflow-push-relabel maxflow algorithm \[2\]. I am trying to implement the global relabeling update heuristic \[3\], but have run into some issues.

I have a specific instance of the problem here to illustrate my questions :

a) For this problem instance, the "current preflow" is a state that is reached by my implemented max flow algorithm \[\[ even without global relabeling heuristic we reach this state \]\]. Without applying any heuristics the algorithm proceeds to completion from this state giving the correct result.

b) The distance labels (in green) at this state represent a valid labeling as for every (u, v) \belong to E\_{residual} d\_u \<= d\_v + 1

Q1: The distance label (or height) is supposed to be a lower bound on the distance from the sink. However for several nodes in the residual graph (eg: 6, 7) this is not true. Eg. Node 7 has a distance label of 14...but clearly has a distance of 1 from the sink in the residual graph.

Q2: On running the global relabel at this stage, we get a labeling as seen in the extreme right. From this point on (depending on how frequently you do the global update), the algorithm can get stuck \[\[ deadlock \]\] -- eg. nodes 6, 3 keep circulating flow between them as they each get relabeled to a higher height. If you run the global update before the reach the final height, you will reset the heights and the process repeats.

I am reasonably sure I am making a very trivial error but am unable to put my finger on it. Can someone help me with this issue? I am happy to provide a code snippet if that would help.

A couple more points that may be relevant:
-\> I am implementing a single phase version of the push-relabel algorithm (ie. do not stop when you have a min. cut, but continue till you obtain a valid flow).
-\> I am processing active vertices in FIFO order in the current problem instance. But I have a highest label first \[3\] implementation as well. I do not think this affects the two questions I have.

Thank You!

\[\[ This question has also been posted on programmers stackexchange -- I was unsure which forum is better for this question \]\]

\[2\] A new approach to the maximum flow problem; A.Goldberg, R.Tarjan; JACM, Vol 35. Iss 4, 1988

\[3\] On implementing the push-relabel method for the maximum flow problem; B.V.Cherkassky, A.Goldberg

# Answer
> 1 votes
Q1: The invariant goes the other way around: `height[n1] <= height[n2] + 1` for all edges `(n1,n2)` in the residual graph.

As the sink (10) is not adjacent from (7) in the residual graph, the configuration `height[7] == 14, height[10] == 0` is perfectly fine.

The other way around, (7) *is* adjacent from (10) in the residual graph, and indeed `height[10] <= height[7] + 1`.

---
Tags: algorithms, network-flow, heuristics, program-correctness
---


# Question
Title: What is the rationale behind implicitly widening integer types in numeric operations?
Languages such as Java and C specify implicit widening of integer types for numeric operators, especially arithmetic operators, to a minimum of 32 bits. What is the rationale behind doing this?

My impression is that it's based on the end-programmer's expectations - that is, `200 + 100` should yield `300`, and not overflow to `44`. Is there additional impetus behind this implicit type conversion?

This decision to widen only to 32 bits seems a bit arbitrary to me. Besides performance/memory concerns (some target instruction sets don't support 64-bit numbers, so more instructions are necessary), why not widen to 64 bits to minimize overflow as much as possible? If a language were designed which required 64-bit integer promotion for the operands of a numeric operation, would a sufficiently sophisticated optimizer be able to optimize down to 32-bits where sufficient (or, given that I have a pretty poor grasp on computability, is such an optimization impossible)?

TLDR: why are `200` and `100` in `200 + 100` widened to 32 bits? Why not 64 bits? Would a language be significantly inefficient if converted operands to 64 bits, especially if implemented with a "good" optimizer?

# Answer
> 1 votes
First of all, when you write `200 + 100` the compiler deduces the type for both numbers. It's assigning `int` which has a width of 32bits on most languages and target architectures, so your `200` was never just `0xC8`, it always were `0x000000C8` (on little endian).

Why are we still using 32bits? My guess is that 32bits is still the sweet spot for avoiding overflows while not using too much memory.

Moving from 32bits to 64bits requires twice the memory, that is trivial, but has some details.

* Twice the memory will have to be moved, and the memory copying speed won't increase.
* Twice the memory will not only reside on your ram, but also on the cache of your CPU, and while your system may have a lot of ram it still has quite limited cache. Take for example the i7-4790K, quite more powerful and expensive than your average CPU. It says it has 8MB of cache, but that is Level-3 cache, it has 4x32kB data Level-1 cache to use across it's 4 cores, now memory seems expensive.
* When I mentioned the Level-1 cache I was only bringing you closer to the real thing. Your CPU operates on it's registers and they are even more limited.

This may seem interesting now: Memory hierarchy

"Most modern CPUs are so fast that for most program workloads, the bottleneck is the locality of reference of memory accesses and the efficiency of the caching and memory transfer between different levels of the hierarchy"

Edit: I forgot to mention that because of the no-overhead backwards compatibility of the amd64 (x86-64) architecture, 32bits operations are done just as fast as 64bits operations, but probably that also applies to 16bits.

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


# Question
Title: prove language is Context-free and not regular
I have to prove that $\left \\{ a, b \right \\}^{\ast} - \left \\{ a^ib^i | i\geq 0 \right \\}$ is a context-free language and it's not regular.

So far I've got that this language is not regular because regular languages are closed under complementation and $\left \\{ a^ib^i | i\geq 0 \right \\}$ is a well know context free language (by the way do you have a link with a formal proof that $\left \\{ a^ib^i | i\geq 0 \right \\}$ is context free?)

For the context-free I'm a little confused I've thought about building a PDA that recognize $\left \\{ a^ib^i | i\geq 0 \right \\}$ (pushing a's on the stack and popping a's when a b is read works?) I think is deterministic CF so i can use the same reasoning (complement of a DCF is a DCF language?)

# Answer
> 1 votes
To prove that the language is Context Free, it suffices to give the Push Down Automaton, and that language is recognized by one of the simplest PDA.

To prove that the language is NOT regular, you don't only have to show that you can't find an appropriate Automaton (be it a FDA or FNA, they have equivalent expressive power), but that no one can.

That proof can't be shown with an example, because you want to prove that not a single FDA can recognize the language correctly. The proof shows a contradiction between having such FDA and that the FDA correctly rejects some words outside the language.

The idea is similar to the pumping lemma. Suppose that you have an FDA that recognizes the language, you are going to break it. That FDA is, as it name says, finite, let it's size (node count) be $N$. To recognize the words in $\left \\{ a^ib^i | i\geq N \right \\}$ it certainly has to do some loops.

By exploiting a loop of length $l$ (looping in it one time more than the expected), you can see that $a^{(i+l)}b^i$ should also be accepted by that FDA, so it fails to recognize the language, as it would accept words that are not in it.

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


# Question
Title: What is the appropriate algorithm for bipartite matching with constraints?
I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).

Let's say we have a lot of employees and a few jobs to be done. Each employee ranks the jobs they want most.

Easy. Bipartite matching, with weighted edges. Or Hungarian algorithm. Right?

Now things become more complicated. Instead of one job each day, an employee has to do 4 jobs in a day. The same single ranking they gave will be taken into account for the other 3 jobs they receive (no repetitions).

Since each employee must have 4 jobs, and there are many more employees than jobs, each job can have multiple people assigned to it for each period.

More complicated: each job has a maximum of employees it can accommodate (different for each job).

More complicated. Now jobs are skill based. Each employee has not only a preference ranking, but a skill class they belong to, low, med, or high. So each job has a phase for the low-skilled, the medium-skilled, and the high-skilled, with a skill level repeated for the fourth phase, as needed.

The objective is to make sure every employee ends up with the most of their highest ranked choices.

Does there exist some framework for solving such problems? Is there a way to adapt bipartite matching for all of these constraints?

# Answer
The problem as described still seems amenable to doing a bipartite matching with weighted edges if you adapt the graph setup as follows.

If an employee must do four jobs, represent the employee with four vertices in the graph. Each job should be represented as four vertices in the graph, one for each needed skill level plus one repeated skill level. Connect each employee vertex with the job vertex corresponding to the highest skill level the employee is capable of performing. Don't connect an employee to more than one skill level within a job. Example: if a job has two high skill phases, connect all the employee vertices for a given qualified employee to one phase or the other, not both. The edge weights between the employee and job vertices should be the employee preference score for the job.

With this graph, a maximal bipartite matching should produce proper job assignments maximizing employee preferences while matching skills.
> 1 votes

# Answer
Constraint satisfaction problems are solved easier on declarative languages, where you specify the problem and not how to actually solve it.

Look for a max-SAT solver (=
> 1 votes

---
Tags: algorithms, graphs, assignment-problem
---


# Question
Title: Regular Expression from Context Free Grammar
The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular expression from the grammar

> $S\rightarrow ASA\mid A$
> $A\rightarrow aAa\mid aAab\mid bA\mid\epsilon$

By intuition I guessed that this grammar generates words in the form of $\left \\{ a^ia^jb^\*a^jb^ja^i \right \\}^\*$ and, correct me if I'm wrong, this doesn't seems like a regular language.

My problem with this type of exercise (I've tried a lot like this) is that there is no automatic way to find the regular expression from the grammar even if it generates indeed a regular language. Any advice on how to proceed on exercises like this?

# Answer
Denote your grammar by $G$ and let $$ M=\\{w\in\\{a,b\\}^\*\mid |w|\_a\equiv 0\pmod 2\\} $$ where $|w|\_a$ is the number of $a$s in $w$. In other words, $M$ is the set of all strings of $a$s and $b$s with an even number of $a$s. We claim $L(G)=M$.

First, it is clear that any word in $L(G)$ must have an even number of $a$s, so $L(G)\subseteq M$. All we now have to do is show $M\subseteq L(G)$, in other words, that every string in $M$ can be generated by $G$. We'll show this by induction on the number, $n$, of $a$s in a word.

If $n=0$, we can generate strings consisting only of $i\ge 0\ b$s by one of two derivations: $$\begin{align} S &\Rightarrow A\Rightarrow \epsilon \\ S &\Rightarrow A\Rightarrow bA\stackrel{\*}{\Rightarrow} b^i \end{align}$$ So we can generate all strings with no $a$s.

If $n=2$, any string in $M$ with exactly two $a$s must have the form $b^iab^jab^k$ with $i, j, k\ge 0$. Write such a string as $(b^i)(ab^ja)(b^k)$. We've seen that we can generate the $b^i$ and $b^k$ portions from $A$. We can also generate the $ab^ja$ part from $A$: $$ A\Rightarrow aAa\stackrel{\*}{\Rightarrow} ab^ja $$ so we can generate $b^iab^jab^k$ by $$ S\Rightarrow ASA\Rightarrow AAA\stackrel{\*}{\Rightarrow} b^iAA\stackrel{\*}{\Rightarrow}b^iab^jaA\stackrel{\*}{\Rightarrow}b^iab^jab^k $$ and it's clear that we can continue this process for even $n\>2$, simply by starting with the requisite number of $A$s. In short, we've shown that any word in $M$ can be generated by the grammar $G$, and this, combined with the first part, shows that $L(G)=M$.

Of course, $M$ is regular, if for no other reason than it is denoted by the regular expression $(ab^\*a+b)^\*$. Also, it would also be easy to construct a finite automaton for $L$ as well.
> 2 votes

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


title: fixed point in regular expressions

text:
# Question
Title: fixed point in regular expressions
I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll figure out the regular expression I'll derive the equivalent Finite Automaton that accepts the language generated by the grammar), but instead I'm trying to understand the methodology to derive regular expressions (if they exists, from context-free grammars)

I have this productions of a context free grammar (axiom S, e is the empty word)

S-\>AS|b|A A-\>abA|Ab|e I have to figure out a regular expression (if exists) that generates a language equivalent to the one generated by that grammar.

So far i wrote that

```
L(S)=L(A)L(S) + b + L(A) = L(A)*(L(A) + b) (by Arden Rule)
L(A)=(ab)*(L(A)b+e)

```

I've tried the method of finding the fixed point (I'd like more info about that since seems I can't get the hang of it

```
for A: 0 -> e -> (ab)*(b+e) -> (ab)*[(ab)*(b+e)](b+e)

```

should i check if (ab)*(b+e) = (ab)*(ab)\*(b+e) (if that's is the fixed point? Or should i go ahead?) It's not the first exercise I'm having trouble with so any help would be appreaciated, Thanks.

# Answer
As all productions in $A\rightarrow \mathrm{ab}A\text{ }|\text{ }A\mathrm{b}\text{ }|\text{ }ε$ are linear, and (crucially) there is only one non-terminal symbol, all derivation sequences can be reordered into equivalent ones where left-side derivations always precede (or always succeed) right-side ones.

For instance:

$wAv \Rightarrow w\mathrm{ab}Av \Rightarrow w\mathrm{ab}A\mathrm{b}v \Rightarrow w\mathrm{abab}A\mathrm{b}v \Rightarrow w\mathrm{abab}A\mathrm{bb}v\equiv \\wAv \Rightarrow wA\mathrm{b}v \Rightarrow wA\mathrm{bb}v \Rightarrow w\mathrm{ab}A\mathrm{bb}v \Rightarrow w\mathrm{abab}A\mathrm{bb}v$

(This is a hint of what an inductive proof using fixed-points would look like in this particular case. Check this if you are determined to go down that road).

This means that this grammar can be converted into a regular grammar in two steps, by grouping left-linear and right-linear productions:

```
1.

```

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow A''\mathrm{b}\text{ }|\text{ }ε$

```
2.

```

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow \mathrm{b}A''\text{ }|\text{ }ε\\\$

So $\mathcal{L}(A) = (\mathrm{ab})^\*\mathrm{b}^\*$
> 3 votes

---
Tags: context-free, regular-expressions, parsers
---


title: Prove language is regular

text:
# Question
Title: Prove language is regular
let's have these two languages in the alphabet $\\{a,b,c\\}$:

$L\_1 = \\{ w \mid w \text{ is a palindrome and $|w| \< 200$}\\}$

$L\_2 = \\{ w \mid w \text{ is a suffix of $u$ and $|u|$ is a prime number and $u$ doesn't contain a $c$}\\} $

and I have to prove that $L\_1 ∪ L\_2$ is regular.

So my idea is I have to prove both languages are regular and therefore their union would be regular. $L\_1$ is obviously regular since it's finite. I also know that the language consisting of all suffixes of words from a regular language is also regular, so I narrowed it down to proving that

$L = \\{w \mid |w| \text{ is a prime number and $w$ doesn't contain a $c$}\\}$

any ideas on that one? Thanks in advance.

# Answer
> 2 votes
The language $L$ is not regular, but $L\_2$ is. In fact $L\_2 = \\{a,b\\}^\*$. Indeed if $w \in L\_2$, then by definition, $w$ is suffix of a word of $\\{a,b\\}^\*$ and thus $w \in \\{a,b\\}^\*$. Thus $L\_2 \subseteq \\{a,b\\}^\*$. To prove the opposite inclusion, consider a word $w \in \\{a,b\\}^\*$. Let $p$ be a prime such that $p \geqslant |w|$ and let $u = a^{p-|w|}w$. By construction, $|u| = p$, $u \in \\{a,b\\}^\*$ and $w$ is a suffix of $u$, and thus $w \in L\_2$.

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


# Question
Title: Converting Regular expression to DFA by building syntax tree
There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute **first pos**, **last pos**, **follow pos**, and then use a Transition technique to build DFA for that particular regular expression. But this case only works when operators in the regular expression are only . (Dot), * (star), | (or). I just want to know if the operators in the regular expression are like ?, \[\], - and etc. Then can i convert regular expression to DFA just like above way?

Thanks in advance.

# Answer
> 1 votes
No, using complementation yields an exponential blow-up in the size of the DFA.

---
Tags: automata, finite-automata, regular-expressions, compilers, syntax-trees
---


# Question
Title: Regular expression of a language over {a,b,c} which does not contain substring bbb
I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the Regular Expression but still stuck as I found the DFA a bit complicated. I appreciate any help. Thanks!!!

Ok, here is the Regular Expression I've worked on to help me solve the above question. a*c*\[(acb)\* U (acbb)*\]a*c\*

Test: aaaa ccccc acbacbacb aaaaaaa ccccc (OK) aa acbb acbb acbb acbb cccccccc (OK)

But how about cab or cabb? I then modified the above expression to: a*c*\[(acb)\* U (acbb)\* U (cab)\* U (cabb)*\]a*c\*

I'm I heading to the right direction?

Thanks again!

# Answer
The following regular expression (where $\cdot$ stands for $a|b|c$) will match all strings with lengths divisible by 3 not containing the string $bbb$ and not starting with a b.

$((a|c)\cdot\cdot)^\*$

Can you modify this to get the expression you want?
> 1 votes

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