Problem Detail: I was reading chapter-1 The Foundations: Logic and Proofs from this book. The chapter gives example of translating English sentence : “There is a woman who has taken a flight on every airline in the world.” as follows: Introducing Read More …
Author: ignougroup
[Solved]: construct a dfa that accepts odd consecutive number of 0’s and 1’s
Problem Detail: this dfa should accept only consecutive odd number of both 0’s and 1’s. example: 10001,1110001,10,01,011101. How can I draw its diagram? Asked By : user49697 Answered By : Rick Decker Here are a couple of hints to get you started. Could Read More …
[Solved]: Longest Common Subsequence Via Dynamic Programming
Problem Detail: I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here Read More …
[Solved]: Is the set of minimal DFA decidable?
Problem Detail: Let $mathrm{MIN}_{mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $langle A rangle in mathrm{MIN}_{mathrm{DFA}}$ then for every other DFA $B$ with less states than $A$, $L(A)ne L(B)$ Read More …
[Solved]: Context-free grammar for $L = {a^n : nleq2^{20}}$
Problem Detail: I want to find a context-free grammar for $L = {a^n : nleq2^{20}}$. There’s one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the Read More …
[Solved]: Type inference + overloading
Problem Detail: I’m looking for a type inference algorithm for a language I’m developing, but I couldn’t find one that suits my needs because they usually are either: à la Haskell, with polymorphism but no ad-hoc overloading à la C++ (auto) Read More …
[Solved]: What if block sizes are not equal among caches?
Problem Detail: In all the books, packets of slides and similar I read, cache miss is always explained by assuming that blocks of different caches (or cache and RAM) are always of the same size. It’s pretty clear how it’s works Read More …
[Solved]: Is Post’s Correspondence Problem decidable with fixed word size?
Problem Detail: So, it’s known that PCP is undecidable even when we fix the number of tiles to $n geq 7$. I’m wondering, can anything similar be said for when there is a fixed word length? To be precise, here’s the Read More …
[Solved]: Log-Space Reduction $CO-2Col le_L USTCON$
Problem Detail: I want to show that $CO-2Col le_L USTCON$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. [Input]: An undirected graph $G=(V,E)$, $s,t in V$. [Output]: 1 iff $s$ is connected to $t$ in $G$. Read More …
[Solved]: Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?
Problem Detail: From this statement As there is no surjection from $mathbb{N}$ onto $mathcal{P}(mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning does not work with a finite set $B$ which also has no Read More …
