1
$\begingroup$

Took a Theory of Computation exam where one of the questions was :

Is there an infinite amount of regular expressions for the language $L=\{aa,bb\}$ ?

The proof requested was just an informal one.

My intuition was that if a set is countably infinite then it is infinite itself.

Then I thought that the following regular expressions are different :

  • $(aa)\ \cup \ (bb)$
  • $(aa)\ \cup \ (bb) \ \cup \ \emptyset$
  • $(aa)\ \cup \ (bb) \ \cup \ \emptyset \ \cup \ \emptyset$
  • $\dots$

So I can define a set of them that can be countably infinite.

To be clear I was taught some of the very basics of set theory so bare with me.

My questions are :

  • Are the regular expressions mentioned above different from one another?
  • Is a countably infinite set infinite itself?
$\endgroup$
2
  • $\begingroup$ What do you mean by "a regular expression for a language"? A regular expression defining the language? A regular expression built with symbols for the language? Also, what do you mean by the unione of expressions? $\endgroup$
    – Andrea Marino
    Commented Apr 6, 2023 at 12:21
  • 1
    $\begingroup$ @AndreaMarino a regular expression describes a regular language and $\{aa, bb\}$ is a regular one. As explained here : en.wikipedia.org/wiki/Regular_expression#Formal_language_theory. $\endgroup$
    – PatelisGM
    Commented Apr 6, 2023 at 12:42

1 Answer 1

Reset to default
1
$\begingroup$

Your intuition is right. You could also write $aa$ as $a\varepsilon a$, $a\varepsilon \varepsilon a$, etc., to get another countable set of regular expressions.

$\endgroup$

You must log in to answer this question.

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