Union of two regular languages

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In formal language theory, and in particular the theory of nondeterministic finite automata, it is known that the union of two regular languages is a regular language. This article provides a proof of that statement.

Theorem[edit]

For any regular languages and , language is regular.

Proof

Since and are regular, there exist NFAs that recognize and .

Let

[clarification needed]

Construct

where

In the following, we shall use to denote [clarification needed]

Let be a string from . Without loss of generality assume .

Let where

Since accepts , there exist such that[clarification needed]

Since


We can therefore substitute for and rewrite the above path as



Furthermore,

and


The above path can be rewritten as



Therefore, accepts and the proof is complete.[clarification needed]


Note: The idea drawn from this mathematical proof for constructing a machine to recognize is to create an initial state and connect it to the initial states of and using arrows.

References[edit]

  • Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (See . Theorem 1.22, section 1.2, pg. 59.)