Problem Detail: Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a Read More …
Author: ignougroup
[Solved]: Precise definition of term: *schema*
Problem Detail: Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a schema language? Read More …
[Solved]: Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?
Problem Detail: Let $C$ be a non-trivial set of recursively enumerable languages ($emptyset subsetneq C subsetneq mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language in $C$: $$L={langle M rangle mid L(M) in C Read More …
[Solved]: Is Big-Oh notation preserved under monotonic functions?
Problem Detail: I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) implies log (f(n)) = O(log (g(n)))$$ I can prove that this is true if $g$ is monotonically increasing, but Read More …
[Solved]: How to show that L*=(L*)*?
Problem Detail: I am studying formal language theory and have been asked to prove the following: $forall L, L^*=(L^*)^*$ I’ve started with $def. L^* = bigcup_{i in mathbb{N}} L_i, L_0={{epsilon}}, L_1={L}, L_{i+1}={uv|uin L_i, vin L}$ $then (L^*)^* = bigcup_{i in mathbb{N}} Read More …
[Solved]: Proving iff statement with reductions
Problem Detail: I have a statement I am trying to prove, and I’m very close, but I think I’m missing a couple of key concepts about regular and context-free languages. Question: Let $ A = { ww | w epsilon Sigma^{*} Read More …
[Solved]: pumping lemma for $L={a^n b^m c^k mid n = m vee mneq k}$
Problem Detail: Using pumping lemma, how can I prove that $L={a^n b^m c^k mid n = m vee mneq k}$ is not regular?. If I choose $w= a^m b^m c^m$ and pump up with $i=2$, if have $a^m=1 b^m c^m$ but Read More …
[Solved]: Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace
Problem Detail: Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped. Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(X)$ gate (for $n > 3$), using no work qubits. Read More …
[Solved]: Given 2 regular languages and their DFA’s, how to construct the DFA of the union?
Problem Detail: Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA’s. How can I construct a new DFA for the regular language $L1 cup L2$? Asked By : slallum Answered By : Patrick87 Let’s denote the sets of Read More …
[Solved]: Deciding Countability of Languages
Problem Detail: Suppose we have given $Sigma={a,b}$, Which one of the following set is not countable (a) Set of all languages over $Sigma$ (b) Set of all regular languages over $Sigma$ (c) Set of all languages over $Sigma$ accepted by Turing Read More …
