Problem Detail: If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty. If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default blank characters), then its language Read More …
Author: ignougroup
Negligible Function in Cryptography
Problem Detail: In the field of Cryptography and Computation Complexity there is a notion of negligible function. I have some difficulties in understanding intuition behind this notion. The following are some definitions from Chapter 9. Cryptography from the textbook Computation Complexity. Read More …
Which languages are recognized by one-counter machines?
Problem Detail: Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation. However, I have not seen a formal analysis of which languages can be recognized by a Read More …
Can reversing the final and non-final states of a DFA produce the complement of the original language?
Problem Detail: Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of the language that Read More …
CFG for ${a^ib^jc^k mid i neq j+k}$
Problem Detail: I am trying to design a context-free grammar for the language $L = {a^ib^jc^k mid ineq j+k}$ over the alphabet $Sigma = {a,b,c}$. I know that I can split this up into the union of two cfg’s $S_1$ and Read More …
Converting CFG to PDA
Problem Detail: I have the following CFG, $S rightarrow CB$ $C rightarrow aCa text{ }|text{ } bCb text{ }|text{ } text{#}B$ $B rightarrow AB text{ }|text{ } varepsilon$ $A rightarrow atext{ }|text{ }b$ This is the CFG for the following language: Read More …
DNF to CNF conversion: Easy or Hard
Problem Detail: In relation to the thread CNF to DNF — conversion is NP Hard (and a related Math thread): How about the other direction, from DNF to CNF? Is it easy or hard? On Page 2 of this paper, they Read More …
Good explanatory resource for algorithm techniques such as greedy, backtracking and recursive functions
Problem Detail: What would be a good book/resource that explains the basic idea behind those techniques, how to use (and maybe when to use them) and plenty of exercises with perhaps some worked examples (kind of like when for loops were Read More …
Regular languages that can’t be expressed with only 2 regex operations
Problem Detail: I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular operations (concatenation, union, and Read More …
Why did RSA encryption become popular for key exchange?
Problem Detail: This is a soft question. I don’t know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message Read More …
