Problem Detail: I’m a self-taught programmer and have been coding for 8 years. Due to this experience, I’m already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.). However, I never learned “computer science,” only programming. What Read More …
Blog
[Solved]: What is a forwarding pointer?
Problem Detail: I heard this terminology used today and haven’t come across it before, could someone please explain? Are there any other terms/names that describe this concept? Asked By : jcm Answered By : babou “Forwarding pointer” is the name of a technique Read More …
[Solved]: What is the possible number of states in the DFA of intersection of two given FA?
Problem Detail: Consider a DFA over $a,b$ accepting all strings having number of $a$ ‘s divible by 6 and number of $b$ ‘s divisble by 8. What is the minimum number of states in the resultant DFA ? This problem Read More …
[Solved]: Where am I wrong?: “countability” and “recursive enumerability”
Problem Detail: I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i Read More …
[Solved]: Proof of non-regularity, based on the Kolmogorov complexity
Problem Detail: In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the first two, Myhill-Nerode theorem and Pumping lemma, I understood well and Read More …
[Solved]: Exponential time algorithms
Problem Detail: Wiki define Polynomial time as fallow: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ Read More …
[Solved]: A quine in pure lambda calculus
Problem Detail: I would like an example of a quine in pure lambda calculus. I was quite surprised that I couldn’t find one by googling. The quine page lists quines for many “real” languages, but not for lambda calculus. Of course, Read More …
[Solved]: Algorithm to find Dominance Frontiers
Problem Detail: The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9). We start with the immediate dominators of each control-flow graph node B already calculated and stored Read More …
[Solved]: Why is Turing completeness right?
Problem Detail: I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can perform any possible computation. Read More …
[Solved]: Is the language $L = { a^ib^j mid i nmid j } $ context free?
Problem Detail: Is the language $L = { a^ib^j mid i nmid j } $ context free ? If we fix $n in N$ then we know that the language $L = { a^ib^j mid forall 1 le k le n Read More …
