Is the set of languages that can be recognized by combinational logic smaller than those recognized by regular expressions?

Question

In the Wikipedia article on Automata theory there is a diagram that suggests that combinational logic recognizes a proper subset of the languages that a regular expression recognizes. Is this in fact the case?

Answer 1

The set of languages which can be recognised by combinational logic (to the extent that it's reasonable to talk about languages being recognised by combinational logic) is a proper subset of the set of languages recognised by DFAs. However, the two sets have the same cardinality ($\aleph_0$); both are isomorphic with $\mathbb{N}$.

Unlike DFAs and the other automaton in that diagram, combinational logic automaton have no way of dealing with sequential input. Every combinational circuit has a predefined finite number of boolean inputs. That allows the construction of a combinational circuit for any finite language. Every finite language is regular, but not all regular languages are finite. Hence, the set of finite languages is a proper subset of the set of regular languages.

A finite language with alphabet $\Sigma$ can be precisely described as a finite string by adding two symbols to the language ("separator" and "end-marker") and then listing the members in some order, separated by the separator and terminated by the end-marker. Each such representation corresponds to some natural number written in base $|\Sigma|+2$. That's similar to the representation of an arbitrary regular language by writing out its regular expression, also using an alphabet which augments $\Sigma$ with a few special characters.

That's not a one-to-one mapping; a strict proof of the assertion that both of these sets are isomorphic to $\mathbb{N}$ is left as an exercise. (But see this question if necessary.)