Problem Detail: So I have a question: Give a CFG for ${a^i b^j : 2 i<j}$ And this is my approach: $Sto AB$ $Ato aAbmid varepsilon$ $Bto b mid bB$ A confirmation, or correction, along with how you tested(and tips for Read More …
Author: ignougroup
[Solved]: Can a Turing Machine decide if an NFA accepts a string of prime length?
Problem Detail: I want to know if the following problem is decidable: Instance: An NFA A with n states Question: Does there exist some prime number p such that A accepts some string of length p. My belief is that this Read More …
[Solved]: Algorithm for wait-for graph
Problem Detail: During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used? By making a slight modification, i.e., instead Read More …
[Solved]: Are DCFLs closed under reversal?
Problem Detail: According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and pops) for this seems to depend on Read More …
[Solved]: Propositional formula in DNF can be decided in polynomial time?
Problem Detail: For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable: Just walk through all subformulas (l_1 and … and l_k) and check, wheter it has NO complementary pair of literals. Read More …
[Solved]: Difficulty in understanding an approach to SPOJ $d$-query problem
Problem Detail: I was trying to solve this problem on SPOJ: Given a sequence of $n$ numbers $a_1, a_2, ldots, a_n$ and a number of $d$-queries. A $d$-query is a pair $(i, j)$, $(1 leq i leq j leq n)$. For Read More …
[Solved]: Regular expression for odd binary numbers without leading zeros
Problem Detail: I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0cup1)^*1$, but that doesn’t match just 1. The best it matches is 11. Read More …
[Solved]: Amdahl’s law or gustafson’s law
Problem Detail: I am a little confused which of the two laws above i should use: Suppose I have a computer program that can be parallelized by 70%. 30% cannot be parallelized. Every single data (100% of data) will pass the Read More …
[Solved]: What are the main ideas used in a Fenwick tree?
Problem Detail: While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this technique. So in an effort Read More …
[Solved]: Design a Turing Machine Checking if Apples and Bananas are Even
Problem Detail: I am having trouble with a past exam paper. I have to design a Turing Machine to do the following, but I don’t really know where to start with this question. Any help would be very much appreciated. Design Read More …
