While learning Automata and computation theory independently, I made a realization I want to confirm.
Regular languages can all be created by taking elementary languages (languages made up of a single member of its alphabet) and performing closed operations in them, such as union, concat, and kleene star. This was clear to me from regular expressions.
Is this true? Is there any significance to this fact?
What about Context-free languages and other formal languages? Are there operations that can be performed on elementary languages to create all of them? Or is this a special property of regular languages only?
You are correct. For the example of regular languages, we have Kleene algebras, which are special cases of *-semirings. Similar algebras exist for the rest of the Chomsky hierarchy.
Before going up the hierarchy, I would recommend checking out what we can do with semirings alone. Two great papers on the topic are “Fun with Semirings”, Dolan 2013 and “A Very General Method of Computing Shortest Paths”, O’Connor 2011. Don’t be fooled by the titles; they both involve surprise guest appearances from regular expressions.