What does a language parameterizing another language mean?

71 Views Asked by At

I am reviewing my class notes, and I came across this expression -

The $n$-th slice of $A \subseteq \Sigma^*$ is

$A_n = \{x \in \Sigma^* \mid {\langle n,x \rangle} \in A \}$

$C$ parameterizes $D$ (also called $C$ is universal for $D$) if,

$\exists A \in C \quad\text{such that}\quad D = \{A_n \mid n\in \mathbb{N}\}$

Also, please note, $\exists$ doesn't mean there exists here. It stands for existential projection.

$\exists B=\{x\in \Sigma^* \mid \exists w\in \Sigma^*\ {\langle x,w \rangle}\in B\}$

As a follow-up, I'm also trying to understand the following statement -

$D$ is $C$-countable if,

$\exists A \in C \quad\text{such that}\quad D \subseteq \{A_n \mid n\in \mathbb{N}\}$