Languages

We build languages from some alphabet/lexicon $\Sigma$ by defining a language $L$ on $\Sigma$ as a subset of the strings $\Sigma^*$ that can be built from $\Sigma$.

\[L \subseteq \Sigma^*\]

This definition implies that the set of all languages on $\Sigma$ is the power set of $\Sigma^*$

\[L \in 2^{\Sigma^*}\]

This terminology arises from the fact that, if $\Sigma$ were, say, all of the phonemes of English, at least one element of $2^{\Sigma^*}$ would be all and only the words of English (or at least one persons English idiolect). If $\Sigma$ were all English words (and assuming that grammaticality is a coherent binary concept), at least one element of $2^{\Sigma^*}$ would be all the grammatical sentences of English (or at least one persons English idiolect). Of course, many of the sets in $2^{\Sigma^*}$ won’t look anything like English or any other languages, and a big part of this class is going to be figuring out how to find subsets of $2^{\Sigma^*}$ that look like possible languages.

To generate the finite languages, we can compose our generator for $\Sigma^*$ with the incremental finite-subset generator developed earlier. No generator can enumerate all languages on a nonempty finite alphabet, because $2^{\Sigma^*}$ is uncountable.

from collections.abc import Iterable, Iterator, Sequence
from itertools import product

#| code-fold: true
#| code-summary: Generator for natural numbers

def natural_numbers() -> Iterator[int]:
    """Yield the natural numbers starting from 0.

    Yields
    ------
    int
        The next natural number.
    """
    i = 0
    while True:
        yield i
        i += 1

Generator for power set

def powerset[T](iterable: Iterable[T]) -> Iterator[frozenset[T]]:
    emptyset: frozenset[T] = frozenset()
    yield emptyset

    seen = {emptyset}

    for r in iterable:
        new = {s | frozenset({r}) for s in seen}
        for n in new:
            yield n
            seen.add(n)

Generator for Σ*

def sigma_i(sigma: Sequence[str], i: int) -> Iterator[tuple[str, ...]]:
    """Generate all strings of length i over an alphabet.

    Parameters
    ----------
    sigma : Sequence[str]
        The alphabet.
    i : int
        The string length.

    Returns
    -------
    Iterator[tuple[str, ...]]
        An iterator over all strings of length ``i``.
    """
    if i < 0:
        raise ValueError("i must be nonnegative")
    sigma_repeated = [sigma] * i
    return product(*sigma_repeated)

def sigma_star(sigma: Sequence[str]) -> Iterator[str]:
    """Generate all strings over an alphabet in length order.

    Parameters
    ----------
    sigma : Sequence[str]
        The alphabet.

    Yields
    ------
    str
        The next string in the enumeration.
    """
    for i in natural_numbers():
        for s in sigma_i(sigma, i):
            yield ''.join(s)

english_phonemes: tuple[str, ...] = (
    "ɑ", "æ", "ə", "ʌ", "ɔ", "aʊ", "aɪ", "b", "tʃ", "d", "ð", "ɛ", "ɝ", "eɪ",
    "f", "g", "h", "ɪ", "i", "dʒ", "k", "l", "m", "n", "ŋ", "oʊ", "ɔɪ", "p", "ɹ", "s",
    "ʃ", "t", "θ", "ʊ", "u", "v", "w", "j", "z", "ʒ",
)

finite_languages: Iterator[frozenset[str]] = powerset(sigma_star(english_phonemes))

for i, l in enumerate(finite_languages):
    if not i % 100000:
        print(l)
    
    if i > 1000000:
        break

Notice that even if we compute a million finite languages using this generator, we are still ending up with small languages. More generally, every value it can yield is finite; it necessarily misses every infinite language.

Question

How many languages are there in $2^{\Sigma^*}$? That is, what is $|2^{\Sigma^*}|$?

Because $\{s\} \in 2^{\Sigma^*}$ for all $s \in \Sigma^*$, we know that $2^{\Sigma^*}$ must be at least as large as $\Sigma^*$, which is the same size as $\mathbb{N}$. But unlike $\Sigma^*$ in comparison to $\mathbb{N}$, it turns out that $2^{\Sigma^*}$ is larger than either.

The trick to seeing this is to try to sequence all languages in $2^{\Sigma^*}$. Suppose there were such a sequence of languages $L_*: \mathbb{N} \rightarrow 2^{\Sigma^*}$ such that $L_*$ is bijective: if $L_*(i) = L_*(j)$, then $i = j$ ($L_*$ is injective), and $L_*(\mathbb{N}) = 2^{\Sigma^*}$ ($L_*$ is surjective). Given a sequence $S_*$ on the strings, which we know we can construct, define a language $\bar{L}$ such that $S_*(i) \in \bar{L}$ if $S_*(i) \not\in L_*(i)$, and $S_*(i) \not\in \bar{L}$ otherwise, for every $i \in \mathbb{N}$.

By definition, $\bar{L} \neq L_*(i)$ for any $i$, since $\bar{L}$ and $L_*(i)$ differ on at least $S_*(i)$: either $S_*(i) \in \bar{L}$ and $S_*(i) \not\in L_*(i)$ or $S_*(i) \in L_*(i)$ and $S_*(i) \not\in \bar{L}$. But if $\bar{L} \neq L_*(i)$ for every $i$, then $\bar{L} \not\in L_*(\mathbb{N})$. Thus, $L_*$ is not surjective, contrary to our assumption. Every proposed sequence omits at least its diagonal language $\bar{L}$, so $|2^{\Sigma^*}| > |\Sigma^*| = |\mathbb{N}|$.

--- title: Languages jupyter: python3 --- We build languages from some alphabet/lexicon $\Sigma$ by defining a language $L$ on $\Sigma$ as a subset of the strings $\Sigma^*$ that can be built from $\Sigma$. $$L \subseteq \Sigma^*$$ This definition implies that the set of all languages on $\Sigma$ is the power set of $\Sigma^*$ $$L \in 2^{\Sigma^*}$$ This terminology arises from the fact that, if $\Sigma$ were, say, all of the phonemes of English, at least one element of $2^{\Sigma^*}$ would be all and only the words of English (or at least one persons English idiolect). If $\Sigma$ were all English words (and assuming that _grammaticality_ is a coherent binary concept), at least one element of $2^{\Sigma^*}$ would be all the grammatical sentences of English (or at least one persons English idiolect). Of course, many of the sets in $2^{\Sigma^*}$ won't look anything like English or any other languages, and a big part of this class is going to be figuring out how to find subsets of $2^{\Sigma^*}$ that look like possible languages. To generate the finite languages, we can compose our generator for $\Sigma^*$ with the incremental finite-subset generator developed earlier. No generator can enumerate *all* languages on a nonempty finite alphabet, because $2^{\Sigma^*}$ is uncountable. ```{python} from collections.abc import Iterable, Iterator, Sequence from itertools import product #| code-fold: true #| code-summary: Generator for natural numbers def natural_numbers() -> Iterator[int]: """Yield the natural numbers starting from 0. Yields ------ int The next natural number. """ i = 0 while True: yield i i += 1 ``` ```{python} #| code-fold: true #| code-summary: Generator for power set def powerset[T](iterable: Iterable[T]) -> Iterator[frozenset[T]]: emptyset: frozenset[T] = frozenset() yield emptyset seen = {emptyset} for r in iterable: new = {s | frozenset({r}) for s in seen} for n in new: yield n seen.add(n) ``` ```{python} #| code-fold: true #| code-summary: Generator for Σ* def sigma_i(sigma: Sequence[str], i: int) -> Iterator[tuple[str, ...]]: """Generate all strings of length i over an alphabet. Parameters ---------- sigma : Sequence[str] The alphabet. i : int The string length. Returns ------- Iterator[tuple[str, ...]] An iterator over all strings of length ``i``. """ if i < 0: raise ValueError("i must be nonnegative") sigma_repeated = [sigma] * i return product(*sigma_repeated) def sigma_star(sigma: Sequence[str]) -> Iterator[str]: """Generate all strings over an alphabet in length order. Parameters ---------- sigma : Sequence[str] The alphabet. Yields ------ str The next string in the enumeration. """ for i in natural_numbers(): for s in sigma_i(sigma, i): yield ''.join(s) ``` ```{python} english_phonemes: tuple[str, ...] = ( "ɑ", "æ", "ə", "ʌ", "ɔ", "aʊ", "aɪ", "b", "tʃ", "d", "ð", "ɛ", "ɝ", "eɪ", "f", "g", "h", "ɪ", "i", "dʒ", "k", "l", "m", "n", "ŋ", "oʊ", "ɔɪ", "p", "ɹ", "s", "ʃ", "t", "θ", "ʊ", "u", "v", "w", "j", "z", "ʒ", ) finite_languages: Iterator[frozenset[str]] = powerset(sigma_star(english_phonemes)) for i, l in enumerate(finite_languages): if not i % 100000: print(l) if i > 1000000: break ``` Notice that even if we compute a million finite languages using this generator, we are still ending up with small languages. More generally, every value it can yield is finite; it necessarily misses every infinite language. ::: {.callout-caution} ## Question How many languages are there in $2^{\Sigma^*}$? That is, what is $|2^{\Sigma^*}|$? ::: Because $\{s\} \in 2^{\Sigma^*}$ for all $s \in \Sigma^*$, we know that $2^{\Sigma^*}$ must be at least as large as $\Sigma^*$, which is the same size as $\mathbb{N}$. But unlike $\Sigma^*$ in comparison to $\mathbb{N}$, it turns out that $2^{\Sigma^*}$ is larger than either. The trick to seeing this is to try to sequence all languages in $2^{\Sigma^*}$. Suppose there were such a sequence of languages $L_*: \mathbb{N} \rightarrow 2^{\Sigma^*}$ such that $L_*$ is bijective: if $L_*(i) = L_*(j)$, then $i = j$ ($L_*$ is injective), and $L_*(\mathbb{N}) = 2^{\Sigma^*}$ ($L_*$ is surjective). Given a sequence $S_*$ on the strings, which we know we can construct, define a language $\bar{L}$ such that $S_*(i) \in \bar{L}$ if $S_*(i) \not\in L_*(i)$, and $S_*(i) \not\in \bar{L}$ otherwise, for every $i \in \mathbb{N}$. By definition, $\bar{L} \neq L_*(i)$ for any $i$, since $\bar{L}$ and $L_*(i)$ differ on at least $S_*(i)$: either $S_*(i) \in \bar{L}$ and $S_*(i) \not\in L_*(i)$ or $S_*(i) \in L_*(i)$ and $S_*(i) \not\in \bar{L}$. But if $\bar{L} \neq L_*(i)$ for every $i$, then $\bar{L} \not\in L_*(\mathbb{N})$. Thus, $L_*$ is not surjective, contrary to our assumption. Every proposed sequence omits at least its diagonal language $\bar{L}$, so $|2^{\Sigma^*}| > |\Sigma^*| = |\mathbb{N}|$.