4

Consider the following language S = {0, 00, 000, 0000, 00000,....}.

Consider the power-set of S and let each element of the power-set of S be a regular language. Since S is countably infinite its power set is uncountably infinite. Since each element of the power set of S is finite each element is a regular language, but this implies that there are uncountably many regular languages.

I know that the above 'proof' is wrong but I don't understand why. Where exactly does the proof break down.

Ahmed Shaaban
  • 51
  • 2

1 Answers1

1

It's not true that every element of the powerset is finite. For example, the powerset includes S itself. It's also not true that every element of the powerset is a regular language. For example, it includes the set {0^n | n is the code of a Turing machine that halts on empty input}.

David Richerby
  • 170
  • 8