CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 315
LANGUAGES
12.6. LetA={a, b}. Describe verbally the following languages overA(which are subsets ofA*):
(a)L 1 ={(ab)m|m> 0 };(b) L 2 ={arbasbat|r, s, t≥ 0 };(c)L 3 ={a^2 bma^3 |m> 0 }.
(a) L 1 consists of wordsw=ababab···ab, that is, beginning witha, alternating withb, and ending withb.
(b) L 2 consists of all words with exactly twob’s.
(c) L 3 consists of all words beginning witha^2 and ending witha^3 with one or moreb’s between them.
12.7. LetK={a, ab, a^2 }andL={b^2 ,aba}be languages overA={a, b}. Find: (a)KL;(b)LL.
(a) Concatenate words inKwith words inLto obtainKL={ab^2 ,a^2 ba, ab^3 , ababa, a^2 b^2 ,a^3 ba}.
(b) Concatenate words inLwith words inLto obtainLL={b^4 ,b^2 aba, abab^2 ,aba^2 ba}.
12.8. Consider the languageL={ab, c}overA={a, b, c}. Find: (a)L^0 ;(b)L^3 ;(c)L−^2.
(a) L^0 ={l}, by definition.
(b) Form all three-word sequences fromLto obtain:
L^3 ={ababab, ababc, abcab, abc^2 , cabab, cabc, c^2 ab, c^3 }
(c) The negative power of a language is not defined.
12.9. LetA={a, b, c}. FindL∗where: (a)L={b^2 };(b)L={a, b};(c)L={a, b, c^3 }.
(a) L∗consists of all wordsbnwherenis even (including the empty wordl).
(b) L∗consists of words inaandb.
(c) L∗consists of all words fromAwith the property that the length of each maximal subword composed entirely of
c’s is divisible by 3.
12.10. Consider a countable alphabetA={a 1 ,a 2 ,...}. LetLkbe the language overAconsisting of those words
wsuch that the sum of the subscripts of the letters inwis equal tok. (For example,w=a 2 a 3 a 3 a 6 a 4
belongs toL 18 .) (a) FindL 4 .(b) Show thatLkis finite. (c) Show thatA* is countable. (d) Show
that any language overAis countable.
(a) No word inL 4 can have more than four letters, and no letteranwithn>4 can be used.
Thus we obtain the following list:
a 1 a 1 a 1 a 1 ,a 1 a 1 a 2 ,a 1 a 2 a 1 ,a 2 a 1 a 1 ,a 1 a 3 ,a 3 a 1 ,a 2 a 2 ,a 4
(b) Only a finite number of thea’s, that is,a 1 ,a 2 ,...,ak, can be used inLkand no word inLkcan have
more thankletters. ThusLkis finite.
(c) A* is the countable union of the finite setsLk; henceA* is countable.
(d) Lis a subset of the countable setA*; henceLis also countable.
REGULAR EXPRESSIONS, REGULAR LANGUAGES
12.11. LetA={a, b}. Describe the languageL(r)where:
(a) r=abb∗a; (b) r=b∗ab∗ab∗; (c) r=a∗∨b∗; (d) r=ab∗∧a∗.
(a) L(r)consists of all words beginning and ending inaand enclosing one or moreb’s.
(b) L(r)consists of all words with exactly twoa’s.
(c) L(r)consists of all words only inaor only inb, that is,L(r)={l,a,a^2 ,···,b,b^2 ,···}
(d) Hereris not a regular expression since∧is not one of the symbols used in forming regular expressions.