320 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12
LANGUAGES
12.34. LetL={a^2 ,ab}andK={a, ab, b^2 }. Find: (a)LK; (b)KL; (c)L∨K; (d)K∧L.
12.35. LetL={a^2 ,ab}. Find: (a)L^0 ; (b)L^2 ; (c)L^3.
12.36. LetA={a, b, c}. DescribeL* if: (a)L={a^2 }; (b)L={a, b^2 }; (c)L={a, b^2 ,c^3 }.
12.37. Does (L^2 )∗=(L∗)^2? If not, how are they related?
12.38. Consider a countable alphabetA={a 1 ,a 2 ,···}. LetLkthe language overAconsisting of those wordswsuch that
the sum of the subscripts of the letters inwis equal tok. (See Problem 12.10.) Find: (a)L 3 ;(b)L 5.REGULAR EXPRESSIONS, REGULAR LANGUAGES
12.39. LetA={a, b, c}. Describe the languageL(r)for each of the following regular expressions:(a) r=ab∗c; (b) r=(ab∨c)∗; (c) r=ab∨c∗.12.40. LetA={a, b}. Find a regular expressionrsuch thatL(r)consists of all wordswwhere:(a) wcontains exactly threea’s.
(b) The number ofa’s is divisible by 3.12.41. LetA={a, b, c}and letw=ac. State whether or notwbelongs toL(r)where:(a)r=a∗bc∗; (b)r=a∗b∗c; (c)r=(ab∨c)∗12.42. LetA={a, b, c}and letw=abc. State whether or notwbelongs toL(r)where:(a)r=ab∗(bc)∗; (b)r=a∗∨(b∨c)∗; (c) r=a∗b(bc∨c^2 )∗.FINITE AUTOMATA
12.43. LetA={a, b}. Construct an automatonMsuch thatL(M)will consist of those wordswwhere:
(a) the number ofb’s is divisible by 3. (b)wbegins withaand ends inb.
12.44. LetA={a, b}. Construct an automatonMwhich will accept the language:(a) L(M)={brabs|r> 0 ,s> 0 }; (b) L(M)={arbs|r> 0 ,s> 0 }.12.45. LetA={a, b}. Construct an automatonMsuch thatL(M)will consist of those words where the number ofa’s is
divisible by 2 and the number ofb’s is divisible by 3.
(Hint: Use Problems 12.15, 12.43(a), and 12.20.)
12.46. Find the languageL(M)accepted by the automatonMin Fig. 12-11.Fig. 12-11