Problem Detail: I am new to StackExchange, and I already made the mistake of posting a new question as a response to a previous question. Here, I rewrote my question more clearly and separately. I am trying to store an existing Read More …
Author: ignougroup
[Solved]: Proving that non-regular languages are closed under concatenation
Problem Detail: How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L={a^nb^n|nge1}$ ? Asked By : TT8 Answered By : David Richerby You can’t prove it because it isn’t true: the class of non-regular languages isn’t Read More …
[Solved]: Counterexample to this modified Dijkstra’s
Problem Detail: In class, we were given the following problem: We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the Read More …
[Solved]: Are the Before and After sets for context-free grammars always context-free?
Problem Detail: Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the Read More …
[Solved]: execises in computational complexity
Problem Detail: I am trying to get better in proofs and deep understanding of concept of computational complexity. Unfortunately, so far, with no success. In order to get more intuition, I decided to do more exercises, but most of them are Read More …
[Solved]: Advantages of amortized analysis
Problem Detail: I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis? What I understood: Let say we have 3 three operations a,b,c used 1,2 and 3 times to achieve Read More …
[Solved]: Does Reverse Polish Notation have an LL grammar?
Problem Detail: Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $Sigma(L) = {n, o}$, n := number, o := operator. Is there an LL grammar G so that L(G) = L? Read More …
[Solved]: Reduce the following problem to SAT
Problem Detail: Here is the problem. Given $k, n, T_1, ldots, T_m$, where each $T_i subseteq {1, ldots, n}$. Is there a subset $S subseteq {1, ldots, n}$ with size at most $k$ such that $S cap T_i neq emptyset$ for Read More …
[Solved]: How does an Operating System without kernel mode works?
Problem Detail: Andrew S. Tanenbaum in his book “Modern Operating Systems 3rd Edition” states that the distinction between operating system software and normal (user mode) software can sometimes be blurred in embedded systems(which may not have kernel mode) Can someone please Read More …
[Solved]: Finding big O notation of function with two parameters
Problem Detail: I’m looking to work out the big-O notation for the following: $$frac{n^{s + 1} – 1}{n – 1} – 1$$ I have a feeling the result is $Oleft( n^s right)$ but I’m not sure how to prove it. Any Read More …
