deepdream of
          a sidewalk
Show Question
Math and science::Theory of Computation

Regular language operators

Let A and B be languages. We define the regular operations union, concatenation and star as follows:

Union
AB={xxAxB}  (i.e. as per standard axiom of union for sets)
Concatenation
AB={xyxAyB}
Star
A={x1x2...xkk0 and each xiA}

The class of regular languages is closed under these three operations!


Visual Justification

It is quite easy to grasp how regular languages are closed under the above three operations. To do so, consider the state diagrams representing two nondeterministic finite automata N1 and N2 which accepts languages A1 and A2 respectively. We can combine them in different ways to achieve union, concatenation and star operations.

Union, A1A2

The set of start states is the union of the start states of N1 and N2.

Concatenation, A1A2

Each accept state of N1 has an ε-transition to the start state of N2.

Star operator, A1

Each accept state of N1 has an ε-transition to the start state of N1.


Source

Introduction to the Theory of Computation, Sipser
p44