nir shahar
  • Member for 1 year, 8 months
  • Last seen this week
Finding the shortest path in a grid which has walls
1 votes

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 ...

View answer
Is necessarily the following language not decideable
Accepted answer
1 votes

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.

View answer
decider for a question not clear
0 votes

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 ...

View answer
Implementing Queue operations in $\Theta(1)$
Accepted answer
2 votes

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 ...

View answer
How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language
0 votes

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

View answer
Proving undecidability for a language which contains string with certain syntax
Accepted answer
0 votes

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
one for loop wraps 2 indexof method, what is the time efficiency?
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
How to prove semi-decidable = verifiable?
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
is co-NP-hard contained in EXPTIME-hard or vice-versa?
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
Proving a solution for the $n$-Queens Puzzle
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
How to prove Big-O when $f(n)$ is defined sectionwise
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&...

View answer
Quicksort Time Complexity
1 votes

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 ...

View answer
Is there any property about height of PDA?
1 votes

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 ...

View answer
XOR of three integers where each pair's XOR is the other integer
1 votes

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
Doubt regarding strong component in a graph
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
Prove a language is not recursive enumerable
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
Asymmetric Transition Probability Matrix with uniform stationary distribution
0 votes

Take the matrix $A$ such that for every $i$, we have: $A_{i,i} =0.5$ $A_{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
Close To Cook Reduction given NP != coNP
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 $...

View answer
Having Moore's law is it worth looking for more algorithms?
0 votes

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 ...

View answer
Find the number using binary search against one possible lie
1 votes

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 ...

View answer
Is there a dynamic programming solution to the student allocation problem?
1 votes

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 ...

View answer
Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps
Accepted answer
0 votes

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 ...

View answer
Is the language of rectangular matrices in MATLAB-style syntax context free?
0 votes

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 ...

View answer
"problematic" non-halting inputs for Turing machines
Accepted answer
0 votes

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 ...

View answer
Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }
-1 votes

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, ...

View answer
How to enumerate all Turing machines?
Accepted answer
2 votes

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 ...

View answer
Is the empty string and some words of even length are elements of this set?
0 votes

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 ...

View answer
How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Accepted answer
0 votes

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

View answer
When proving a set is not regular is it enough to prove a subset of it regular?
Accepted answer
0 votes

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 ...

View answer
Modified shortest path problem
Accepted answer
4 votes

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 $...

View answer