Theory of Computation: Finite Automata

Regular Expression

I was wondering if the operation of regular expression (Union, Concatenation, Star) is complete.

This question needs further prompt: In what sense do I mean complete?

Am I asking: - Does every string is representable with the regular operation? - Does the three operation formed the universe set of operation? (Whatever the universe set of operation means) - Does the three operation adding more information to each other? (By that I could mean that "why can't we define the operation by something else; by less operations?") - ...

I eventually chose the last question listed above. The answer for now is easy: this set of operation corresponds to what a finite automata can do. By that, I meant that a finite automata can recognize every regular expression.


Theory of Computation: Finite Automata
http://blog.slray.com/2025/01/30/Theory-of-Computation-Finite-Automata/
Author
Sirui Ray Li
Posted on
January 30, 2025
Licensed under