We know that the union, concatenation, and Kleene star of regular languages are also regular because they exhibit NFAs that accept them. The term that describes the property of operators “staying within the same class of language” is called closure; just as integers are closed under addition, subtraction, and multiplication, we say that regular languages are closed under union, concatenation, and Kleene star.

Note: A set is closed under an operation if the result of the operation remains in that set.

Now, we’ll take a deeper look at closure and other properties of regular languages, and develop algorithms for making decisions about regular languages. Finally, we’ll introduce formal languages that are not regular.

Reversing a finite automaton

We know that regular languages are closed under complementation by inverting the acceptability of each state in a DFA that accepts a language. Therefore, having found an automaton that accepts the complement of the original language, we conclude that the complement of any regular language is regular.

We can show that reversing the strings in a regular language results in another regular language by “reversing” its machine. To reverse a machine, we do the following:

  • Remove any jail state ( because jail states become unreachable when arrows are reversed).
  • If there is more than one accepting state, we create a new, unique, accepting state, reachable from what were the accepting states, by lambda transitions.
  • We make the original start state the new, unique, accepting state.
  • We make the original (now unique) accepting state the new start state.
  • We reverse all edges (and their strings if the diagram is a GTG).

Example: Reversing a machine that accepts the language aa∗c∗b∗aa^*c^*b^*

To illustrate this, we’ll reverse the machine that accepts the language L=aa∗c∗b∗L=aa^*c^*b^*.

Get hands-on with 1200+ tech skills courses.