Problem Detail: Consider the language over the alphabet $sum= {a}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language Asked By : Leroy Kayanda Answered By : Yuval Filmus Read More …
Category: Uncategorized
[Solved]: If a predicate is not computable, what can be said about its negation?
Problem Detail: Doing the following exercise: Let $overline{HALT(x,y)}$ be defined as $overline {HALT(x,y)} iff text{program number y never halts on input x}$ Show that it is not computable. Just want to make sure I have understood the concept correctly. We had Read More …
[Solved]: Push Down Automatons “guess” – what does that mean?
Problem Detail: I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can “choose” among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown. Still, I do not understand how Read More …
[Solved]: Machines in P undecidable?
Problem Detail: Given a Turing machine $M$, we say that $L(M) in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M in P$ if the machine runs in polynomial Read More …
[Solved]: Showing that 3-colorable is NP-complete
Problem Detail: Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I’m aware we Read More …
[Solved]: FM-index – print all patterns
Problem Detail: How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it’s better to leave more details regarding my problem. The input i have are: the Read More …
[Solved]: Does two languages being in P imply reduction to each other?
Problem Detail: Given two languages $L_1$ and $L_2$ that are in $mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the empty Read More …
[Solved]: Which kind of branch prediction is more important?
Problem Detail: I have observed that there are two different types of states in branch prediction. In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay. In the instruction pipeline, Read More …
[Solved]: Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
Problem Detail: In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. Now Assume that $R$ is a regular language and $D$ Read More …
[Solved]: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?
Problem Detail: I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near Read More …
