nir shahar
• Member for 1 year, 8 months
• Last seen this week

Note: This solution assumes you cannot move left or up. Have you heard about dynamic programming? With a little bit of work, Im pretty sure it can help you find a solution for the question! An ...

Take some undecidable language $A$ and choose $B=A'\bigcup \{\epsilon\}$. $B$ is also undecidable, and the rest of the proof is just as what you have already done.

The pigeonhole principle. If you go through $|Q|+1$ states, then there must be a state you have been in twice already. This means that because the input is $\sqcup$ almost all of the time, then we are ...

A linked list is indeed a good idea. In addition to keeping a linked list, add a pointer to the middle item. When you insert an item, check to see if the current list's length is even or odd. If its ...

Proving such a claim rigorously can be usually done with induction on word length $|w|$.

It can be thought of a semantic property of the language, and its ok to use Rice's theorem here. Define $C=\{L|\text{there is a string with exactly 3 zeros in }L\}$ So, $L_1=\{<M>|M \text{ is ... View answer 1 votes Yes, you are correct. But time complexity we measure only in big-O notation. So the code above has time complexity$\mathcal O(n^2)$The space complexity depends on indexof's space complexity. ... View answer Accepted answer 2 votes Its obvious why a semi-decidable language is verifiable ($w$would be the machine's computation history on$x$). Now, we will show the other way: Let$V(x,w)$be a verifier for$L$. Define$M(x)$as ... View answer 3 votes It is known that co-NP$\subseteq$PSPACE$\subseteq$EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every$L\in$EXPTIME to it,... View answer 2 votes For the diagonal case, split to two proofs - one for each "rotation" of the diagonal line. When the diagonal line is "from top left to bottom right", then assume for the sake of contradiction we have ... View answer 1 votes you have to do for both expressions. But in this case, one expression is strictly smaller than the other one, so you can do it just for the$3n^2+2$and say$4n+1<3n^2+2$and therefore also$4n+1&...

The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$ and any other constant work done (for example, the work after the ...

If you could bound the stack height, say to some constant $c$, then it would have been possible to define an NFA for the task: Simply encode in the NFA states another $c$ values that represent the ...

There are infinitely many solutions: choose $a=b\in\mathbb N, c=0$ and then $a\oplus b\oplus c=0$. To find all solutions, choose an arbitrary $c\in\mathbb N$. We want to find all $a,b$ with $a\oplus ... View answer 1 votes A strong component in a graph$G$, is a group of vertices$V_s$such that$\forall v_1,v_2\in V_s:\exists u_1,...,u_n\in V_s:v_1=u_1\rightarrow u_2\rightarrow...\rightarrow u_n=v_2$. In simpler terms:... View answer 0 votes Yes it's okay to use Rice's extended theorem. To clarify, the theorem states: "if$C$is some set of languages, and$C\neq\emptyset\wedge\Sigma^*\notin C$, then$\{<M>|L(M)\in C\}\notin RE$." ... View answer 0 votes Take the matrix$A$such that for every$i$, we have:$A_{i,i} =0.5A_{i,i+1}=0.5$(for$i=n$, set$A_{n,0}=0.5$) Then it is not symmetric, but has a uniform stationary distribution. View answer 0 votes The assumption of$\text{P} \neq \text{NP}$is not necessary here. given a reduction$\Phi$from a language$A$to a language$B$, (that is polynomial time) then for every$x$we have,$x\in A $iff$...

Yes. Better algorithms, that run in less time complexity - work way better than just an increase in constant factor for large enough input, but more transistors is just a constant factor of work. We ...

If it was wrong one time, but right all of the other times after it, then we notice it will return you always the same thing after that wrong decision, and it would be the negation of them. In this ...

This sounds like it could be solved using a flow network. Define the graph $G=(V,E)$ such that: Add a starting node $s$. It will be the "source" node in the flow-graph. Add a node $v_{s_i}$ for ...

This language is obviously decideable, just emulate $M$ on $w$ and see whether it halted within $n$ steps or not... Now, to whether $nHALT\in P$ or $nHALT\notin P$. The length of $n$ here is ...

To convert this question into an easier question to answer, practically, we consider the language $\hat L=\{(a^nb)^n|n\in\mathbb N\}$. Proving this is not context free is enough, since we can give a ...

So, let's start tackling those problems. As a side note, I have arranged the questions such that each question uses the answer of the one before it (and this way, they almost seem too trivial to begin ...

PDA: Here is a guideline to solve this problem: Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, ...

A turing machine has a representation as a string. more specifically, you write the transition function. to do this, simply think of it as one big table, having in each row two states a letter, and a ...

Yes, since "the first, the middle, and the last characters of $w$ are identical" is not really well defined here (so there might be ambiguities like is $\epsilon\in L$?) Probably it wont really ...

I recommend to use this explanation on how to transform a CFG into a (1 state) PDA

I think you mixed up a few things here. Say, L is indeed regular. Then the pumping lemma guarantees us a pumping length. If we want to show that $L$ is not regular, we can go on by assuming its ...
Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need. Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge \$...