306 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12
(3)L(r∗)=(L(r))* (the Kleene closure ofL(r)).
(4)L(r 1 ∨r 2 )=L(r 1 )∪L(r 2 )(the union of the languages).
(5)L(r 1 r 2 )=L(r 1 )L(r 2 )(the concatenation of the languages).Remark: Parentheses will be omitted from regular expressions when possible. Since the concatenation of
languages and the union of languages are associative, many of the parentheses may be omitted. Also, by adopting
the convention that “*” takes precedence over concatenation, and concatenation takes precedence over “∨,” other
parentheses may be omitted.
Definition 12.3: LetLbe a language overA. ThenLis called aregular languageoverAif there exists a regular
expressionroverAsuch thatL=L(r).
EXAMPLE 12.2 LetA={a, b}. Each of the following is an expressionrand its corresponding languageL(r):
(a) Letr=a*. ThenL(r)consists of all powers ofaincluding the empty wordl.(b) Letr=aa*. ThenL(r)consists of all positive powers ofaexcluding the empty word.
(c) Letr=a∨b∗. ThenL(r)consists ofaor any word inb, that is,L(r)={a,l,b,b^2 ,···}.(d) Letr=(a∨b)∗. NoteL(a∨b)={a}∪{b}=A; henceL(r)=A∗, all words overA.
(e) Letr=(a∨b)∗bb. ThenL(r)consists of the concatenation of any word inAwithbb, that is, all words
ending inb^2.(f) Letr=a∧b∗. L(r)does not exist sinceris not a regular expression. (Specifically,∧is not one of the
symbols used for regular expressions.)EXAMPLE 12.3 Consider the following languages overA={a, b}:
(a)L 1 ={ambn|m> 0 ,n> 0 }; (b)L 2 ={bmabn|m> 0 ,n> 0 }; (c)L 3 ={ambm|m> 0 }.Find a regular expressionroverA={a, b}such thatLi=L(r)fori= 1 , 2 ,3.
(a) L 1 consists of those words beginning with one or morea’s followed by one or moreb’s. Thus we can set
r=aa∗bb∗. Note thatris not unique; for example,r=a∗abb∗is another solution.
(b)L 2 consists of all words which begin with one or moreb’s followed by a singleawhich is then followed
by one or moreb’s, that is, all words with exactly oneawhich is neither the first nor the last letter. Hence
r=bb∗abb∗is a solution.
(c) L 3 consists of all words beginning with one or morea’s followed by the same number ofb’s. There exists
no regular expressionrsuch thatL 3 =L(r); that is,L 3 is not a regular language. The proof of this fact
appears in Example 12.8.12.5Finite State Automata
Afinite state automaton(FSA) or, simply, anautomatonM, consists of five parts:
(1) A finite set (alphabet)Aof inputs.(2) A finite setSof (internal) states.
(3) A subsetYofS(called accepting or “yes” states).(4) An initial states 0 inS.
(5) A next-state functionFfromS×AintoS.