# Tagged Questions

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

22 views

### How to describe this Context Free Grammar?

I've been having a really difficult time in describing the following Context Free Grammar S → SS | T T → aTb|ab I understand that it must start with an ...
15 views

### Help explain this Boolean equation XOR with NOR gates

I'm just starting Boolean algebra and am following an example given in the text that shows the configuration of NOR gates to create an XOR. I cannot follow the algebraic example and would like to have ...
51 views

### recurrence algorithms, algebra issues?

So we're given a problem to solve... no other instructions.. the answer is given as well. I am having trouble understanding how this problem is unrolled. I understand that $\sqrt{2^{2^k}}$ can ...
35 views

### Finite automata problem

I need to draw a finite automata over the alphabet $\{a,b,c\}$, such that the following properties hold: a word starts with at most two $a$ a $c$ is always followed by an even number of $b$ (0 ...
32 views

### Troubles proving $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$

Prove that $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$, knowing that $O[g(n)] = \left\{ f(n) \mid \exists\ c,n_0 > 0\ :\ 0 \leq f(n) \leq c \cdot g(n)\ \forall\ n \geq n_0 \right\}$ I don't ...
34 views

### Importance of Bernoulli Numbers

I'm writing a research paper on the foundations of computing. Supposedly Ada Lovelace wrote an algorithm to find Bernoulli numbers. It sounds cool, but it won't mean anything to my history teacher. ...
18 views

### prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...