Dean Gurvitz
  • Member for 3 years, 10 months
  • Last seen this week
Why a TM with infinite states can decide the halting problem?
Accepted answer
3 votes

If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each ...

View answer
Big O and constants
Accepted answer
3 votes

Evaluating these Big-O constants in real life situations is nearly impossible. Each computer has different hardware, and the precise cost of each operation (or even of only a specific type of ...

View answer
Reversing topo-order of the original graph instead of the topo-order of the transposed graph?
3 votes

My intuition for why the reverse topological order is necessary is that given a node $v$ in a strongly connected component $C$, if $v$'s finishing time (denoted in CLRS as $f(v)$) is maximal, than so ...

View answer
Topology vs sigma-algebra's as a framework for approximate information?
2 votes

I don't consider myself knowledgable enough about logic to provide a complete answer myself, but I think the following two posts (1 from math.stackexchange, one from mathoverflow) contain some ...

View answer
Is the verifier for an $NP$ and its $co-NP$ the same?
2 votes

I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and ...

View answer
Kosaraju with connections between SSCs (strongly connected components)
2 votes

Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*...

View answer
Context free Grammar for this context free language
Accepted answer
2 votes

When trying to come up with a grammer for this language, there are several things one must make sure every word generated by it satisfies, including: It starts with a double $p$ Every addition of a $...

View answer
Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?
2 votes

To expand on what blue-dino wrote, is it indeed impossible to make a general sorting algorithm with worst-case (or even average-case) complexity which is better than $O(n\log(n))$. In this case "...

View answer
How to define (logically) the complement language?
1 votes

You aren't exactly correct in your example because of the redundant negation of the $\leq$ sign. In the most general sense, we always have: $$\neg (x_1 \land x_2\land ...\land x_n)=(\neg x_1) \lor...\...

View answer
Turing Machine DTime(log(n))
Accepted answer
1 votes

To add to old's answer, saying a TM runs in $O(1)$ means that the number of steps the TM makes cannot become infinitely large depending on the size of the input, and is always bounded by some constant....

View answer
Infinite Union operation of Formal Languages
1 votes

To add a more concrete example to chi's answer, in the case of CFL's, think about the following infinite union: $$\bigcup_{i=1}^\infty\{0^i1^i2^i\} = \{0^n1^n 2^n|n>0\}$$ which is a known example ...

View answer
Context-Free Grammar from this language
Accepted answer
0 votes

As Aspass.Jack wrote in the comments, let's first define $L_3$ to be the language where each $a$ is followed by at least 2 $b$'s, and $L_4$ to be the language where each $b$ is followed by at least ...

View answer
Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$
Accepted answer
0 votes

As Yuval commented, this is a very basic exercise so you should probably go over the basic definitions. One simple answer for this particular question is: $$S\rightarrow0S11|\varepsilon$$

View answer