Search

Apologies if the title is confusing, but I couldn't think of better phrasing in short text.

Whenever we define / specify a certain automaton (such as a finite state machine or a turing machine) by defining all of its States, transition function, etc., this feels awfully similar to defining an algorithm. For example, I can define a machine that can tell if a number is divisible by 3. It is very similar to writing an algorithm and the steps to solving the problem.

Now I understand that the two aren't exactly equivalent. But would it be incorrect to say that the specification of a machine is a type of algorithm, since we're defining the steps it takes to solve a problem (how to respond to a specific state or input to solve a specific problem)?

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?