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?
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.