9

For a fixed alphabet $\Sigma$, the blow-up is at most polynomial. First, given a regular expression $r$, it is straightforward to construct an expression $\tilde r$ using the operators $a\in\Sigma$, $+$, $\cdot$, $(-)^+$, and $\let\nul\varnothing\nul$ such that $$L(\tilde r)=L(r)\let\bez\smallsetminus\bez\{\let\ep\varepsilon\ep\}$$ recursively, by putting $\...


3

Suppose Alice always sends exactly $k$ bits to Bob during the protocol. On average, how many possible candidates for her $n$-bit string are consistent with the communication transcript? What does that tell you about the probability that Bob guesses which one of those candidates is the correct one?


1

Being a web developer, I am sure you realize that most large scale websites contain at least one of databases, high availability server, front end design, an algorithm of some sort, etc. Each of these areas has an active research community. Database researchers mostly study data structures and algorithms that speed up database operations. UI/UX researchers ...


Only top voted, non community-wiki answers of a minimum length are eligible