1
$\begingroup$

I have an exercise where one is supposed to give a function that will enumerate the following language:

$L_1 = \{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in \mathbb{N} \hspace{1mm} \wedge \text{ (P is a prime number )} \}$.

The solution is the following function: $f: \mathbb{N} \rightarrow \Sigma^*$ with $f(i) = a^{p_{i+1}}b^{p_{i+1}}$, where $p_{i+1}$ is the $(i+1)^{th}$ prime number, ordered by the prime's order.

Could anyone explain to why does this solution work? And especially why does the function include $p_{i+1}$ instead of $p_{i}$ ?

Thank you!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

This function maps nonnegative integers to the set of integers of the form $a^pb^p$. Enumerating is trivial, just start $i$ from 0, compute $p_{i+1}$-th prime, compute $a^{p_{i+1}}b^{p_{i+1}}$ and output that number.

As for the index $i+1$, I guess that is because $0 \in N$ and it is assumed that primes are ordered starting from the index 1 not from 0, in other words we start from $p_1$ not from $p_0$, e.g., $f(0) = a^{p_1}b^{p_1}$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.