Problem Detail: As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), “regex golf” (which might better be called the regular expression separation problem) is the puzzle of defining Read More …
Blog
[Solved]: What is an IELR(1)-parser?
Problem Detail: I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables. What is an IELR-parser? All relevant articles Read More …
[Solved]: Is there a non-brute force algorithm for Eulerization of graphs?
Problem Detail: Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree. In graphs with two or more vertices of odd degree (there may only be Read More …
[Solved]: Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Problem Detail: Can a two-stack PDA accept language $L={a^nb^mc^nd^m mid n geq m}$, which has no context-free grammar? I don’t believe this has a context-free grammar, but please correct me if I’m wrong. Asked By : Iancovici Answered By : Patrick87 A two-stack Read More …
[Solved]: Algorithm to convert decimal number to binary
Problem Detail: I am reading this material to understand the basics of number system. I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number. The heading of that part Read More …
[Solved]: Why is the Shannon entropy 0.94 in this example?
Problem Detail: Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$. I must find Read More …
[Solved]: Metrics and algorithms for complexity of a graph
Problem Detail: I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short description or list Read More …
[Solved]: Minimum number of processes for the deadlock?
Problem Detail: A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock? 1 2 3 4 My Read More …
[Solved]: Are permutations of context-free languages context-free?
Problem Detail: Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ context-free? I found two papers dealing Read More …
[Solved]: Is it possible that the union of two undecidable languages is decidable?
Problem Detail: I’m trying to find two languages, $L_1, L_2 in RE setminus R$, such that $L_1 cup L_2 in R$. I have already proved that if $L_1cap L_2 in R$ and $L_1 cup L_2 in R$, such $L_1, L_2$ don’t Read More …
