New answers tagged computability
1
Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.
The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:
Start with $n=2$ - this is prime.
Set $j$ equal to $n$.
Add $1$ to $n$
Set $k$ equal to $n$.
...
0
Alternatively show for every k: There is no w containing 2k+1 d’s.
0
The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number ...
0
I'm not convinced by your setup. All programs are finite sequences of steps, so the equivalence of $A$ and $B$ in your first paragraph isn't decidable: they're equivalent iff $B$ halts on every input that $A$ halts on.
Your main question seems to be under-specified in a way that makes it trivial. The empty langauge is a decidable problem about pairs $(...
-4
Here is working code. Don't forget to input your percentage in fractional form (e.g. $0.02$ for $2\%$).
#include <stdio.h>
#define MONTHS_IN_YEAR 12
float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears);
int main(void) {
//Problem statement variables
float principalAmount; // use int if principal can ...
2
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.
So. We have some DFA $M$, and we can build a PDA $N$ which ...
Top 50 recent answers are included
