3
$\begingroup$

The definition of regular expressions says they are closed under union, concatenation, and Kleene star. Single symbols also form regular expressions/languages.

Since union is between two languages, does that mean that when the alphabet is infinitely countable, the language which is exactly the alphabet is not a regular language?

Thanks.

$\endgroup$
1
  • $\begingroup$ Most definitions of regular languages are made for finite alphabets, and the definitions break down in a number of ways when you try to make the alphabet infinite. (+1) in the hopes people more knowledgeable than me find this, but I don't know of any canonical way to solve this problem. My answer would have to be "regular languages over countable alphabets aren't well defined". $\endgroup$
    – HallaSurvivor
    Jun 21, 2020 at 23:42

1 Answer 1

Reset to default
2
$\begingroup$

I just discover this question after answering your other question, but to avoid repetition, I will refer to my answer for definitions.

If $A$ is an infinite alphabet, then the set $A$ is not a rational subset of $A^*$. However, it is a recognizable subset of $A^*$. Indeed, let $F = \{1, a, 0\}$ be the finite monoid defined by $aa = a0 = 0a = 0$ and let $f: A^* \to F$ be the monoid morphism defined by $f(c) = a$ for each $c \in A$. Then $f(A) = \{a\}$ and $f^{-1}(a) = A$, since$f(1) = 1$ and $f(u) = 0$ if the length of $u$ is $\geqslant 2$.

This is a good illustration of the difference between rational and recognizable subsets.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .