Problem Detail: I need some help with explaining why a grammar is not LL(1). Let us take the following grammar: $$ begin{align} S rightarrow & aB mid bA mid varepsilon A rightarrow & aS mid bAA B rightarrow & b end{align} Read More …
Category: Uncategorized
Turing machine – infinite tape in one or two directions
Problem Detail: I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my head I think they are Read More …
Worst case analysis of bucket sort using insertion sort for the buckets
Problem Detail: Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode). In the worst case, this would imply that we would have $O(n^2)$ performance, because Read More …
High Level Programming Languages vs Block Programming Environments
Problem Detail: I am looking for the opinions of more experienced programmers as to the effectiveness of writing programs in Block Programming Environments such as Scratch or App Inventor as opposed to High Level Languages such as C++, Python or Java. Read More …
What future working opportunities do computer science students have?
Problem Detail: If I am right students learning computer science at universities learn very theoretical kind of knowledge. A knowledge most of which (e.g. algorithm theory) can’t be used to create everyday software (e.g. MS Word, IE, etc.). What opportunities do Read More …
Maximum number of states in minimized DFA from NFA with $n$ states
Problem Detail: If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$? Asked By : Kapes Answered By : bellpeace The maximum Read More …
Why is this example a regular language?
Problem Detail: Consider this example (taken from this document: Showing that language is not regular): $$L = {1^n mid ntext{ is even}} $$ According to the Pumping Lemma, a language $L$ is regular if : $y ne ε$ $|xy| lt n$ Read More …
Is the class NP closed under complement?
Problem Detail: Is the class $sf NP$ closed under complement or is it unknown? I have looked online, but I couldn’t find anything. Asked By : user16742 Answered By : joebloggs The answer is “not known to science”. It is known that P Read More …
Is $a^n b^n c^n$ context-free?
Problem Detail: I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language $${a^nb^nc^nmid ngeq 1},.$$ Can anybody tell me if this is a Read More …
What’s an example of an unsatisfiable 3-CNF formula?
Problem Detail: I’m trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT. Maybe it’s the late hour but I’m afraid I can’t think of a 3CNF formula that cannot be satisfied (I’m probably missing something Read More …
