# Question
Title: Solve modified knapsack problem using dynamic programming
I'm trying to solve following modified knapsack problem using dynamic programming.

**What we know:**

* Total number of items
* Item weight, value and type
* Knapsack capacity

**Aims**

* Find Maximum weight of knapsack
* List taken Items

**Constraints**

* Only one item of each type can be taken

For example, in my problem, the item list would look like:

Fruit

```
Banana (weight 9, value 10)
Apple (weight 4, value 30)
...

```

Vegetable

```
Potato (weight 2, value 20)
Onion (weight 3, value 25)
...

```

Sweet

```
Chocolate(weight 4, value 30)
Cookie(weight 2, value 30)
...

```

and so on, where the problem requires that you select exactly one item from Fruit, one item from Vegetable, one item from Sweet, and so on.

Can anyone give me some advice about algorithm or pseudo code?

# Answer
> 1 votes
Let $C \ge 1$ be the capacity of the knapsack and let $G\_1, \dots,G\_k$ be your groups, where each group is a non-empty collection of items, i.e., $G\_i = \\{ x^{(i)}\_1, x^{(i)}\_2, \dots \\}$. Groups are pairwise disjoint. Define $n= \sum\_{i=1}^k |G\_i|$ as the total number of items in the instance.

For any item $x$, let $w(x)$ and $v(x)$ denote its weight and value, respectively, and assume for simplicity that the all weights and the values of the above items positive. It is helpful to imagine the existence of $k$ additional items $x\_1^{(0)}, \dots, x\_k^{(0)}$, each with value and weight $0$.

Here are three possible algorithms. Pick the fastest one according to your instance.

---

For $i=0, \dots, k$ and $c=0, \dots, C$, define $OPT\[i, c\]$ as the maximum overall value that can be obtained by selecting at most one element from each of the group $G\_1, \dots, G\_i$ and no elements from the groups $G\_{i+1}, \dots, G\_k$, with the constraint that the total weight of the selected elements must be at most $c$.

According the above definition we have $OPT\[0,c\] = 0$ and, for $i \> 0$ $$ OPT\[i,c\] = \max\_{\substack{j=0, \dots, |G\_i| \\ w(x^{(i)}\_j) \le c}} \left( v(x^{(i)}\_j) + OPT\left\[i-1, c-w(x^{(i)}\_j)\right\] \right). $$

You can compute all the quantities $OPT\[i,c\]$ in non-decreasing order of $i$. Since $OPT\[i,c\]$ can be fond in time $O(|G\_i|)$, the overall time complexity is $$ O\left( C \cdot \sum\_{i=1}^k |G\_i| \right) = O(C \cdot n). $$

The value of the optimal solution is $OPT\[k, C\]$ and an optimal set of items to select can be found using standard techniques.

---

Let $V$ be an upper bound on the maximum attainable value. For example: $V = \sum\_{i=1}^k \max G\_i$.

For $i=0, \dots, k$ and $v=0, \dots, V$, define $OPT\[i, v\]$ as the minimum overall weight of a set of items that has an overall value of at least $v$ and can be obtained by selecting at most one element from each of the group $G\_1, \dots, G\_i$ and no elements from the groups $G\_{i+1}, \dots, G\_k$. If no such set of items exists, define $OPT\[i, v\]= +\infty$.

We have $OPT\[0, 0\] = 0$, and $OPT\[0, v\] = +\infty$ for $v\>0$. Moreover, for $i\>0$: $$ OPT\[i, v\] = \min\_{j=0,\dots,|G\_i| } \left( w(x^{(i)}\_j) + OPT\left\[i-1, \max\\{v - v(x^{(i)}\_j), 0 \\}\right\] \right). $$

The value of the optimal solution is $\max \\{v \mid v=0, \dots, V \wedge OPT\[k, v\] \le C\\}$. Again, you can solve all subproblems in non-decreasing order of $i$, where each $OPT\[i, v\]$ can be found in time $O(|G\_i|)$ yielding an overall time complexity of $O(V \cdot n)$.

---

Partition the groups into three sets $\mathcal{G}\_1, \mathcal{G}\_2, \mathcal{G}\_3$ such that $\sum\_{G\_i \in \mathcal{G}\_1} |G\_i| \le n/2$, $\sum\_{G\_i \in \mathcal{G}\_2} |G\_i| \le n/2$, and $|\mathcal{G}\_3| = 1$.

Guess an element $x^\*$ that belongs to the only group in $\mathcal{G}\_3$. There are at most $O(n)$ choices.

Exhaustively generate all sets that can be constructed by selecting at most one element from each group in $\mathcal{G}\_1$ (and no elements from other groups). For each such set $S$ look at the pair $(\sum\_{x \in S} w(x), \sum\_{x \in S} v(x))$ and collect all these pairs into a list $L\_1$. Notice how there are at most $O(2^{n/2})$ sets to examine, which means that we can build $L\_1$ in time $O(n \cdot 2^{n/2})$.

Repeat the same procedure for $\mathcal{G}\_2$ to obtain a list $L\_2$. Sort the pairs $(w,v)$ in $L\_2$ in non-decreasing order of $w$ and use this sorted list to compute a value $\nu(w)$ for each $w$ that appears in some pair $(w, v)$ in $L\_2$. Specifically, $\nu(w) = \max\_{\substack{(w',v') \in L\_2 \\ w' \le w}} v'$, i.e., $\nu(w)$ is the maximum value that can be obtained by selecting at most one item from each set in $\mathcal{G}\_2$ without exceeding an overall weight of $w$. Sorting $L\_2$ requires time $O(n \cdot 2^{n/2})$, while the quantities $\nu(w)$ can be found by a linear scan of (the sorted version) of $L\_2$.

Finally, for each pair $(w, v)$ in $L\_1$ with $C-w-w(x^\*) \ge 0$, we can fetch $\nu(C-w-w(x^\*))$ in time $O(\log |L\_2|) = O(\log 2^{n/2}) = O(n)$ and consider the quantity $v + v(x^\*) + \nu(v)$ as a candidate answer.

The maximum among all candidate answers is the value of an optimal solutions to your original instance. The overall time spent is $O(n^2 \cdot 2^{n/2})$.

---
Tags: dynamic-programming, knapsack-problems, java
---


# Question
Title: How to represent mutually exclusive events in CSP
I am studying Communicating Sequential Processes (CSP), and I understand that an event can be "emmited" ($\overline{e}$) and an event can be "waited on" ($e$), so that an event will sync with another parallel event ($\overline{e} || a \rightarrow e$).

Now how do I represent the fact that an event *must* not occur at the same time as another one, but can occur right after or right before? Is there something I missed?

# Answer
So, I have asked this question at my university, and the answer I got was:

1. The model does not account for parallelism, only concurrency.
2. The model assumes that events are "instant" or "atomic".

So no two events can occur at the same time because no two things ever happen at the same time (no "paralellism"), and the event takes no "time", of which there is no concept of.
> 1 votes

---
Tags: computation-models, parallel-computing
---


# Question
Title: Is this language a context-free language or not?
I try to determine if the following statement is true:

for any given language $L \subseteq A^\*$ if $L$ is a context-free language then $L\_1 = \\{u^Rv^R \ | \ uv \in L, |u|=|v| \\}$ is also a context-free language.

Initially I tried to come up with a counterexample but now I start to believe this statement could be true. As far as I know I could prove that language is not a context-free language using pumping lemma but how can I prove this language is a context-free one (if it's true)? I would be grateful for any hints.

Edit: I found interesting and maybe related question: Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

Based on the question from the above link I started to wonder if language $L = \\{uv \ | \ |u|=|v| \\}$ is a context-free language only if $u \neq v$. If it's true then answer to my question is obvious.

# Answer
No, $L\_1$ is not necessarily context-free.

---

For example, let $L=\\{0^n1^{3n}\mid n\ge0\\}$.

If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$.

So, $L\_1=\\{1^n0^n1^{2n}\mid n\ge0\\}$, which is not context-free.
> 8 votes

# Answer
I do not think the linked question is relevant.

Consider the context-free language $L = \\{a^n b^n c^m d^m \mid m,n\ge 0\\}$.

Let us consider an example string, $uv = a^3 b^3 c^8 d^8 $. Assuming $u$ and $v$ are of equal length, $u= a^3 b^3 c^5$ and $v= c^3 d^8 $. Thus $u^Rv^R = c^5 b^3 a^3 d^8 c^3$. We see that the letters are in a rather scrambled order.

Now study the minimally scrambled strings in the new language, meaning $L\_1 \cap b^\* a^\* d^\* c^\*$.

What is that language?
> 3 votes

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


# Question
Title: Could someone give me an example of MaxSat's approximable 1/2 algorithm?
in my Complexity class I have to present the 1/2 **MaxSat approximation algorithm** that appears in the Vazirani, Vijay V - Approximation algorithms-Spring (2011) \[Image attached\]. The problem is that it is not clear to me where and how the **weights** are assigned. The example talks about considering the weights as a unit but I don't understand why. Could someone give me a small **example of the execution of the algorithm**?

Thank you

# Answer
The weights are provided as part of the instance: each clause is accompanied by one.

In the unweighted case, you can think of each clause as having unit weight.
> 0 votes

---
Tags: maxsat
---


title: Randomized Algorithm Lemma

text:
# Question
Title: Randomized Algorithm Lemma
Hello I am struggling with proving a lemma, it goes as follows:

Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose now we have a n x n matrix called M (which has at least one non zero element).

I need to prove that the Pr\[Mr = 0\] \<= 1/2(basically prove that the probability of one random position of the matrix M is zero is less than or equal 1/2).

Hint: We can assume that M11 ≠ 0. Based on the hypothesis, argue that the probability of the inner product of the first line of the matrix with the vector r being zero, is at most 1/2.

Also with the help of the above lemma give a randomized algorithm that can check if 3 matrices n x n A,B,C satisfy the relation AB = C in O(n^2).

# Answer
To prove the claim

$$ P(Mr = 0 ) \leq \frac{1}{2} $$ it is enough to prove it for any row vector $m = (M\_{i,1},...,M\_{i,n})$ that has at least one non-zero coefficient. Thus, we continue by induction on $n$.

> $n= 1 $ base case

The base case is trivial since

$$ P(mr=0) = P(r=0) = \frac{1}{2} $$ in this case.

> Induction case $n \implies n+1$.

If $m$ has only one nonzero coefficient then it reduces to the base case; otherwise, there are at least 2 non-zero coefficients say $m\_1,m\_2$ and we can condition on the two cases $r\_1 = 0,1$ to get the result by applying the induction hypothesis.

The second part is given by the following algorithm:

1. Generate a uniform random binary vector $r$
2. Multiply $Br$ to get $r\_1$
3. Multiply $Ar\_1$ to get $r\_2$
4. Multiply $Cr$ to get $r\_3$
5. Subtract $r\_2-r\_3$ to get $r\_4$
6. **Return** $r\_4$

This algorithm has $P(r\_4 = 0 )\>\frac{1}{2} \iff AB = C$ and has complexity $\mathcal{O}(n^2)$.
> 2 votes

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


# Question
Title: Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}
The language given is $L = \\{a^i b^j c^k\mid i+j \ge 2k\\}$ for which I need to construct a simplest possible Context Free Grammar.

I tried understanding but I could only go as far as making sense of $i+ j = 2k$ but I am unable to come up with anything that caters for the condition where it it can be less than 2k.

# Answer
> 3 votes
### Grammar

```
Main rules:
S -> AASc | T      two A for each c
T -> ABUc | U      AB for one c (at most once)
U -> BBUc | ε      two B for each c
A -> Aa | a        one or more a for each A
B -> Bb | b        one or more b for each B

Additional rules:
S -> A | B | AB

```

The main rules for S, T and U produce $A^i B^j c^k$ with $i+j=2k$. The rules for A and B turn them into $a$ and $b$, allowing additional ones to make it $\ge$.

The additional rules are for $k=0$, since with $i+j=2k$, that also means $i=j=0$. I'll try to think of a neater way to cover those cases.

### Testing results / tool

I wrote a little tool that computes all words produced by the grammar up to a certain length and compares that to the correct set of words up to that length. Result:

```
Correct for words up to length 15: True
(That's 471 words.)
missing 0 words: []
invalid 0 words: []

```

Code (Try it online!):

```
import re
from itertools import product

start = "S"
rules = {
    "S": ["AASc", "T", "A", "B", "AB"],
    "T": ["ABUc", "U"],
    "U": ["BBUc", ""],
    "A": ["Aa", "a"],
    "B": ["Bb", "b"],
}
empties = "[UTS]"

max_length = 15

# Generate words with the grammar
words = horizon = {start}
while horizon:
    horizon = {
        new_word
        for word in horizon
        for match in re.finditer("[A-Z]'?", word)
        for symbol, start, stop in [[match[0], *match.span()]]
        for body in rules[symbol]
        for new_word in [word[:start] + body + word[stop:]]
        if len(re.sub(empties, '', new_word)) <= max_length
    } - words
    words |= horizon
generated_words = {word for word in words
                   if not word or word.islower()}

# Generate words in a simple was as reference
correct_words = {
    'a'*i + 'b'*j + 'c'*k
    for i, j, k in product(range(max_length + 1), repeat=3)
    if i + j + k <= max_length and i + j >= 2 * k
}

# Show the comparison results
print(f'Correct for words up to length {max_length}:',
      generated_words == correct_words)
print(f"(That's {len(correct_words)} words.)")
def sort(words):
    return sorted(words, key=lambda word: (len(word), word))
missing = sort(correct_words - generated_words)
invalid = sort(generated_words - correct_words)
print(f'missing {len(missing)} words:', missing)
print(f'invalid {len(invalid)} words:', invalid)

```

### Testing gnasher729's grammar

Using this:

```
start = "S"
rules = {
    "S": ["aaSc", "a", "X", "abXc"],
    "X": ["bbXc", "Y"],
    "Y": ["bY", ""],
}
empties = "[YXS]"

```

Result (Try it online!):

```
Correct for words up to length 15: False
(That's 471 words.)
missing 265 words: ['aa', 'ab', 'aaa', 'aab', 'abb', 'aaaa', 'aaab', 'aabb', 'abbb', 'aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aaabc', 'aabbb', 'abbbb', 'aaaaaa', 'aaaaab', 'aaaaac', 'aaaabb', 'aaaabc', 'aaabbb', 'aaabbc', 'aabbbb', 'abbbbb', 'aaaaaaa', 'aaaaaab', 'aaaaaac', 'aaaaabb', 'aaaaabc', 'aaaabbb', 'aaaabbc', 'aaabbbb', 'aaabbbc', 'aabbbbb', 'abbbbbb', 'aaaaaaaa', 'aaaaaaab', 'aaaaaaac', 'aaaaaabb', 'aaaaaabc', 'aaaaaacc', 'aaaaabbb', 'aaaaabbc', 'aaaaabcc', 'aaaabbbb', 'aaaabbbc', 'aaabbbbb', 'aaabbbbc', 'aabbbbbb', 'abbbbbbb', 'aaaaaaaaa', 'aaaaaaaab', 'aaaaaaaac', 'aaaaaaabb', 'aaaaaaabc', 'aaaaaaacc', 'aaaaaabbb', 'aaaaaabbc', 'aaaaaabcc', 'aaaaabbbb', 'aaaaabbbc', 'aaaaabbcc', 'aaaabbbbb', 'aaaabbbbc', 'aaabbbbbb', 'aaabbbbbc', 'aabbbbbbb', 'abbbbbbbb', 'aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac', 'aaaaaaaabb', 'aaaaaaaabc', 'aaaaaaaacc', 'aaaaaaabbb', 'aaaaaaabbc', 'aaaaaaabcc', 'aaaaaabbbb', 'aaaaaabbbc', 'aaaaaabbcc', 'aaaaabbbbb', 'aaaaabbbbc', 'aaaaabbbcc', 'aaaabbbbbb', 'aaaabbbbbc', 'aaabbbbbbb', 'aaabbbbbbc', 'aabbbbbbbb', 'abbbbbbbbb', 'aaaaaaaaaaa', 'aaaaaaaaaab', 'aaaaaaaaaac', 'aaaaaaaaabb', 'aaaaaaaaabc', 'aaaaaaaaacc', 'aaaaaaaabbb', 'aaaaaaaabbc', 'aaaaaaaabcc', 'aaaaaaaaccc', 'aaaaaaabbbb', 'aaaaaaabbbc', 'aaaaaaabbcc', 'aaaaaaabccc', 'aaaaaabbbbb', 'aaaaaabbbbc', 'aaaaaabbbcc', 'aaaaabbbbbb', 'aaaaabbbbbc', 'aaaaabbbbcc', 'aaaabbbbbbb', 'aaaabbbbbbc', 'aaabbbbbbbb', 'aaabbbbbbbc', 'aabbbbbbbbb', 'abbbbbbbbbb', 'aaaaaaaaaaaa', 'aaaaaaaaaaab', 'aaaaaaaaaaac', 'aaaaaaaaaabb', 'aaaaaaaaaabc', 'aaaaaaaaaacc', 'aaaaaaaaabbb', 'aaaaaaaaabbc', 'aaaaaaaaabcc', 'aaaaaaaaaccc', 'aaaaaaaabbbb', 'aaaaaaaabbbc', 'aaaaaaaabbcc', 'aaaaaaaabccc', 'aaaaaaabbbbb', 'aaaaaaabbbbc', 'aaaaaaabbbcc', 'aaaaaaabbccc', 'aaaaaabbbbbb', 'aaaaaabbbbbc', 'aaaaaabbbbcc', 'aaaaabbbbbbb', 'aaaaabbbbbbc', 'aaaaabbbbbcc', 'aaaabbbbbbbb', 'aaaabbbbbbbc', 'aaabbbbbbbbb', 'aaabbbbbbbbc', 'aabbbbbbbbbb', 'abbbbbbbbbbb', 'aaaaaaaaaaaaa', 'aaaaaaaaaaaab', 'aaaaaaaaaaaac', 'aaaaaaaaaaabb', 'aaaaaaaaaaabc', 'aaaaaaaaaaacc', 'aaaaaaaaaabbb', 'aaaaaaaaaabbc', 'aaaaaaaaaabcc', 'aaaaaaaaaaccc', 'aaaaaaaaabbbb', 'aaaaaaaaabbbc', 'aaaaaaaaabbcc', 'aaaaaaaaabccc', 'aaaaaaaabbbbb', 'aaaaaaaabbbbc', 'aaaaaaaabbbcc', 'aaaaaaaabbccc', 'aaaaaaabbbbbb', 'aaaaaaabbbbbc', 'aaaaaaabbbbcc', 'aaaaaaabbbccc', 'aaaaaabbbbbbb', 'aaaaaabbbbbbc', 'aaaaaabbbbbcc', 'aaaaabbbbbbbb', 'aaaaabbbbbbbc', 'aaaaabbbbbbcc', 'aaaabbbbbbbbb', 'aaaabbbbbbbbc', 'aaabbbbbbbbbb', 'aaabbbbbbbbbc', 'aabbbbbbbbbbb', 'abbbbbbbbbbbb', 'aaaaaaaaaaaaaa', 'aaaaaaaaaaaaab', 'aaaaaaaaaaaaac', 'aaaaaaaaaaaabb', 'aaaaaaaaaaaabc', 'aaaaaaaaaaaacc', 'aaaaaaaaaaabbb', 'aaaaaaaaaaabbc', 'aaaaaaaaaaabcc', 'aaaaaaaaaaaccc', 'aaaaaaaaaabbbb', 'aaaaaaaaaabbbc', 'aaaaaaaaaabbcc', 'aaaaaaaaaabccc', 'aaaaaaaaaacccc', 'aaaaaaaaabbbbb', 'aaaaaaaaabbbbc', 'aaaaaaaaabbbcc', 'aaaaaaaaabbccc', 'aaaaaaaaabcccc', 'aaaaaaaabbbbbb', 'aaaaaaaabbbbbc', 'aaaaaaaabbbbcc', 'aaaaaaaabbbccc', 'aaaaaaabbbbbbb', 'aaaaaaabbbbbbc', 'aaaaaaabbbbbcc', 'aaaaaaabbbbccc', 'aaaaaabbbbbbbb', 'aaaaaabbbbbbbc', 'aaaaaabbbbbbcc', 'aaaaabbbbbbbbb', 'aaaaabbbbbbbbc', 'aaaaabbbbbbbcc', 'aaaabbbbbbbbbb', 'aaaabbbbbbbbbc', 'aaabbbbbbbbbbb', 'aaabbbbbbbbbbc', 'aabbbbbbbbbbbb', 'abbbbbbbbbbbbb', 'aaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaab', 'aaaaaaaaaaaaaac', 'aaaaaaaaaaaaabb', 'aaaaaaaaaaaaabc', 'aaaaaaaaaaaaacc', 'aaaaaaaaaaaabbb', 'aaaaaaaaaaaabbc', 'aaaaaaaaaaaabcc', 'aaaaaaaaaaaaccc', 'aaaaaaaaaaabbbb', 'aaaaaaaaaaabbbc', 'aaaaaaaaaaabbcc', 'aaaaaaaaaaabccc', 'aaaaaaaaaaacccc', 'aaaaaaaaaabbbbb', 'aaaaaaaaaabbbbc', 'aaaaaaaaaabbbcc', 'aaaaaaaaaabbccc', 'aaaaaaaaaabcccc', 'aaaaaaaaabbbbbb', 'aaaaaaaaabbbbbc', 'aaaaaaaaabbbbcc', 'aaaaaaaaabbbccc', 'aaaaaaaaabbcccc', 'aaaaaaaabbbbbbb', 'aaaaaaaabbbbbbc', 'aaaaaaaabbbbbcc', 'aaaaaaaabbbbccc', 'aaaaaaabbbbbbbb', 'aaaaaaabbbbbbbc', 'aaaaaaabbbbbbcc', 'aaaaaaabbbbbccc', 'aaaaaabbbbbbbbb', 'aaaaaabbbbbbbbc', 'aaaaaabbbbbbbcc', 'aaaaabbbbbbbbbb', 'aaaaabbbbbbbbbc', 'aaaaabbbbbbbbcc', 'aaaabbbbbbbbbbb', 'aaaabbbbbbbbbbc', 'aaabbbbbbbbbbbb', 'aaabbbbbbbbbbbc', 'aabbbbbbbbbbbbb', 'abbbbbbbbbbbbbb']
invalid 0 words: []

```

### Testing Peter Leupold's grammar

I'm not entirely sure I'm interpreting Peter correctly, but I think their full grammar is this:

```
start = 'S'
rules = {
    "S": ["aS'c", "aB'c", "aS"],
    "B'": ["bB", "b", "bB'"],
    "S'": ["aS", "aB", "aS'"],
    "B": ["bB'c", "bB"]
}
empties = "[']"

```

Result (Try it online!):

```
Correct for words up to length 15: False
(That's 471 words.)
missing 206 words: ['', 'a', 'b', 'aa', 'ab', 'bb', 'aaa', 'aab', 'aac', 'abb', 'bbb', 'bbc', 'aaaa', 'aaab', 'aaac', 'aabb', 'abbb', 'bbbb', 'bbbc', 'aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aabbb', 'abbbb', 'bbbbb', 'bbbbc', 'aaaaaa', 'aaaaab', 'aaaaac', 'aaaabb', 'aaaacc', 'aaabbb', 'aabbbb', 'abbbbb', 'bbbbbb', 'bbbbbc', 'bbbbcc', 'aaaaaaa', 'aaaaaab', 'aaaaaac', 'aaaaabb', 'aaaaacc', 'aaaabbb', 'aaabbbb', 'aabbbbb', 'abbbbbb', 'bbbbbbb', 'bbbbbbc', 'bbbbbcc', 'aaaaaaaa', 'aaaaaaab', 'aaaaaaac', 'aaaaaabb', 'aaaaaacc', 'aaaaabbb', 'aaaabbbb', 'aaabbbbb', 'aabbbbbb', 'abbbbbbb', 'bbbbbbbb', 'bbbbbbbc', 'bbbbbbcc', 'aaaaaaaaa', 'aaaaaaaab', 'aaaaaaaac', 'aaaaaaabb', 'aaaaaaacc', 'aaaaaabbb', 'aaaaaaccc', 'aaaaabbbb', 'aaaabbbbb', 'aaabbbbbb', 'aabbbbbbb', 'abbbbbbbb', 'bbbbbbbbb', 'bbbbbbbbc', 'bbbbbbbcc', 'bbbbbbccc', 'aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac', 'aaaaaaaabb', 'aaaaaaaacc', 'aaaaaaabbb', 'aaaaaaaccc', 'aaaaaabbbb', 'aaaaabbbbb', 'aaaabbbbbb', 'aaabbbbbbb', 'aabbbbbbbb', 'abbbbbbbbb', 'bbbbbbbbbb', 'bbbbbbbbbc', 'bbbbbbbbcc', 'bbbbbbbccc', 'aaaaaaaaaaa', 'aaaaaaaaaab', 'aaaaaaaaaac', 'aaaaaaaaabb', 'aaaaaaaaacc', 'aaaaaaaabbb', 'aaaaaaaaccc', 'aaaaaaabbbb', 'aaaaaabbbbb', 'aaaaabbbbbb', 'aaaabbbbbbb', 'aaabbbbbbbb', 'aabbbbbbbbb', 'abbbbbbbbbb', 'bbbbbbbbbbb', 'bbbbbbbbbbc', 'bbbbbbbbbcc', 'bbbbbbbbccc', 'aaaaaaaaaaaa', 'aaaaaaaaaaab', 'aaaaaaaaaaac', 'aaaaaaaaaabb', 'aaaaaaaaaacc', 'aaaaaaaaabbb', 'aaaaaaaaaccc', 'aaaaaaaabbbb', 'aaaaaaaacccc', 'aaaaaaabbbbb', 'aaaaaabbbbbb', 'aaaaabbbbbbb', 'aaaabbbbbbbb', 'aaabbbbbbbbb', 'aabbbbbbbbbb', 'abbbbbbbbbbb', 'bbbbbbbbbbbb', 'bbbbbbbbbbbc', 'bbbbbbbbbbcc', 'bbbbbbbbbccc', 'bbbbbbbbcccc', 'aaaaaaaaaaaaa', 'aaaaaaaaaaaab', 'aaaaaaaaaaaac', 'aaaaaaaaaaabb', 'aaaaaaaaaaacc', 'aaaaaaaaaabbb', 'aaaaaaaaaaccc', 'aaaaaaaaabbbb', 'aaaaaaaaacccc', 'aaaaaaaabbbbb', 'aaaaaaabbbbbb', 'aaaaaabbbbbbb', 'aaaaabbbbbbbb', 'aaaabbbbbbbbb', 'aaabbbbbbbbbb', 'aabbbbbbbbbbb', 'abbbbbbbbbbbb', 'bbbbbbbbbbbbb', 'bbbbbbbbbbbbc', 'bbbbbbbbbbbcc', 'bbbbbbbbbbccc', 'bbbbbbbbbcccc', 'aaaaaaaaaaaaaa', 'aaaaaaaaaaaaab', 'aaaaaaaaaaaaac', 'aaaaaaaaaaaabb', 'aaaaaaaaaaaacc', 'aaaaaaaaaaabbb', 'aaaaaaaaaaaccc', 'aaaaaaaaaabbbb', 'aaaaaaaaaacccc', 'aaaaaaaaabbbbb', 'aaaaaaaabbbbbb', 'aaaaaaabbbbbbb', 'aaaaaabbbbbbbb', 'aaaaabbbbbbbbb', 'aaaabbbbbbbbbb', 'aaabbbbbbbbbbb', 'aabbbbbbbbbbbb', 'abbbbbbbbbbbbb', 'bbbbbbbbbbbbbb', 'bbbbbbbbbbbbbc', 'bbbbbbbbbbbbcc', 'bbbbbbbbbbbccc', 'bbbbbbbbbbcccc', 'aaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaab', 'aaaaaaaaaaaaaac', 'aaaaaaaaaaaaabb', 'aaaaaaaaaaaaacc', 'aaaaaaaaaaaabbb', 'aaaaaaaaaaaaccc', 'aaaaaaaaaaabbbb', 'aaaaaaaaaaacccc', 'aaaaaaaaaabbbbb', 'aaaaaaaaaaccccc', 'aaaaaaaaabbbbbb', 'aaaaaaaabbbbbbb', 'aaaaaaabbbbbbbb', 'aaaaaabbbbbbbbb', 'aaaaabbbbbbbbbb', 'aaaabbbbbbbbbbb', 'aaabbbbbbbbbbbb', 'aabbbbbbbbbbbbb', 'abbbbbbbbbbbbbb', 'bbbbbbbbbbbbbbb', 'bbbbbbbbbbbbbbc', 'bbbbbbbbbbbbbcc', 'bbbbbbbbbbbbccc', 'bbbbbbbbbbbcccc', 'bbbbbbbbbbccccc']
invalid 0 words: []

```

# Answer
> 0 votes
Most likely the CFG you made has some transition to an accepting state when it sees the stack is empty.

This is exactly what checks the equality between $i+j$ and $2k$.

If, instead, you would change the transition so that it will always do this transition (Notice, this is a nondeterministic PDA!), then the PDA will accept any word that reaches this state while not "dying out" in the middle of the run. If you will think about it - this is exactly the change you need to also accept words with $i+j\ge 2k$.

# Answer
> 0 votes
Maybe your grammar for the equality in the condition looks something like this (only the productions):

$$ S\rightarrow aS'c | aB'c, \ \ B' \rightarrow bB |b, \ \ S' \rightarrow aS | aB, \ \ B \rightarrow bB'c $$

This supposes that $i$ and $j$ must be at least one. The primed nonterminals say that we have an odd $(i+j)$, the nonprimed ones say that this number is even. $(i+j)$ must be even in accepted words, so can only terminate with productions from the primed versions, which add one more symbol to make $(i+j)$ even. The $c$ are added via the productions from the nonprimed nonterminals.

Now if we add the possibility to produce additional $a$ and/or $b$ via the rules $S\rightarrow aS$ and $B\rightarrow bB$ and the same for the primed versions we can get $i+j\> 2k$.

# Answer
> 0 votes
If it was i + j \>= k: You first produce a’s and c’s in pairs, then b’s and c’s in pairs, then some more b’s. But it’s i + j \>= 2k, so you need 2 a’s and b’s for every c.

To do this we start producing two a’s and one c in pairs. Then we can add a single a and are done. Or we optionally add ab and c, then bb and c in pairs, then more single b’s. In summary:

```
S -> aaSc
S -> a
S -> X
S -> abXc
X -> bbXc
X -> Y
Y -> bY
Y -> eps

```

You can easily see that the result is $a^ib^jc^k$, that i and j can be any integers, and that for each c, we produce at least two of a and b.

For some practice, write a grammar for the case 2i + j \>= 3k. You just need to be very careful with the details.

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


# Question
Title: Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
I understand why L2 is not a regular language. We can use the pumping lemma to prove it

In the case of L2:

assume n = 1 and string = ab

We assume that L2 is regular, so it has "pumping length" property and it can be divided into 3 strings, x = empty string, y = a, z = b

Now we pump y, so after pumping once we get the string: aab. Now trivially the string aab is not present in the language L2

Now let's prove why L1 is regular language:

We cannot use the pumping lemma to prove that a language is regular. To prove that a language is regular we have to build either FA or Regular expression. Right?

But i don't understand why L1 would be regular, like there will be a case where n will be equal to m, which means it resembles the string from L2, and since we know any string of the form L2 is not regular. How could we come to the conclusion that L1 regular?

We def could build a regex for L1: a * b * which means it indeed is regular. But still for some reason i cannot grasp the concept intuitively. Can someone help me please?

# Answer
The language $L\_1 = \\{a^n b^m: n, m \ge 0, m \ge n\\}$ is not regular. This can be proved using the pumping lemma.

By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$ such that if $s \in L\_1$ and $|s| \ge p$, then $s$ can be divided into three pieces as $s=xyz$ such that (1) $xy^iz \in L\_1, \forall i \ge 0$, (2) $|y| \ge 1$, and (3) $|xy| \le p$. Let $s=a^p b^p$. Then, $s \in L\_1$ and $|s| \ge p$. Regardless of how $s$ is partitioned as $s=xyz$, since $|xy| \le p$, $y$ must contain only $a$'s. Since $y$ contains at least one $a$, $xyyz$ contains more $a$'s than $b$'s, whence $xyyz \notin L\_1$. This contradicts (1).
> 1 votes

---
Tags: regular-languages, finite-automata, regular-expressions, pumping-lemma, theory
---


# Question
Title: Is ε a part of alphabet or property of alphabet and NFA in FA
I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:

3rd point of the above image is the point of interest in the post

According to a few stackoverflow post: 1)https://math.stackexchange.com/questions/1689850/is-the-empty-string-always-in-a-finite-alphabet

2)https://stackoverflow.com/questions/52286628/how-can-i-tell-if-a-dfa-accepts-an-empty-string#:~:text=The%20empty%20string%20is%20never,string%20to%20accept%20the%20language.

It looks like ε is the property of the alphabet and NFA in the form of "zero sequence of alphabet symbols" and "ε transition". So it cannot be a part of the alphabet

But sipser does mention it as the union of alphabet and ε. So what does that imply?

1. Is ε a symbol like any other symbol present in the alphabet, then it isn't special anymore, which also means ε should be present in the input string such as "abεba" etc..
2. or, it's more like he wants to imply that NFA can have empty transition that is without reading any input, but to do that we use a special symbol ε. That's why he included ε in alphabet?
3. The meaning of ε is different in these two contexts? in the case of strings it means zero length and in the case of input it means no need to read input?

Can someone explain "can ε be a part of alphabet or not"

# Answer
> 1 votes
In the definition of $\Sigma\_\epsilon$, $\epsilon$ is a letter (which must not belong to $\Sigma$).

Elsewhere, $\epsilon$ is the empty word.

To avoid confusion, you can use different symbols for the two different meanings, say use $\epsilon$ for the empty word and $\hat\epsilon$ for the letter of $\Sigma\_\epsilon$.

# Answer
> 0 votes
There's a difference between how an NFA is represented and how it computes. Three common representations of an NFA are its state transition diagram, the tabular representation, and a description of each component of the 5-tuple by just writing down various sets and formulas. These are equivalent representations - if you have the state transition diagram, then you can construct the table, and vice-versa.

In terms of how an NFA computes, when an NFA reaches a new state, it splits into multiple copies, with one copy at this new state and other copies at states that can be reached from this new state by following one or more $\epsilon$-transitions. Because these new states are reached without consuming input, you can assume an empty string has been inserted at this place in the input. When defining the NFA, these $\epsilon$-transitions were placed in the diagram.

In the tabular representation of the NFA, you would have an extra column, with column heading $\epsilon$ say; the subset in row $q$ and column $\epsilon$ of the table is exactly the subset of states that can be reached from $q$ by following a single $\epsilon$-transition. In this tabular representation, whether you give the column a heading of $\epsilon$ or some other letter such as $\epsilon'$ is irrelevant, as long as it's clear that the entries in this column refer to the subsets of states that can be reached by an $\epsilon$-transition. The tabular form contains the same information as the state transition diagram.

In the tabular form, the subsets in the column labeled $\epsilon$ refer to subsets that can be reached by following a single arrow labeled $\epsilon$ (and are just an equivalent representation of the NFA's diagram), whereas in the computation, the machine can reach states that follow even 2 or more arrows labeled $\epsilon$ without consuming any input. To be precise, when the machine reaches a subset $R$ of states, the machine splits into copies and immediately reaches the subset $E(R)$ of states, where $E(R)$ is the set of states reachable from $R$ by following zero or more $\epsilon$-transitions.

An input string such as $abba$ would be accepted by the NFA if there is a sequence of transitions with labels $a, b, \epsilon, \epsilon, b, a$ that take the machine from the start state to an accepting state. Here, the string $abba$ is over the language $\\{a,b\\}$, and there are $\epsilon$-transitions in the diagram which you can interpret as being equivalent to an empty string.

---
Tags: automata, finite-automata, computation-models, nondeterminism, theory
---


# Question
Title: Complement of DFA always give the language which is complemented?
***Case:1***

Suppose l have one DFA which accepts the set of all strings over `{a, b}` which starts with `a`and it's complement is not starts with `a`.

From the above image we see that in the second diagram represents the DFA which accepts the strings which belong to complement of the language accepted by first DFA.

***Case:2***

Now consider the DFA which accepts set of all strings over `{a, b}` in which every `a` is followed by `b.` And the language should be

**L={$\epsilon$,ab,abab,....b,bb,...bab,bbab,babbbbab,....}**

See the image:

Now consider the DFA which accepts set of all strings over `{a, b}` in which every `a` should **never** followed by `b`(which is the complement of DFA which accepts set of all strings over `{a, b}` in which every `a` is followed by `b.`).

And the language should be

**L'={$\epsilon$,a,aa,aaa,......b,bb,....ba,bba,bbba,....}**

See the complement of L which is L':

In the last diagram we see that the DFA which accepts the strings like `aab, aba` etc which shows that language don't complemented of L properly.

My question is that in case:1 language, DFA and it's correspondence complement works properly. But in second case after complimenting DFA we don't get complimented language. Where did I mistaken to understand DFA and it's complement? Actually be L' represents the complement of L or not in case:2?

# Answer
Let $L$ be the language over the alphabet $\\{a,b\\}$ defined by $L = \\{w: \mbox{an $a$ in $w$ is always followed by a $b$}\\}$. Let $L' = \\{w: \mbox{an $a$ in $w$ is never followed by a $b$}\\}$. Observe that $L$ and $L'$ are not complements of each other. Strings such as $aab$ and $aba$ belong to neither $L$ nor $L'$ because some of the $a$'s in the string are followed by a $b$, but other $a$'s in the string are not followed by a $b$.

The strings $aab$ and $aba$ are not in $L$, and since you have a DFA for $L$, these strings are accepted by the complement DFA. It's just that your description of the complement $L'$ is incorrect. The complement of $L$ would be the language consisting of all strings $w$ over the alphabet $\\{a,b\\}$ such that $w$ contains at least one $a$ that is not followed by a $b$.
> 2 votes

# Answer
I have forgotten the quantifier:

~$\forall x \\,(P(x))\neq$$\forall x \\,($~$P(x)).$ Instead

1. ~($\forall x \\,,P(x))= $$(\exists x \\,,$~$P(x))$.
2. ($\forall x \\,,$~$P(x))= $~$(\exists x \\,,P(x))$.

That means Complement of $a$ always followed by $b$ is not $a$ never followed by $b$ instead:

1. Complement of $a$ always followed by $b$ is at least one $a$ is not followed by $b$ in any strings.
2. $a$ is never followed by $b$ is complement of at least one $a$ is followed by $b$ in any strings.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: How to prove ww^r is context free using pumping lemma for context free languages
I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could still be regular.

But since we already know that ww^r is a context free language cause we can design a pda for it, we should be able to divide a string from ww^r into 5 parts and pump it and the result should still be in the language. But i fail to do so, i have done the following:

assume w = 010 then ww^r = 010010

Then, u = 0, v = 10, x = 0, y = 1, z = 0

And then i pumped it once and i got: 010100110, which obviously isn't in the language produced by ww^r which again is contradicting because we can design a pda for it

Where am i going wrong? How do i exactly use pumping lemma for CFL?

# Answer
The pumping lemma for context-free languages is used to prove that a given language is *not* a context-free language. There exists a PDA accepting the language $L = \\{w w^r: w \in \\{0,1\\}\\}$, and so $L$ is a context-free language.

The pumping lemma states that all regular languages and all CFL's satisfy a certain property: there exists a pumping length $p$ such that for every string of length at least $p$ in the language, there exists a partition of the string (into 3 parts or 5 parts) such that the pumped string belongs to the language. This property claims only that there *exists* a $p$ and (for every string of length at least $p$) a partition satisfying some conditions - if you choose an arbitrary value of $p$ and an arbitrary partition, the pumped strings might not be in the language.
> 1 votes

---
Tags: context-free, pushdown-automata, pumping-lemma, context-sensitive, theory
---


# Question
Title: An exercise that asks for informal description of the language accepted by a specific PDA
This is a problem that I have found from *Introduction to automata theory, languages and computation* by John Hopcroft and Jeffrey Ullman. PDA P=({q0, q1, q2, q3, f)}, {a, b}, {Z0, A, B}, δ, q0, Z, {f}) has the following rules defining δ:

```
δ(q0,a,Z)=(q1,AAZ)
δ(q0,b,Z)=(q2,BZ)
δ(q0,∈,Z)=(f,∈)

δ(q1,a,A)=(q1,AAA)
δ(q1,b,A)=(q1,∈)
δ(q1,∈,Z)=(q0,Z)

δ(q2,a,B)=(q3,∈)
δ(q2,b,B)=(q2,BB)
δ(q2,∈,Z)=(q0,Z)

δ(q3,∈,B)=(q2,∈)
δ(q3,∈,Z0)=(q1,AZ)

```

Note that since each of the sets above has only one choice of move, we have omitted the set brackets from each of the rules.

It has been asked to informally describe L(P). After observing, it seems to me that in case the string started with a, no prefix should contain more b's than twice the number of a's and in the string, number of a's * 2 = number of b's. Am I wrong about this particular description? How can I informally describe the language that the PDA accepts?

# Answer
The language of this PDA seems to be the set of all strings that have twice as many $b$'s as $a$'s.

If there is a deficit of $a$'s in the prefix seen so far in the sense that the number of $b$'s exceeds twice the number of $a$'s, then the PDA would be operating essentially from state $q\_2$, where it would modify the number of $B$'s on the stack. In this state, the PDA would remove two $B$'s for each $a$ it sees in the input and push a $B$ for each $b$ it sees in the input.

If there is a deficit of $b$'s in the prefix seen so far in the sense that number of $b$'s is less than twice the number of $a$'s, then the PDA would be operating essentially out of state $q\_1$, where it would work with the $A$'s that are on the stack: for each $a$ in the input, push two $A$'s onto the stack, and for each $b$ in the input, remove an $A$ from the stack.

Thus, at any given time, the stack contains either all $A$'s or all $B$'s depending on which way the deficit is. The machine needs to deal with these two situations differently: if there is a surplus of $B$'s, then the next input $a$ causes two $B$'s to be popped from the stack, whereas if there is a surplus of $A$'s, the the next input $a$ causes two more $A$'s to be pushed onto the stack.

When the deficit swings from one way to another, the machine transitions from $q\_2$ to $q\_1$ (via $q\_3$) or from $q\_1$ to $q\_2$ (via $q\_0$).
> 1 votes

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


# Question
Title: What exactly is pumping length in pumping lemma?
**Pumping Lemma** : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^\*$, such that $x = uvw$, and

1. $|uv| \leq n$
2. $|v| \> 0$
3. $uv^iw ∈ \mathbb{L} \space\forall i\geq0$

My question is, what exactly is the "*Pumping Length*" $n$ here? While proving if a language is regular or non-regular, do I have to assume the value of $n$, or do I have to calculate it? If Yes, how to calculate?

# Answer
> 3 votes
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by contradiction.

The idea behind proofs that use the pumping lemma is as follows. To prove a given language $L$ is nonregular, by way of contradiction, assume that $L$ is regular. Then there must be a machine on $n$ states accepting $L$, for some positive integer $n$. You can then show (this is essentially what the proof of the pumping lemma does) that such a machine must also accept other strings, i.e. $L$ must also contain these other strings (these other strings are the pumped strings, which have the form $xy^iz$). However, it can be shown that some of these pumped strings do not belong to the given language, and so we have a contradiction. This contradiction implies that the assumption you started with (that there is a machine with $n$ states accepting $L$) is false, i.e. there is no machine on $n$ states accepting $L$. Since $n$ was chosen to be arbitrary, you've shown that there does not exist a machine on any number of states accepting $L$, i.e. there does not exist a machine accepting $L$.

# Answer
> 2 votes
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.

Your finite automata can have (in effect) a lookup table, and decide where each string goes (accepted or not accepted).

But, you cannot make an infinite lookup table. The program/machine/expression for recognizing regular languages only has so much state. How much state isn't known -- because you can make really, really large finite automata -- so we cannot fix an "n" that works for all machines.

Instead, it is saying that *for every fixed finite automata*, there is a length of string long enough that the finite automata cannot maintain an arbitrary lookup table. As we don't know how big the automata is, we don't know how long this string has to be.

You could write an algorithm that takes a given regular language (assuming it is described reasonably) and produces the point where it cannot hope to maintain a lookup table. As an example: if your recognizing machine was a finite automata description, once your string is longer than the number of states in the finite automata, it must have formed a loop (visited a state twice).

If we break the recognized string into 3 parts (the part before we start the loop, the part that walks the loop, and the part afterwards), we can *repeat the loop* part of the string any number of times.

But in this proof, and in general, we don't have the finite automata.

But we do know *if the language is regular*, then such an "n" exists.

So when proving a language non-regular, if you can prove that *for every single n*, the pumping lemma doesn't hold *for any string* of your choice, you win.

On the other hand, if you prove the pumping lemma holds for given string in the language, that does not prove the language is regular.

This kind of mental gymnastics is tricky, honestly.

You can rephrase this as a challenge-response. To prove a language is non-regular, you need to make a proof machine.

This proof machine must accept a value "n". It must then produce a string x with |x| \> n.

Then it must accept *any subdivision* of x into uvw with |v| \> 0 and |uw| \<= n. From that, it has to prove that uv^iw is not in the language.

The choice of "n" and the "uvw" are *hostile*, not something you get to pick. Your "proof machine" must work regardless of what values it is challenged with.

If you can do this, you have proven the language is non-regular.

# Answer
> 1 votes
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the language. You do not however need to know its exact value, it must exists if the language is regular.

You can read it in the proof of the pumping lemma .

# Answer
> 0 votes
A regular language has a finite state machine, and therefore it has a finite state machine with a minimum number of states n. If we examine the first n letters of an input string, there are n+1 states that we encountered after 0, 1, 2, …, n letters. Since there are no n+1 states, there must be a state S that we encountered after x letters and after x \< y \<= n letters, so in the state S the next y-x letters brought us back to the same state S. Whether we parsed those letters 0, 1, 2, or any number of times, we go back to the same state S.

And if you look carefully, that’s exactly what the pumping Lemma says. The pumping length is any number the number of states in the smallest finite state machine for the language. (Except that we don’t greater than that number of states, and we usually use the pumping Lemma to show that the language is irregular and therefore the number of states and the pumping length don’t exist).

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


# Question
Title: Shannon's result that some Boolean functions require exponential circuits
In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see \[1\] and many texts on computational complexity. This result has been strengthened later, showing that, in the limit, almost all boolean functions have exponential circuit complexity. It is often said that, even in 2022, we still cannot construct a single example of such a function. I'm interested in, and slightly confused about, the state-of-the-art in research on this question. In particular:

* Wikipedia \[2\] states that *"complexity theorists have only been able to prove superpolynomial circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate"* which seems to contradict that *no* explict function is know.
* Are there any candidate boolean functions (or family of functions) that are conjectured to have exponential circuit complexity, but where this has not been proven?
* What is the state of exhaustive exploration of the circuit complexity of $n$-ary boolean functions? Presumably there is some small $n$ such that this complexity has been computed for all $i\<n$?

---

1. C. E. Shannon, *The synthesis of two-terminal switching circuits* https://ia802700.us.archive.org/6/items/bstj28-1-59/bstj28-1-59.pdf
2. Wikipedia entry *Circuit complexity* https://en.wikipedia.org/wiki/Circuit\_complexity#History

# Answer
> 3 votes
The best known lower bounds for *explicit* functions are $\Omega(n)$. The only superpolynomial lower bounds are in restricted models of circuits, such as monotone circuits and bounded-depth circuits.

NP-hard problems are expected to have exponential circuit complexity $2^{n^{\Omega(1)}}$; this is a non-uniform version of the Exponential Time Hypothesis.

Since there are $2^{2^n}$ functions on $n$ bits, I doubt that even for $n = 5$ it is feasible to find the maximal circuit complexity exactly.

---
Tags: complexity-theory, reference-request, complexity-classes, circuits, boolean-complexity
---


# Question
Title: Pseudocode for constructing control flow graph
I'm trying to build a complexity analysis tool and I need an algorithm for constructing the control flow graph (to get cyclomatic and eventually essential complexity). I couldn't find any pseudocode online so I just got down to writing it. Using recursion seems to have been a bad way to go; my code handles most simple cases but with deeper nesting of control structures errors arise.

Is there somewhere I can find pseudocode for constructing the CFG?

(For the curious I'm doing this for VHDL.)

# Answer
> 1 votes
To create a CFG you begin with an Abstract Syntax Tree (AST). So I assume you have an AST available. The first step is to collect the nodes in the tree into basic blocks. This step is optional but reduces the number of nodes in the CFG which improves performance. So if you have the source code:

```
if a:
    x = x + 1
    print(b)
else:
    while c:
        print(d)
    y = y + 1

```

you get a tree structure of basic blocks (here denoted BB):

```
[(BB(if a:), [
    [(BB(x = x + 1, print(b)), [])]
    [(BB(while c:), [
        (BB(print(d)), [])
    ]), (BB(y = y + 1), [])]
])]

```

Note that the if-statement has two children lists and the while-statement has one. Note also that every successor of a block is either the first element in a children list or "follows" the block. Thus,

```
succ(BB(while c:)) = [BB(print(d)), BB(y = y + 1)]

```

cause the first block is the body of the loop and the second block the block reached after exiting the loop.

Given the tree above, we can create a recursive algorithm that computes the successors of every block:

```
def connect(tree, parent):
    tails = [parent] if parent else []
    for bb, children in tree:
        for t in tails:
            succ[t].append(bb)
        if type(bb) == if-block:
            if_tails = connect(children[0], bb)
            else_tails = connect(children[1], bb)
            tails = if_tails + else_tails
        elif type(bb) == while-block:
            tails = connect(children[0], bb)
            for t in tails:
                succ[t].append(bb)
            tails = [bb]
        else:
            tails = [bb]
    return tails

```

The "tails" are the predecessors of the next block to operate on. The algorithm becomes a bit hairier when you involve other kinds of control flow like continue, break, and exceptions.

---
Tags: programming-languages, software-testing, logic-programming, static-analysis
---


# Question
Title: Complexity of finding $d$ largest eigenvectors of a symmetric matrix
I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now we're interested in finding $d$ largest eigenpairs, but for a "symmetric" matrix. What is the time complexity of this algorithm and what is the name of the algorithm? My guess is this would take $O(dn^2)$ just because we need to perform the original method $d$ times. But, I think it's be faster if we assume the matrix is symmetric. Thanks in advance!

# Answer
The power method takes $O(n^2)$ time *per step*. It is an iterative algorithm, and convergence is geometric. The absolute speed of convergence depends on the ratio between the two largest eigenvalues.

The usual generalisation of the power method to the top $d$ eigenpairs is the Lancosz algorithm, if the matrix is positive definite. There are also algorithms with similar convergence properties that find an eigenpair whose eigenvalue is close to a desired value, such as LOBPCG.
> 1 votes

---
Tags: algorithms, time-complexity, matrices, linear-algebra
---


# Question
Title: Time complexity when taking certain elements and iterating over them?
I'm trying to gain a better understanding of Big O.

Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating over each element from this array gives O(n) as we are looping over the array N times.

Now we do the same thing, we iterate over the array N times but only store, for example the number 3 from the array, into another array. Which we then loop over that array. What would the full equation for this algorithm or is it the case that the final result will always be O(n) and so we can completely ignore the rest?

Example:

```
firstArray = [1,1,1,2,2,2,2,3,3,3,6,7,8]
secondArray = []
for i=0 to firstArray.length()
   secondArray.add(firstArray[i])

for i=0 to secondArray.length()
   secondArray[i] += 10
   print(secondArray[i])

```

What confuses me is how we represent the second array, as it can be different each time the code is executed.

# Answer
In doing running-time analysis, we often assume the worst-case. That is, what scenario will lead to the maximum possible running-time. As for your question about the second array, you can assume that in the worst-case, everything from the first array was transferred to the second array. That is, in the worst-case the second array has $n$ elements. In your example, assume that all indices of the first array contains the element 3, thus everything will transferred. However, note that the running-time of the second loop, will depend on what you are doing inside.

As for the total running-time of the two loops, you can add up the time taken by the first loop and the second loop, again assuming the worst-case.

As a final note, it is important that you also understand the cost of the `add` operation in the first loop. It is often expensive to insert a new element at the beggining of the array since that would require moving all elements already in it, which will lead to an $O(n^2)$ total time for the first iteration, in such case. This can be improved, if you insert elements at the end instead, so no elements are moved, which will guarantee an $O(n)$ total running-time for the first loop.
> 2 votes

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


# Question
Title: Small doubt in vulnerable time of CSMA/CD and pure aloha
I understand that vulnerable time is the time when collision is possible.

In CSMA/CD, the vulnerable time is Tp because it takes Tp time for bit to travel from source to destination and collision might occur during that time.Here Tp is propagation delay.

Even in pure aloha, I understand how is vulnerable time 2\*Tt time is derived. Here Tt is transmission time.

My doubt is why don't we add or consider Tp time in pure aloha and Tt time in CSMA/CD when calculating vulnerable time. Why are we ignoring it ?

# Answer
Tp is same as Tt for pure aloha Tfr is also same as Tt
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Determining if an NFA accepts an infinite language in polynomial time
Can we determine in polynomial time if the language accepted by an NFA is infinite?

The case of DFA is simple, but converting an NFA to a DFA may take exponential time. Also, I ran into this post, Determine if an NFA accepts infinite language in polynomial time. But there is no solution.

# Answer
> 8 votes
Since $\epsilon$-transitions can be removed in polynomial time, let us assume for simplicity that the NFA does not contain any $\epsilon$-transitions (though the argument can be modified to accommodate them).

Suppose that the NFA contains $n$ states, and denote by $L$ the language it accepts. If $L$ is infinite then it contains some word $w$ of length at least $n$. An accepting path of $w$ necessarily passes through the same state twice. This means that there are three states $q\_i,q,q\_f$, where $q\_i$ is initial and $q\_f$ is final, and paths $q\_i \to^\* q$, $q \to^+ q$, and $q \to^\* q\_f$ (the second one should be non-empty). Conversely, if such states exist, then $L$ is infinite. You can determine whether such states exist in polynomial time, since reachability is in polynomial time.

# Answer
> 6 votes
An NFA (with $\epsilon$-moves or not) can be viewed naturally as a directed multi-graph. We will use "state" and "node" interchangeably.

Whether an NFA accepts an infinite language is the same as whether there is a path from the initial state to an accepting state that contains at least one state that is a part of a cycle. Here **we consider a self-loop as a cycle**. See Yuval's answer for a simple proof.

#### An algorithm in polynomial time

A DFS from the initial state can determine all states that are reachable from the initial state.
A DFS from each state can determine whether the NFA can reach an accepting state from that state.
For each state, we can use a depth-first-search (DFS) to determine whether it is a part of a cycle.
If there is a state which is reachable from the initial state and from which the NFA can reach an accepting state and which is a part of a cycle, the answer is Yes. Otherwise, the answer is No.

#### An algorithm in linear time

For every ordered nodes $s\_1$ and $s\_2$ in the directed multi-graph, we can replace all edges from $s\_1$ to $s\_2$ by a single edge from $s\_1$ to $s\_2$, which transforms the directed multi-graph into a directed graph without multi-edges (with self-loops possibly). This transformation does not affect paths nor cycles.

Call the transformed graph $H$.

A DFS on $H$ from the initial state can mark all reachable accepting states. Another DFS on $H$ starting from an additional node, "the super-accepting state" that is connected from all accepting states, treating each edge backwards, can mark all states from which the NFA can reach an accepting state. A state is marked by both DFS iff there is a path from the initial state to an accepting state that contains that state.

A state is a part of a cycle iff it is a part of a cyclic strongly connected components (SCCs). An SCC is called cyclic if it contains a cycle, i.e., if it contains either a self-loop or more than one node. We can adapt easily any one of common linear-time algorithms that find all SCCs to find all cyclic SCCs with the same time-complexity.

If there is a state that is marked by both DFS and is part of a cyclic SCC, the answer is Yes. Otherwise the answer is No.

Since each of the transformation, both DFSs, the adapted SCC-finding algorithm and the final check runs in linear time, the entire algorithm runs in linear time.

---
Tags: regular-languages, finite-automata, polynomial-time, infinity
---


title: Knapsack with quadratic constraint

text:
# Question
Title: Knapsack with quadratic constraint
Suppose I have a variant of the knapsack problem:

$$\max\_{x} \sum\_{i=1}^n v\_ix\_i$$

$$(\sum\_{i=1}^n w\_ix\_i - W)^2 \leq k$$

for $v\_i, w\_i \in \mathbb{R}$, $x\_i \in \\{0,1\\}$ and $k \in \mathbb{R}, k \> 0$.

Is it known if the decision problem $\sum\_{i=1}^n v\_ix\_i \> V$ for some $V$ is NP-Complete?

# Answer
> 0 votes
The problem is clearly in $\mathsf{NP}$. You can see that it is $\mathsf{NP}$-hard by a reduction from subset sum: given a set $X = \\{ x\_1, \dots, x\_m \\}$ of positive integers and another integer $T\>0$, is there a subset $S$ of $X$ such that $\sum\_{x \in S} x = T$?

To reduce to your version of subset sum, create $n=m$ items, where the $i$-th item has value $v\_i = 1$ and weight $w\_i=2x\_i$, and set $W=2T$, $k=1$, $V=0$. There is a solution to this "knapsack" instance if and only if there is a solution to the subset sum problem.

---
Tags: np-complete, np-hard, decision-problem, knapsack-problems
---


# Question
Title: How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
We know that $L = \\{ xy | x, y \in (0 + 1)^\*, |x| = |y|, x≠y\\}$

is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by checking one $0$ against three $1s$ but how can we check $x ≠ y?$

# Answer
> 9 votes
If two strings $w\_1, w\_2$ of the same length are different from each other, then you can find a specific position where they differ:

$$w\_1 = \underbrace{\square\ldots \square}\_{k\text{ symbols }}\\;x\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}$$

$$w\_2 = \underbrace{\square\ldots \square}\_{k\text{ symbols }}\\;y\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}$$

$$x\neq y$$

You may already know the trick that when you concatenate the two strings, you can re-subdivide them:

$$w\_1w\_2 = \underbrace{\square\ldots \square}\_{k\text{ symbols }}\\;x\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}\\;|\\;\underbrace{\square\ldots \square}\_{k\text{ symbols }}\\;y\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}$$

$$w\_1w\_2 = \underbrace{\square\ldots \square}\_{k\text{ symbols }}\\;x\\;\underbrace{\square\ldots\square}\_{k\text{ symbols }}\\;|\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}\\;y\\;\underbrace{\square\ldots\ldots \square}\_{\ell\text{ symbols }}$$

You can do this because the $\square$ symbols can be anything. When you divide them this way, you can more easily see how a context free grammar can recognize the language.

---

Based on this trick, here is a definition of a PDA to recognize the language. 1. The PDA has four states, $P$, $Q\_0$, $Q\_1$, and $R$. The initial state is $P$.
2. When in state $P$, the machine will nondeterministically guess the position $k$ where the two strings differ.

Specifically, in state $P$ the machine may read a character from the input (ignoring it), and push the symbol $A$ onto the stack. It may do this as many times as it likes.
3. When in state $P$, the machine may decide that it will inspect the character in the current position. It reads the character at the current input (what I called $x$ above). If it reads $x=0$, the machine transitions to state $Q\_0$. If it reads $x=1$, the machine transitions to state $Q\_1$ instead.

**In this way, the machine uses its finite state to remember the value of $x$ for later**.
4. When in state $Q\_0$ or $Q\_1$, the machine first consumes $k$ characters of input. Specifically, it pops the symbol $A$ from the stack and consumes one character of input (ignoring it) until the stack is empty. (If it runs out of characters, the computation fails because the value of $k$ was invalid.)
5. Next, while in state $Q\_i$, the machine nondeterministically guesses the value of $\ell$. As before, it does this by consuming one character of input (ignoring it) and pushing $B$ onto the stack. It may repeat this process any number of times.
6. When in state $Q\_i$, the machine may decide that it will inspect the character in the current position. It reads the character at the current input (what I called $y$ above).

If it is in state $Q\_0$ and reads $y=1$, we've found a mismatch! If it is in state $Q\_1$ and reads $y=0$, we've found a mismatch!

Otherwise, there is no mismatch at the chosen position. The machine should fail.
7. If the machine finds a mismatch, let it transition to state $R$. In state $R$, it should remove all the $B$ symbols from the stack, consuming one character from the input for each one. At the end of this process, it should be exactly at the end of the string and the stack should be empty. (If not, it has picked invalid values for $k$ and $\ell$.)
8. Overall, if $w\_1$ and $w\_2$ are different strings of the same length, one of the nondeterministic guesses of this machine will succeed, so the overall PDA will accept. Otherwise, all of the branches will fail, and the PDA will reject. This is the desired behavior.

# Answer
> 0 votes
I understand the @user326210 algorithm and on basis of my understanding I design the below NPDA.

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


# Question
Title: Are all CPU computations done using registers?
From my understanding, a CPU register is a temporary storage or working location built into the CPU itself. The CPU includes some functional units such as the ALU (which is part of the chip, as far as I know).

In a 64 bit architecture, we have 16 general purpose registers, that seem to be often used in ASM programs to store temporary values. Going from high to low level, a program is translated to machine code and interpreted by the computer, that executes the instructions.

But if every operation is a kind of arithmetic one, **are all of them done using these general purpose registers**, taking into account that programs generally need some kind of "temporary" storage for their calculations to be performed? Are they kind of "buffers" for **every** mathematical operation the CPU needs to calculate?

Do every computation in a CPU needs to be done using registers to place values?

# Answer
Yes and no.

Ignoring special-purpose CPUs (e.g. stack machines, which still matter), most instruction set architectures (ISA for short) fall into one of two fuzzy categories:

* Load/store architectures, such as ARM, have separate memory instructions (i.e. loads and stores) and ALU instructions.
* Register-memory architectures, such as Intel x86, have ALU instructions that can take a memory location as an operand. Note that the more recently-designed parts of Intel's ISA, such as SSE, follow the load/store approach more closely.

The way that CPUs work internally is more complex. Modern CISC CPUs such as Intel tend to translate programmer-visible instructions into lower-level operations that are more load/store in nature; Intel calls these "micro-ops", or uops for short. This may require "extra" temporary registers, but register renaming means that this is probably also true of the general-purpose registers that a programmer sees.
> 2 votes

# Answer
First, there are many more registers in a modern CPU than the ones that are visible to the program. Your iPhone has about 500 of each type of register per CPU; they are needed to perform out-of-order execution so you don’t have to wait forever for registers to become available.

Second, arithmetic is not performed with registers. Instead the contents of registers are moved to the arithmetic units, processed there, and the results are moved back to registers. Each arithmetic unit can perform all kinds of different operations. Otherwise, you would have an adder, a multiplier, a bit shifter and so on connected to every pair of registers.
> 0 votes

---
Tags: computer-architecture, cpu, memory-hardware, memory-access, assembly
---


title: Shortest word not in dynamic set

text:
# Question
Title: Shortest word not in dynamic set
What is the most efficient data structure for a dynamic set of words over a finite alphabet $\Sigma$ which supports the following operations?

* Add a word.
* Remove a word.
* Determine a shortest word which is not in the set.

Does it help if all words have the same length?

**A real world example:** I was thinking about link shorteners (e.g. https://bitly.com/) and how they search for available short codes.

# Answer
Link shorteners don't face this problem. When they generate a word for you, they use a fixed-length words, so it suffices to keep a dictionary of all words that are currently in use. Also most words are not in use, so for their purpose it suffices for them to pick a random word, check that it is not in use, and if it is, repeat.

If you actually needed to face this problem, probably a reasonable approach is to have a separate dictionary for each length, where the dictionary for length $\ell$ keeps track of the words of length $\ell$. Each dictionary could be stored, for instance, as a trie (where each node of the trie is augmented with the number of leafs found underneath that node); then it is easy to find a word that is not in the dictionary in $O(\ell)$ time. You can also keep track of all lengths that are missing at least one word, in a self-balancing binary tree, which makes it easy to find in logarithmic time the length of a shortest word that is not in the set (I recommend you maintain a pointer from each dictionary to its corresponding leaf in this tree, and vice versa). Putting all of this together, all operations can be implemented in $O(\ell)$ time, plus a term that is logarithmic in the total number of different lengths.
> 3 votes

---
Tags: data-structures
---


title: Finding a DFA for concatenation

text:
# Question
Title: Finding a DFA for concatenation
Consider a deterministic finite automaton $M(k) = (Q, Σ, \delta, 0, F)$, with $k ≥ 2$ and

$Q = \\{0,1,...,k-1\\}$

$Σ = \\{0,1\\}$

$\delta(q,a) = (q+a) \space mod \space k$

$F = \\{0\\}$

If $L$ is the language recognised by $M(k)$, describe a deterministic finite automaton that recognises the concatenation $L ⋅ L ⋅ L ⋅ L ⋅ L ⋅ L ⋅ L$

Is there a way of doing it without converting it into 7 NFAs, joined by epsilon transitions, and then converting that back into a DFA using the power set construction?

# Answer
Looks like a trick question. $L^7 = L$, so you already have a DFA for it.

The words in $L$ are those where the symbol $1$ occurs a multiple of $k$ times. If you concatenate seven of them, the total number of $1$ symbols is still a multiple of $k$. So $L^7 \subseteq L$. On the other hand, $\epsilon \in L$, so you have $L \subseteq L^7$ because for a word in $L$, you can just add six $\epsilon$ to it.
> 4 votes

# Answer
It would be the case that $L = L^i$, for $i \ge 1$ (in your case $i=7$).

Say you have a DFA $M\_i$ for $L^i$. We prove that $w$ is accepted by $M\_i$ if and only if $w$ is accepted by $M$.

* **If $w$ is accepted by $M\_i$ then $w$ is accepted by $M$.** Observe that once a string is accepted by $M$, $M$ must be at the start state. Now, it must be that $w$ can be divided into $i$ substrings, where each substring can be accepted by $M$. When $w$ is given as input to $M$, we can think of it as if $M$ is consuming each substring then reseting back to the start state.
* **If $w$ is accepted by $M$ then $w$ is accepted by $M\_i$.** Since the start state of your DFA is also the final state, it accepts the empty string. Think of $w$ as if it is divided into $i$ substrings where the first substring is $w$ itself and the rest are empty strings.
> 2 votes

# Answer
It turns out that the same DFA given for $L$ also accepts the language $L^7$ because $L=L^7$. Note that while a DFA $M$ can accept many strings, it accepts only one language, called the language accepted by $M$, and denoted $L(M)$. It was possible for the given DFA to accept both $L$ and $L^7$ because these two languages are the same. Both $L$ and $L^7$ are subsets of $\\{0,1\\}^\*$, so the equality in $L=L^7$ refers to set-theoretic equality.

For concreteness, we can work out the solution for $k=3$; the same solution method works for arbitrary $k$.

Let the machine $M$ be the DFA that has three states $q\_0, q\_1, q\_2$. The start state is $q\_0$ and the set of final states is $\\{q\_0\\}$. There are three transitions with label $1$: a transition from $q\_0$ to $q\_1$, a transition from $q\_1$ to $q\_2$, and a transition from $q\_2$ to $q\_0$. This completes a directed cycle of length $3$. Draw a transition from each state to itself with label $0$. Observe that when you start at state $q\_0$, go around to the next state in the cycle for each input symbol $1$, and return to the starting point, the number of $1$'s in the input string would have been a multiple of $3$. Thus, you can convince yourself that the language $L:=L(M)$ accepted by the machine $M$ is the set of all binary strings whose number of $1$'s is a multiple of $3$. Thus, $L = \\{\epsilon, 0, 00, 000, 111, 1101, \ldots\\}$, where $\epsilon$ is the empty string in $\\{0,1\\}^\*$. Note that the empty string $\epsilon$ is accepted by $M$ because the start state of $M$ is one of its final states.

We claim that the given DFA $M$ also accepts the concatenation language $L^7$, i.e. that $L(M) = L^7$. To prove this, we prove that $L=L^7$, by showing set inclusion in both directions. To show $L \subseteq L^7$, let $w \in L$. Since $L$ contains the empty string $ \epsilon$, $w=w \epsilon \epsilon \epsilon \epsilon \epsilon \epsilon \in L^7$.

To prove the reverse inclusion $L \supseteq L^7$, consider any string $w=w\_1 w\_2 \ldots w\_7 \in L^7$, where $ w\_i \in L, \forall i$. Because the number of $1$'s in each $w\_i$ is a multiple of $3$, the number of $1$'s in $w$ is also a multiple of $3$. Hence, $w \in L$, as was to be shown. This proves (for the special case $k=3$) that $L=L^7$ and hence the language accepted by the given DFA is $L^7$.

It should be clear that this solution method works for any $k \ge 2$ \- just replace the directed $3$-cycle in the DFA above with a directed $k$-cycle.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Language of Turing machines that go through some configuration infinitely many times on empty input
I've been going through some questions on old homework. Here was a question that confused me somehow.

***Question:*** Given a language $$L=\\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ goes through some configuration } (q,s,i) \text{ infinite times on input } \epsilon\\}$$ determine whether it's decidable, if not then determine if it's Turing-acceptable.

A configuration of $M$ is a triple $(q, s, i)$, where $q$ is the state, $s$ the tape (with its content), and $i$ the location of the head.

I was required to prove / refute whether $L\subseteq L'$ for $L'=\\{\langle M\rangle\ |\ M \text{ does not halt on input } \epsilon\\}$ so I refuted it by giving a Turing machine:

I don't know if this has something to do with a mapping function for the coming sections.

# Answer
> 3 votes
No, $L$ is not decidable.

***Summary*** (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will record all $T$'s configuration history on the tape. $U$ will check whether there is one configuration repeated at least once after each simulation step. If there is, $U$ will instead move to the right always. Moreover, if $T$ halts, then $U$ will move left and right alternately. We can see that $T$ halts on empty input iff $U\in L$. Hence $L$ is undecidable.

***Proof by contradiction***

Given a Turing machine $T$, we will construct another Turing machine $U$ algorithmically so that $U$ is in $L$ iff $T$ halts on empty input, in the next section, "Construction of $U$ from $T$".

If $L$ is decidable, i.e., we can decide whether $U$ is in $L$, then we can decide whether $T$ halts on empty input, i.e., the HALT problem on empty input is decidable. However, the HALT problem on empty input is not decidable. That means the assumption "$L$ is decidable" is wrong. So $L$ is undecidable.

(This technique is called Turing-reduction that you might have learned or you will learn.)

Now the problem is how to construct such a $U$.

***Construction of $U$ from $T$***

We can view $T$'s actions upon empty input as a sequence of transitions from configuration $c\_k=(q\_k, s\_k, i\_k)$ to $c\_{k+1}=(q\_{k+1}, s\_{k+1}, i\_{k+1})$ for $k=0,1,2,\cdots$, where $c\_0$ is the initial configuration and $k$ may or may not goes to infinity.

Given empty input, $U$ will simulate $T$ in the following way. The illustration below is what the tape looks like before and after simulating $T$ for $m$ steps, usually, where block $b\_k$ encodes $c\_k$. $$\begin{aligned} \text{before: }\ &\underbrace{\overline\sqcup\sigma\_0}\_{b\_0}\\#\\# \underbrace{0\overline\sqcup\sigma\_1}\_{b\_1}\\#\\# \underbrace{\overline01\sigma\_2}\_{b\_2}\\# \underbrace{\overline\sqcup11\sigma\_3}\_{b\_3}\\#\\#\cdots\\#\\# \underbrace{\cdots1\overset{\downarrow}{0}0\cdots}\_{b\_{m-1}}\\ \text{ after: }\ &\underbrace{\overline\sqcup\sigma\_0}\_{b\_0}\\#\\# \underbrace{0\overline\sqcup\sigma\_1}\_{b\_1}\\#\\# \underbrace{\overline01\sigma\_2}\_{b\_2}\\# \underbrace{\overline\sqcup11\sigma\_3}\_{b\_3}\\#\\#\cdots\\#\\# \underbrace{\cdots1\overline{0}0\cdots\sigma\_{m-1}}\_{b\_{m-1}}\\#\\# \underbrace{\cdots11\overset{\downarrow}{0}\cdots}\_{b\_{m}} \end{aligned}$$ The symbol $\sqcup$ is the tape blank symbol. The extra symbol $\\#$ is a block separator. $\sigma\_k$ is a tape symbol that represents the state $q\_k$. In each block $b\_k$ except the rightmost block, there is a unique symbol that has a bar on it; that symbol marks the location of $T$'s head at configuration $c\_k$. In the rightmost block, the arrow above one of the symbols indicates the current head position of $U$. (While that bar is a part of each "barred symbols" on the tape, that arrow is not. The arrow just to indicate the head position of $U$. Similarly, those underbraces with $b\_k$ are not part of the tape. They are used to group the symbols)

For the $m$-th step taken by $T$, $U$ will change its tape from "before" to "after" as follows.

1. mark the current head location by adding a bar to the current tape symbol,
2. append $\sigma\_{m-1}\\#\\#$ to the right of the current block $b\_{m-1}$, which is also the rightmost block, where $\sigma\_{m-1}$ is the current state of the simulated $T$.
3. append a copy of $b\_{m-1}$ to the right, which becomes the new rightmost block. Remove the rightmost symbol $\sigma\_{m-1}$.
4. Move head to unique cell with a tape symbol that has a bar at the rightmost block. Remove the bar. Simulate $T$'s action.

With the steps above, $U$ simulates $T$ with $T$'s computation history $c\_0, c\_1, c\_2, \cdots$ preserved as well.

Furthermore, between step 2 and step 3, $U$ will also perform step 2' as below.
$\quad$2'. Check whether there is one configuration that has been repeated by $T$. This is possible since $U$ preserves the full computation history of $T$. If a repetition is found, $U$ will always moves to right regardless of the content of the tape (so no other kinds of actions can be taken by $U$ any more).

Furthermore, after step 4, if the simulated $T$ halts, $U$ will move left or right alternately forever. (so no other kinds of actions can be taken by $U$ any more). In particular, $U$ will repeat one of its own configurations infinite times.

On input other than the empty word, $U$ will halt immediately.

**Claim**: $U\in L$ $\iff$ $T$ halts on empty input.
**Proof**:
"$\impliedby$": This is straightforward by the construction of $U$.
"$\implies$": If $T$ does not halt, either it never repeat its configuration or repeat one configuration at least twice. In the former case, $U$ will write more and more blocks. In the latter case, $U$ will always move right after some time. In both cases, $U$ cannot repeat any configuration infinite times.

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


# Question
Title: Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?
I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2. Set cover problem with sets of size 2

The solution described involves constructing an Edge Cover for a slightly different graph (Create a graph of keys and each edge links the keys of a subset).

Can we still solve it in polynomial time if there are some subsets of size 1 along with the subsets of size 2? I am unable to come up with a formulation for this.

# Answer
> 3 votes
**Solution 1**

Given an instance $\Pi$ of set cover with non-empty subsets of size at most 2, consider two instances of set cover with subsets of size exactly 2:

* $\Pi'$ contains all subsets in $\Pi$ of size exactly 2.
* $\Pi''$ contains all subsets in $\Pi$ of size exactly 2, and in addition, for each singleton $\\{x\\} \in \Pi$, the subset $\\{x,z^\*\\}$, where $z^\*$ is a new element (the same element is used for all singletons).

If an optimal solution for $\Pi$ doesn't use any singletons, then it will also be an optimal solution for $\Pi'$. Otherwise, it will be an optimal solution for $\Pi''$.

---

**Solution 2**

Let $\Pi$ be an instance of set cover with non-empty subsets of size at most 2. Say that a singleton $\\{x\\} \in \Pi$ is *covered* if $\Pi$ contains some set $\\{x,y\\}$. Any solution for $\Pi$ which uses $\\{x\\}$ could instead use $\\{x,y\\}$, so we can remove all covered singletons from $\Pi$. All singletons that remain in $\Pi$ must participate in any set cover, so we can set them aside, obtaining an instance $\Pi'$ in which all subsets have size exactly 2. Given an optimal solution for $\Pi'$, we obtain an optimal solution for $\Pi$ by adding all uncovered singletons that we had set aside.

---
Tags: algorithms, np-complete, np, matching, set-cover
---


# Question
Title: Myhill–Nerode equivalence classes for the language $b^ia^{5j}$
I have to find equivalence classes for different languages based on Myhill-Nerode. I'm struggling a little bit finding these equivalence classes; for example, the language $L=\\{b^\*a^n\mid n≡0\pmod5\\}$ with alphabet $\\{a,b\\}$.

My first solution would be: $\[\epsilon\],\[b^∗\],\[b^∗a\],\[b^∗aa\],\[b^∗aaa\],\[b^∗aaaa\]$.

Would these be the correct classes? If not, i would appreciate any help!

# Answer
In order to check that these are the correct classes, you need to check three things:

1. Any two words in the same class are equivalent.
2. Any two words in different classes are inequivalent.
3. Every word belongs to one of the classes.

Good luck!
> 2 votes

# Answer
The Myhill-Nerode relation with respect to a given language $L \subseteq \Sigma^\*$ is an equivalence relation on $\Sigma^\*$ and hence gives a partition of $\Sigma^\*$. Because this is a partition, the equivalence classes must be pairwise disjoint and their union must be all of $\Sigma^\*$. Two strings $x, y \in \Sigma^\*$ belong to different equivalence classes if and only if there is some string $z \in \Sigma^\*$ that is a distinguishing extension of $x$ and $y$ in the sense that exactly one of $xz$ and $yz$ belongs to $L$.

When an equivalence class is written as $\[x\]$, the string $x \in \Sigma^\*$ has been chosen as the representative element for this class. Thus, when you write $\[\epsilon\]$, that's the equivalence class represented by the empty string $\epsilon$. But your notation $\[b^\*\]$ is not clear because $b^\*$ is a set (rather than a single string) and denotes the set of all strings that contain zero or more $b$'s. Perhaps you meant the equivalence class $\[b\]$. As shown in the next paragraph, the empty string $\epsilon$ and the string $b$ must belong to the same equivalence class, so your solution that puts $\[\epsilon\]$ and $\[b\]$ as different equivalence classes is incorrect.

Let $L = \\{b^i a^{5j}: i \ge 0, j \ge 0\\}$. We now show that $\epsilon z \in L$ if and only if $bz \in L$, for all $z \in \Sigma^\*$. (a) Suppose $z \in \Sigma^\*$. If $\epsilon z \in L$, then $z = b^i a^{5j}$ for some $i \ge 0, j \ge 0$, whence $b z = b^{i+1}a^{5j} \in L$. (b) Conversely, suppose $bz \in L$. Then $bz = b^i a^{5j}$ for some $i \ge 1, j \ge 0$, whence $z = b^{i-1} a^{5j}$, where $i \ge 0, j \ge 0$. Hence, $\epsilon z = z \in L$. It follows that $\epsilon z \in L$ whenever $bz \in L$.

It appears that $\epsilon$ and $a^5$ belong to different equivalent classes because they have $b$ as a distinguishing extension, i.e. $\epsilon b \in L$ and $a^5 b \notin L$. Consider drawing a DFA with seven states that accepts $L$, and for each state $q$, define the subset $L\_q$ to be the set of all strings in $\Sigma^\*$ that take the machine from the start state to the state $q$. The subsets will give a partition of $\Sigma^\*$. Check if the elements in a subset $L\_q$ are pairwise indistinguishable, and that elements in different subsets are distinguishable. If the DFA has a minimal number of states, the subsets would give the equivalence classes. Alternatively, you can construct the equivalence classes by starting with a string $x\_1$, finding all elements indistinguishable from it to get $\[x\_1\]$, then start with a string in $\Sigma^\* - \[x\_1\]$, and find its class, and so on.
> 2 votes

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


# Question
Title: Difference between an exact and Big O Notation for worst case runtime
I'm having a problem with an exercise, I'm supposed to calculate the *exact* worst case runtime and the worst case runtime in *Big O Notation* for a given algorithm.

This is what I'm struggling to understand, I think I know how to recognize what's the runtime using the big O Notation as it's only a nested loop but what is exactly an *exact* runtime?

How am I supposed to calculate it? How would that look like with a simple bubble sort algorithm?

# Answer
Consider the bubble sort algorithm shown below:

```
function sort(A)
    n = A.length
    for i = 1 to n-1
        for j = n downto i+1
            if A[j] < A[j-1]
                swap A[j] with A[j-1]

```

One way to measure the performance of this algorithm is to count the number of swaps performed by the algorithm. For the worst-case input, the number of swaps performed by the algorithm is $(n-1)+(n-2)+\cdots+2+1 = n(n-1)/2$. This is the exact number of swaps performed in the worst-case.

In the worst case, the number of swaps performed by the algorithm is $O(n^2)$. This expression uses asymptotic notation to describe the worst-case performance.
> 0 votes

# Answer
You can’t calculate any runtime except for some very simple model of a CPU. You can calculate the exact number of comparisons, or the exact number of operations moving array elements of a particular implementation of an algorithm, but it’s practically impossible to predict how many seconds or microseconds the algorithm will run for.
> 2 votes

# Answer
If nothing precise was specified, you can enumerate all operations by type, such as addition, comparison, swap... and give a detailed account of their numbers. That assumes the the basic operations take some constant (but unknown) time each.

In practice, you prefer to limit the evaluation to a single type of operation, such that the other operations are performed in at most a proportional amount.
> 0 votes

---
Tags: algorithms, runtime-analysis, big-o-notation
---


# Question
Title: Influence of a variable in composition of Boolean functions
Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$?

To me it seems like influence of a variable in $f \circ g$ is the product of influence of the outer variable in $f$ with the influence of the variable in $g$, but I'm not sure

# Answer
Suppose that $f\colon \\{\pm1\\}^n \to \\{\pm1\\}$ and that $g\colon \\{\pm1\\}^m \to \\{\pm1\\}$ is balanced. The composed function $f \circ g\colon \\{\pm1\\}^{nm} \to \\{\pm1\\}$ is given by $$ (f \circ g)(x) = f\bigl(g(x\_{1,1},\ldots,x\_{1,m}),\ldots g(x\_{n,1},\ldots,x\_{n,m})\bigr). $$ The influence of $x\_{i,j}$ is the probability that if we sample $x \in \\{\pm1\\}^{nm}$ and construct $x'$ by flipping $x\_{i,j}$ then $(f \circ g)(x) \neq (f \circ g)(x')$. This happens if:

1. $g(x\_{i,1},\ldots,x\_{i,m}) \neq g(x'\_{i,1},\ldots,x'\_{i,m})$.
2. $f(y\_1,\ldots,y\_n) \neq f(y'\_1,\ldots,y'\_n)$, where $y\_i = g(x\_{i,1},\ldots,x\_{i,m})$ and $y'\_i = g(x'\_{i,1},\ldots,x'\_{i,m})$.

The first property happens with probability $\operatorname{Inf}\_j\[g\]$.

Since $g$ is balanced, the vector $(y\_1,\ldots,y\_n)$ is uniformly random. Therefore, given that the first property happens, the second property happens with probability $\operatorname{Inf}\_i\[f\]$. In total, $$ \operatorname{Inf}\_{i,j}\[f \circ g\] = \operatorname{Inf}\_i\[f\] \operatorname{Inf}\_j\[g\]. $$

---

Here is a calculational proof. Recall that $$ \operatorname{Inf}\_i\[f\] = \sum\_{i \in S} \hat{f}(S)^2. $$ The Fourier expansion of $f \circ g$ is $$ f \circ g = \sum\_{S \subseteq \[n\]} \sum\_{\substack{T\_i \subseteq \[m\] \\ \text{for all } i \in S}} \hat{f}(S) \prod\_{i \in S} \hat{g}(T\_i) \prod\_{i \in S} \prod\_{j \in T\_i} x\_{i,j}. $$ Since $g$ is balanced, every monomial appears exactly once: $S$ needs to be the set of $i$ indices that appear in the monomial, and for each $i$, $T\_i$ needs to be the set of $j$ indices such that $x\_{i,j}$ appears in the monomial. (If $g$ were unbalanced, then $S$ could be any superset of the set of $i$ indices appearing in the monomial, with $T\_i = \emptyset$ for any $i$ not appearing in the monomial.) Therefore \begin{align} \operatorname{Inf}\_{i,j}\[f \circ g\] &= \sum\_{i \in S} \sum\_{\substack{T\_k \\, \forall k \in S \\ j \in T\_i}} \hat{f}(S)^2 \prod\_{k \in S} \hat{g}(T\_k)^2 \\ &= \sum\_{i \in S} \hat{f}(S)^2 \cdot \sum\_{j \in T\_i} \hat{g}(T\_i)^2 \cdot \prod\_{\substack{k \in S \\ k \neq i}} \sum\_{T\_k} \hat{g}(T\_k)^2 \\ &= \sum\_{i \in S} \hat{f}(S)^2 \cdot \operatorname{Inf}\_j\[g\] \\ &= \operatorname{Inf}\_i\[f\] \cdot \operatorname{Inf}\_j\[g\], \end{align} using $$ \sum\_T \hat{g}(T)^2 = 1, $$ since $g^2 = 1$.
> 2 votes

---
Tags: probability-theory, boolean-algebra
---


title: NFA to recognize the language ${ab}$

text:
# Question
Title: NFA to recognize the language ${ab}$
In Michael Sipser's *Introduction to the Theory of Computation*, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^\*$ to an NFA. It builds up from the smallest subexpression to larger subexpressions until the required NFA is obtained:

My question is: why is the NFA to recognize $\text{ab}$ not a simple 3 state DFA?

# Answer
It is because of the method used for the construction. The NFA that results from the concatenation of the languages of two automata $A\_1$ and $A\_2$ is the juxtaposition of $A\_1$ and $A\_2$ with $\varepsilon$-transitions from the final states of $A\_1$ to the initial state of $A\_2$.

Given the automata for the regular expressions $a$ and $b$, we obtain an automaton for $ab$ with 4 states with this method.

Note that as stated by Sipser, the method is not optimal, but it is easy to apply.
> 2 votes

# Answer
The procedure described in the text is a *systematic method* for converting a regular expression to an NFA. It’s a recipe that works, and so you don’t have to think much to prove that the language of every regular expression is accepted by some DFA. However, the machine obtained in this manner would generally not have the minimal number of states.
> 1 votes

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


title: Show all chains per user

text:
# Question
Title: Show all chains per user
Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it.

You have a chains of reservations from AirBnb:

```
reservations:[
    {user = 1, res_id = 1001, checkin = 100, checkout = 101},
    {user = 2, res_id = 1002, checkin = 104, checkout = 105},
    {user = 1, res_id = 1003, checkin = 101, checkout = 103},
    {user = 3, res_id = 1004, checkin = 104, checkout = 105},
    {user = 3, res_id = 1005, checkin = 105, checkout = 107},
    {user = 4, res_id = 1006, checkin = 106, checkout = 108},
    {user = 4, res_id = 1007, checkin = 108, checkout = 110},
    {user = 4, res_id = 1008, checkin = 108, checkout = 109},
    {user = 4, res_id = 1009, checkin = 110, checkout = 112},
    {user = 4, res_id = 1010, checkin = 109, checkout = 113},
];

```

where all res\_ids are unique and check\_out is always bigger than check\_in for a reservation.

We name a chain something like:

`[checkin = 1, checkout = 3], [checkin = 3, checkout = 5]`.

If there are no two reservations connected then no chain. We are interested only in reservation chains, two or more reservations connected by checkin/checkout. Since check\_out is always bigger than check\_in for a reservation, there will be no cycles.

My task was to find all the chains per user. In the example from above the chains would be:

**Example:** `{ 1: {{1001, 1003}}, 3: {{1004, 1005}}, 4 : {{1006, 1007, 1009}, {1006, 1008, 1010}} }`

In fact, I do not need the users, only the list would work too.

```
{ {1001, 1003}, {1004, 1005}, {1006, 1007, 1009}, {1006, 1008, 1009}}.

```

In case the chains were not overlapping I solved it by using sorting based on checkin and checkout. It worked. However, when the reservations were overlapping I had no idea.

I put here an example where they are overlapping.
I tried using a stack, something similar to the minimum number of knight moves to reach coordinate (x, y) from (0, 0) but with no success as number of top level are not one after the other. Any suggestions?

# Answer
> 1 votes
I am assuming that the question is asking for maximal chains. (It's not too difficult to modify the below procedure to get all possible chains)

Below is the step by step approach.

1. It is trivial to group the the given data by users (can use sorting or a hash table on the user id). Now, we can find the chains for each user separately. (All the next steps are at a per-user level)
2. Map all the checkin and checkout timings (in sorted order) to a list of integers 1,2,....,n. Let us call this **MAPPING**. Let us also store an inverse to this mapping, **TIME**. First mapping can be stored using an hashtable/BST and the inverse mapping can stored using an array.
3. Create a list (of lists) **R** of size n, where **R\[i\]** stores all the reservations with checkin at **TIME\[i\]**.
4. Now create a list (of lists) **L** of size n, where we will store all the chains starting at **TIME\[i\]** in **L\[i\]**.

```
 5. You can fill L by iterating i from end(n) to start(1)
    a. For each reservation res at R[i]:
           for each chain ch at L[MAPPING[res.checkout]]:
               L[i].append({current_res_id,ch})
           if(L[MAPPING[res.checkout]] is empty)
               L[i].append({current_res_id})
    b. Remove all chains at L[i] that are of a smaller length than the largest one at L[i]

```

Now, your maximal chains will be a part of the array L and you should not have much difficulty filtering them out. You can mark the chains that are part of a larger chain during the above procedure and ignore them.

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


# Question
Title: Prove that the language of regular expressions is not regular
I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of it, and then I can rule out the regularity.

# Answer
Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character from all of its words produces a regular language. That isn't very hard to prove.
> 1 votes

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


# Question
Title: Algorithm for generating sorted lists of random floats
More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output is already in sorted order? I found this, but it and everything else I found only generates integer lists. Is there an equivalent for floats and without worrying about repetition?

# Answer
You haven't answered the question about what distribution, so I will assume you want the uniform distribution on \[0,1\].

Yes, this can be done. However, I doubt that the result will be better in practice than just generating $n$ numbers uniformly at random and sorting them.

Based on the order statistics of the uniform distribution, the distribution of the smallest of $n$ numbers from the uniform distribution is known: it has a Beta$(1,n)$ distribution. Also, it is known how to sample from such a distribution.

So, there is a simple algorithm: sample the first number $x\_1$ from the sorted sequence, by generating a random sample from Beta$(1,n)$. Then, sample the second number $x\_2$, by letting $x\_2 = x\_1 + d\_2/(1-x\_1)$ where $d\_2$ is sampled from Beta$(1,n-1)$, and $x\_3 = x\_2 + d\_3/(1-x\_1-x\_2)$ where $d\_3$ is sampled from Beta$(1,n-2)$, and so on.

Why does this work? Well, obviously $x\_1$ has the right distribution. Also, the numbers $x\_2,\dots,x\_n$ can be obtained by sampling uniformly at random from $\[x\_1,1\]$ and sorting, so we can generate them recursively using the same algorithm. Finally, unwinding the recursion gives the above algorithm.
> 1 votes

---
Tags: algorithms, sorting, pseudo-random-generators
---


# Question
Title: Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path can also be deduced by recursively traversing dfs.

# Answer
> 2 votes
I'm not sure what you mean by "deduced by recursively traversing dfs" but the depth-first search tree is, in general, exponentially large in the size of the graph so any algorithm that potentially involves looking at all of it must take exponential time in the worst case.

Indeed, it's not even obvious that you can solve Hamiltonian path using depth-first search. Consider the graph that is a clique plus one extra vertex, which sends one edge to the clique, say to vertex $x$. If you start your depth-first search at $x$, none of the paths explored by the DFS will be Hamiltonian. Further, if you start at any other vertex in the clique, you might have to explore something like $n!$ paths before you find a path that visits every vertex in the clique, finishing at $x$ and then moves to the extra vertex.

# Answer
> 1 votes
If I interpret the question correctly, it asks whether you could solve Hamiltonian Path by performing depth first search and checking whether the tree that describes the search is in fact a path that includes all vertexes.

Consider this graph:

```
      C
     / \
A---B---D---E

```

There is a Hamiltonian Path in this graph: ABCDE.

Depth-first search, starting from A, may result in a tree

```
A-B-C-D-E

```

that is the Hamiltonian Path.

But, depending the order in which it considers adjacent vertexes while searching, it may instead result in the tree

```
A-B-D-E
     \
      C

```

This does not reveal that there is a Hamiltonian path.

The trouble with using depth-first search to solve Hamiltonian Path is that you have to re-run the search for each possible vertex ordering, and that requires exponential time.

---
Tags: algorithms, np-complete, shortest-path, hamiltonian-path
---


title: Graph Injective-Homomorphism Problem

text:
# Question
Title: Graph Injective-Homomorphism Problem
Graph Homomorphism is a well-known NP-complete problem. Given graph $G$ and $H$, $G$ is said to be homomorphic to $H$ if there is a mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$.

The mapping in above is unrestricted -- and hence, multiple nodes of $G$ can map to a single node in $H$. If we restrict the mapping to be injective, then only one node of $G$ can map to a node in $H$. Thus, we have the injective-homomorphism variant:

Given graph $G$ and $H$, $G$ is said to be *injective-homomorphic* to $H$ if there is an *injective* mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$.

To me -- the injective homomorphic is a very natural variant of Graph Homomorphism problem, but I am unable to find a single research paper on it (the closest is "locally injective" homomorphisms). Why has there been zero interest in Injective-Homomorphism? Could I be missing something? BTW, its easy to see that injective-homomorphism decision problem is also NP-complete, by a simple reduction from the Homomorphism problem.

# Answer
> 5 votes
As D.W. mentioned, $G$ is injective-homomorphic to $H$ if and only if $G$ is isomorphic to a subgraph of $H$. That is why you are "unable to find a single research paper on 'injective-homomorphism'". There are plenty of paper about subgraphs or about subgraph isomorphism, of course.

---

More specifically, suppose we are given graph $G$ and $H$ and an injective-homomorphism from $G$ to $H$ $f: G\to H$, i.e., $f|\_{V(G}:V(G) \to V(H)$ is injective and, $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$. Then $f(G):=(f(V(G)),f(E(G)))$ is a subgraph of $H$. Moreover, the map $f: G\to f(G)$ is a graph isomorphism.

Conversely, if there is a graph isomorphism $f: G\to S$ where $S$ is a subgraph of $H$, then the composition of $f$ with the natural inclusion of $S$ into $H$ is an "injective-homomorphism" from $G$ to $H$.

# Answer
> 1 votes
If the homomorphism from a graph $G$ to a graph $H$ is injective, then $G$ is isomorphic to a subgraph of $H$. An injective homomorphism is called a *monomorphism*. Perhaps you can search for research papers on specific types of injective homomorphisms, such as co-retractions or isometric embeddings.

Given any homomorphism $f$ from $G$ to $H$, we can construct an injective homomorphism $\psi$ from the quotient $G/P$ to $H$ and a map $\pi\_P$ such that $f = \psi \cdot \pi\_P$. Here, $P$ is the partition of $V(G)$ obtained from the equivalence relation $x \sim y$ if and only if $f(x)=f(y)$, the quotient $G/P$ is defined to have vertex set $P$ and two vertices $V\_i$ and $V\_j$ are adjacent in this quotient whenever they each contain vertices that are adjacent in $G$, and $\pi\_P: V(G) \rightarrow V(G/P)$ maps each vertex of $G$ to the part it belongs to.

A map $f:V(G) \rightarrow V(H)$ is an *isometric embedding* if it preserves distances in the sense that $d\_H(f(u),f(v)) = d\_G(u,v)$ for any two vertices $u,v \in V(G)$. Thus, an isometric embedding is a special type of injective homomorphism; it arises in the context of routing problems.

See (Hahn and Tardif, "Graph Homomorphisms: structure and symmetry") for properties of isometric embeddings and co-retractions.

---
Tags: graphs, colorings
---


# Question
Title: Do certain epsilon transitions have to be a part of an epsilon nfa?
Hello, Im new to learning epsilon nfas, and I have been wondering if we could leave certain epsilon transitions out, and if so would it still be a valid epsilon nfa? For example regarding the image, couldnt I just delete the marked epsilon transition and the state that it leads to, thus only having the unmarked epsilon and c transition left, and the states that they lead to? To me it seems that it is still equivalent to the epsilon nfa before deleting the marked transition, or does the marked epsilon transition have to exist?

# Answer
> 1 votes
Yes, it has to exist. If you remove the circled $\epsilon$-transition, your resulting NFA will be different since the second state will become unreachable. You would only be able to accept the empty string whereas your actual NFA accepts either the empty string, or strings that contain only $c$'s.

In essence, the resulting NFA stays valid, but will not recognise the same language as the complete one.

---
Tags: nondeterminism
---