One way to show that two regular expressions, r and s, correspond to the same language is to show that any string generated by r can be generated by s, and that any string that can be generated by s can also be generated by r. Another way is to develop identities by which a regular expression may be rewritten. If by application of the rewriting rules, two expressions may be made identical, then the two expressions correspond to the same language. Some example identities are given below. Closure Closure properties allow us both to build a desired regular language and to show that a given language is regular.
Proof Follows directly from the definitions of regular language and regular expression.
All finite languages are regular. Proof Induction on the number of elements in the language, and induction on the length of the string in a single element language prove this. The class of regular languages is closed under intersection, complementation, and difference. The proofs of these statements is most easily accomplished by using the corresponding finite state machines to build new FSAs that recognize the new languages. For intersection, the new FSA for its states pairs of states from the original two machines.