Dennis Meng
  • Member for 9 years, 6 months
  • Last seen more than a month ago
DFA for exactly two of a and one or more of b
5 votes

Since it's for class, I won't actually build the DFA for you, but I will give you a way to look at it that'll help. As far as $b$s go, you really only care about whether or not you've seen a $b$ so ...

View answer
Big O relation between $2^n$ and $2^{2n}$
3 votes

The statement: If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$. is incorrect, and that's probably where your confusion is. Taking from Raphael's answer in How does one ...

View answer
Regular language concatenation with superset
3 votes

Simply put, this statement of yours: On the other hand $\tilde{L}$ seems to contain strings E does not, i.e. those that are formed by concatenating non-empty string from both languages. is wrong....

View answer
Simple explanation of Simon's Problem
3 votes

What the article means by $$f : \{0,1\}^n \rightarrow \{0,1\}^n$$ is that the input and output of the function is a binary string of length $n$. As for the problem itself, the idea is that we have ...

View answer
Regular language using pumping lemma
2 votes

You probably misunderstood the question. For starters, the pumping lemma can't be used to prove that a language is regular, it can only be used to prove that a language isn't regular. The Wikipedia ...

View answer
Efficient Median Algorithm With Very Constrained Operators
Accepted answer
1 votes

I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all ...

View answer
Case distinction in B-tree deletion
1 votes

In simple terms, "case 1" dictates what happens when we reach the appropriate leaf node. "case 3" tells us what we do when we're still higher up in the tree. Small example: suppose we have {x, y, z} ...

View answer
Minimum number of people required to invite everyone to a reunion
1 votes

One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends. Now, assuming that you're asking people ...

View answer