Problem Detail: In Knuth’s original paper on $LR(k)$ grammars, he proved that the decision problem “Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?” is undecidable. Is there a similar result showing that it is Read More …
Category: Uncategorized
[Solved]: Assign undirected edges in a mixed graph to make graph cyclic/acyclic
Problem Detail: What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle. It doesn’t “feel” like an NP-hard problem, Read More …
[Solved]: Most common subset of size $k$
Problem Detail: I’m trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size Read More …
[Solved]: Which measure of sortedness explains the phase transition in Quicksort’s runtime?
Problem Detail: I’m currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n log n)$ as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of Read More …
[Solved]: Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar
Problem Detail: I’m trying to understand the equivalence in expressive power of formal grammars whose rules take the form: $$ alpha rightarrow beta $$ where $ |alpha| leq |beta| $ (called a monotonic grammar), and grammars whose rules take the form: Read More …
[Solved]: Find non-regular $L$ such that $L cup L^R$ is regular?
Problem Detail: I’ve been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem: Give a non-regular language $L$ such that $L cup L^R$ is regular. I’ve been Read More …
[Solved]: MU0 instruction set
Problem Detail: As i know the MU0 processor instruction format is as follows: so the opcode is 4 bit, can anyone explain why it has only 8 instructions, if it could have 16 instructions, 2^4 = 16 ?? Asked By : rainman Read More …
[Solved]: Prove that regular languages and context-free languages aren’t closed under $Perm(L)$
Problem Detail: Let the operation $$Perm(L) = { w | exists u in L text{ such that } u text{ is a permutation of } w }$$ Prove that both regular languages and CFLs aren’t closed under $Perm(L)$. I’ve tried to Read More …
[Solved]: Understanding Logical to Physical Addressing
Problem Detail: I am trying to understand the concept of logical to physical addressing. I am given 72 physical addresses (0-71) with values A virtual address = 2^(p+w) p = page bits w = word bits I know the page table Read More …
[Solved]: How do calculators convert from decimal to fraction?
Problem Detail: Sorry if this question is either obvious or ignorant. I am a high school student with only the computer science knowledge I have taught myself. Calculators have a function that can convert numbers from decimal to fractional equivalents. For Read More …
