Solutions_RegularLanguages
1
Regular Languages
5 Finite State Machines
2 Build a deterministic FSM for each of the following languages:
a) {w Î {a, b}* : every a in w is immediately preceded and followed by b}.
b
b
1 b 2 3
a
b) {w Î {a, b}* : w does not end in ba}.
a
1
a
b 2
a
3 b
b
c) {w Î {0, 1}* : w corresponds to the binary encoding, without leading 0’s, of natural numbers that are
evenly divisible by 4}.
d) {w Î {0, 1}* : w corresponds to the binary encoding, without leading 0’s, of natural numbers that are
powers of 4}.
0
1 0
2
e) {w Î {0-9}* : w corresponds to the decimal encoding, without leading 0’s, of an odd natural number}.
2, 4, 6, 8 even
odd
1, 3, 5, 7, 9 even
odd
f) {w Î {0, 1}* : w has 001 as a substring}.
g) {w Î {0, 1}* : w does not have 001 as a substring}.
h) {w Î {a, b}* : w has bbab as a substring}.
a a, b
a b
a b
b b
a
i) {w Î {a, b}* : w has neither ab nor bb as a substring}.
a
a
a
b
3
j) {w Î {a, b}* : w has both aa and bb as a substrings}.
a
a b
a b
b a a, b
a
b b a a
b b
k) {w Î {a, b}* : w contains at least two b’s that are not immediately followed by a’s}.
a a, b
a a
b
b b
l) The set of binary strings with at most one pair of consecutive 0’s and at most one pair of consecutive 1’s.
0 1 1
0
1 0
0 1
0
1 1 0 0
1
m) {w Î {0, 1}* : none of the prefixes of w ends in 0}.
4
n) {wÎ {a, b}*: (#a(w) + 2×#b(w)) º5 0}. (#aw is the number of a’s in w).
9 For each of the following NDFSMs, use ndfsmtodfsm to construct an equivalent DFSM. Begin by showing the
value of eps(q) for each state q:
5
a)
b)
c)
a)
s eps(s)
q0 {q0, q1, q3}
q1 {q1, q3}
q2 {q2}
q3 {q3}
q4 {q2, q4, q5}
q5 {q5}
{q0, q1, q3} 0 {q2, q4, q5}
1 {q0, q1, q3}
{q2, q4, q5} 0 {q2, q4, q5}
1 {q1, q3, q5}
{q1, q3, q5} 0 {q2, q4, q5}
1 { }
1 0 0
0,1,3 0 2,4,5 1 1,3,5
6
b)
c)
s eps(s)
q0 {q0, q1}
q1 {q1}
q2 {q2}
q3 {q3, q0, q1}
q4 {q4}
q5 {q5}
{q0, q1} a {q2, q4}
b {q0, q1, q3}
{q2, q4} a {q1, q2, q4}
b {q0, q1, q3, q5}
{q0, q1, q3} a {q2, q4,}
b {q0, q1, q3}
{q1, q2, q4} a {q1, q2, q4}
b {q0, q1, q3, q5}
{q0, q1, q3, q5} a {q2, q4}
b {q0, q1, q3}
Accepting state is {q0, q1, q3, q5}. 1
11 For each of the following languages L:
(i) Describe the equivalence classes of »L.
(ii) If the number of equivalence classes of »L is finite, construct the minimal DFSM that accepts L.
a. {w Î {0, 1}* : every 0 in w is immediately followed by the string 11}.
[1] {in L}
[2] {otherwise in L except ends in 0}
[3] {otherwise in L except ends in 01}
[D] {corresponds to the Dead state: string contains at least one instance of 00 or 010}
1
[1] 0 [2] 1 [3]
0 0
1
D
0,1
b. {w Î {0, 1}* : w has either an odd number of 1’s and an odd number of 0’s or it has an even number
of 1’s and an even number of 0’s}.
c. {w Î {a, b}* : w contains at least one occurrence of the string aababa}.
7
d. {wwR : w Î {a, b}*}.
[1] {e} in L
[2] {a}
[3] {b}
[4] {aa} in L
[5] {ab}
And so forth. Every string is in a different equivalence class because each could become in L if followed
by the reverse of itself but not if followed by most other strings. This language is not regular.
12 Let M be the following DFSM. Use minDFSM to minimize M.
Initially, classes = {[1, 3], [2, 4, 5, 6]}.
At step 1:
((1, a), [2, 4, 5, 6]) ((3, a), [2, 4, 5, 6]) No splitting required here.
((1, b), [2, 4, 5, 6]) ((3, b), [2, 4, 5, 6])
((2, a), [1, 3]) ((4, a), [2, 4, 5, 6]) ((5, a), [2, 4, 5, 6]) ((6, a), [2, 4, 5, 6])
((2, b), [2, 4, 5, 6]) ((4, b), [1, 3]) ((5, b), [2, 4, 5, 6]) ((6, b), [1, 3])
These split into three groups: [2], [4, 6], and [5]. So classes is now {[1, 3], [2], [4, 6], [5]}.
At step 2, we must consider [4, 6]:
((4, a), [5]) ((6, a), [5])
((4, b), [1]) ((6, b), [1])
No further splitting is required. The minimal machine has the states: {[1, 3], [2], [4, 6], [5]}, with
transitions as shown above.
8
6 Regular Expressions
2 Write a regular expression to describe each of the following languages:
a) {w Î {a, b}* : every a in w is immediately preceded and followed by b}.
(b È bab)*
b) {w Î {a, b}* : w does not end in ba}.
e È a È (a È b)* (b È aa)
c) {w Î {0, 1}* : $y Î {0, 1}* (|xy| is even)}.
(0 È 1)*
d) {w Î {0, 1}* : w corresponds to the binary encoding, without leading 0’s, of natural numbers that are
evenly divisible by 4}.
(1(0 È 1)* 00) È 0
e) {w Î {0, 1}* : w corresponds to the binary encoding, without leading 0’s, of natural numbers that are
powers of 4}.
1(00)*
f) {w Î {0-9}* : w corresponds to the decimal encoding, without leading 0’s, of an odd natural number}.
(e È ((1-9)(0-9)*))(1 È 3 È 5 È 7 È 9)
g) {w Î {0, 1}* : w has 001 as a substring}.
(0 È 1)* 001 (0 È 1)*
h) {w Î {0, 1}* : w does not have 001 as a substring}.
(1 È 01)* 0*
i) {w Î {a, b}* : w has bba as a substring}.
(a È b)* bba (a È b)*
j) {w Î {a, b}* : w has both aa and bb as substrings}.
(a È b)* aa (a È b)* bb (a È b)* È (a È b)* bb (a È b)* aa (a È b)*
k) {w Î {a, b}* : w has both aa and aba as substrings}.
(a È b)* aa (a È b)* aba (a È b)* È
(a È b)* aba (a È b)* aa (a È b)* È
(a È b)* aaba (a È b)* È
(a È b)* abaa (a È b)*
9
l) {w Î {a, b}* : w contains at least two b’s that are not followed by an a}.
(a È b)* bb È (a È b)* bbb (a È b)*
m) {w Î {0, 1}* : w has at most one pair of consecutive 0’s and at most one pair of consecutive 1’s}.
(e È 1)(01)*(e È 1) (01)* (e È (00 (e È (1 (01)* (e È 0))))) /* 11 comes first.
È
(e È 0) (10)* (e È 0) (10)* (e È (11 (e È (0 (10)* (e È 1))))) /* 00 comes first.
n) {w Î {0, 1}* : none of the prefixes of w ends in 0}.
1*
o) {w Î {a, b}* : #a(w) º3 0}.
(b*ab*ab*a)*b*
p) {w Î {a, b}* : #a(w) £ 3}.
b* (a È e) b* (a È e) b* (a È e) b*
q) {w Î {a, b}* : w contains exactly two occurrences of the substring aa}.
(b È ab)*aaa(b È ba)* È (b È ab)*aab(b È ab)*aa(b È ba)* (Either the two occurrences are
contiguous, producing aaa, or they’re not.)
r) {w Î {a, b}* : w contains no more than two occurrences of the substring aa}.
(b È ab)*(a È e) /* 0 occurrences of the substring aa
È
(b È ab)*aa(b È ba)* /* 1 occurrence of the substring aa
È
(b È ab)*aaa(b È ba)* È (b È ab)*aab(b È ab)*aa(b È ba)*
/* 2 occurrences of the substring aa
s) {w Î {a, b}* – L}, where L = {w Î {a, b}* : w contains bba as a substring}.
(a È ba)* (e È b È bbb*) = (a È ba)*b*
t) {w Î {0, 1}* : every odd length string in L begins with 11}.
((0 È 1)(0 È 1))* È 11(0 È 1)*
u) {w Î {0-9}* : w represents the decimal encoding of an odd natural number without leading 0’s.
(e È ((1-9)(0-9)*))(1 È 3 È 5 È 7 È 9)
10
v) L1 – L2, where L1 = a*b*c* and L2 = c*b*a*.
a+b+c* È a+b*c+ È a*b+c+ (The only strings that are in both L1 and L2 are strings composed of no more
than one different letter. So those are the strings that we need to remove from L1 to form the difference.
What we’re left with is strings that contain two or more distinct letters.)
3 Simplify each of the following regular expressions:
a. (a È b)* (a È e) b*.
(a È b)*.
b. (Æ* È b) b*.
b*.
c. (a È b)*a* È b.
(a È b)*.
d. ((a È b)*)*.
(a È b)*.
e. ((a È b)+)*.
(a È b)*.
f. a ( (a È b)(b È a) )* È a ( (a È b) a )* È a ( (b È a) b )*.
a ( (a È b)(b È a) )*.
9 Consider the following FSM M:
The first printing of the book has two mistakes in this figure: The transition from q2 back to q0 should be
labeled a, and state q3 should not be accepting. We’ll give answers for the printed version (in which we’ll
simply ignore the unlabeled transition from q2 to q0) and the correct version.
a. Show a regular expression for L(M).
Printed version: a* È a*bb* È a*bb*a È a*bb*ab (a È b)*
Correct version: (a È bb*aa)* (e È bb*(a È e)).
13 Show a possibly nondeterministic FSM to accept the language defined by each of the following regular
expressions:
11
a) (((a È ba) b È aa)*.
b) (b È e)(ab)*(a È e).
c) (babb* È a)*.
d) (ba È ((a È bb) a*b)).
1 b 2 a 3
b a
a
4 b 5 b 6
e) (a È b)* aa (b È aa) bb (a È b)*.
a,b a,b
a a a a a a
b
14 Show a DFSM to accept the language defined by each of the following regular expressions:
a. (aba È aabaa)*
a
a
a a,b
b b
b b
a a
a,b b
12
b. (ab)*(aab)*
a
a a
b
b a b
b
a
b
a,b
15 Consider the following FSM M:
The first printing of the book has a mistake in this figure: There should not be an a labeling the transition
from q1 to q3.
a. Write a regular expression that describes L(M).
Printed (in book) version: e È ((a È ba)(ba)*b È a)
Correct version: e È ((a È ba)(ba)*b).
b. Show a DFSM that accepts ¬L(M).
This is for the correct version (without the extra label a):
a
{1} {2, 3}
b
a
{0} a b
b a
{2} Æ a,b
b
13
8 Regular and Nonregular Languages
1) For each of the following languages L, state whether or not L is regular. Prove your answer:
a) {aibj : i, j ≥ 0 and i + j = 5}.
Regular. A simple FSM with five states just counts the total number of characters.
b) {aibj : i, j ≥ 0 and i – j = 5}.
Not regular. L consists of all strings of the form a*b* where the number of a’s is five more than the
number of b’s. We can show that L is not regular by pumping. Let w = ak+5bk. Since |xy| £ k, y must equal
ap for some p > 0. We can pump y out once, which will generate the string ak+5-pbk, which is not in L
because the number of a’s is is less than 5 more than the number of b’s.
c) {aibj : i, j ≥ 0 and |i – j| º5 0}.
Regular. Note that i – j º5 0 iff i º5 j. L can be accepted by a straightforward FSM that counts a’s (mod 5).
Then it counts b’s (mod 5) and accepts iff the two counts are equal.
d) {w Î {0, 1, #}* : w = x#y, where x, y Î {0, 1}* and |x|×|y| º5 0}. (Let × mean integer multiplication).
Regular. For |x| × |y| to be divisible by 5, either |x| or |y| (or both) must be divisible by 5. So L is defined by
the following regular expression:
((0 È 1)5)*#(0 È 1)* È (0 È 1)*#((0 È 1)5)*, where (0 È 1)5 is simply a shorthand for writing (0 È 1)
five times in a row.
e) {aibj : 0 £ i < j < 2000}.
Regular. Finite.
f) {w Î {Y, N}* : w contains at least two Y’s and at most two N’s}.
Regular. L can be accepted by an FSM that keeps track of the count (up to 2) of Y’s and N’s.
g) {w = xy : x, y Î {a, b}* and |x| = |y| and #a(x) ³ #a(y)}.
Not regular, which we’ll show by pumping. Let w = akbbak. y must occur in the first a region and be
equal to ap for some nonzero p. Let q = 0. If p is odd, then the resulting string is not in L because all
strings in L have even length. If p is even it is at least 2. So both b’s are now in the first half of the string.
That means that the number of a’s in the second half is greater than the number in the first half. So
resulting string, ak-pbbak, is not in L.
h) {w = xyzyRx : x, y, z Î {a, b}*}.
Regular. Note that L = (a È b)*. Why? Take any string s in (a È b)*. Let x and y be e. Then s = z. So
the string can be written in the required form. Moral: Don’t jump too fast when you see the nonregular
“triggers”, like ww or wwR. The entire context matters.
14
i) {w = xyzy : x, y, z Î {0, 1}+}.
Regular. The key to why this is so is to observe that we can let y be just a single character. Then the rest of
w can generated by x and z. So any string w in {0, 1}+ is in L iff:
• the last letter of w occurs in at least one other place in the string,
• that place is not the next to the last character,
• nor is it the first character, and
• w contains least 4 letters.
Either the last character is 0 or 1. So:
L = ((0 È 1)+ 0 (0 È 1)+ 0) È ((0 È 1)+ 1 (0 È 1)+ 1).
j) {w Î {0, 1}* : #0(w) ¹ #1(w)}.
Not regular. This one is quite hard to prove by pumping. Since so many strings are in L, it’s hard to show
how to pump and get a string that is guaranteed not to be in L. Generally, with problems like this, you want
to turn them into problems involving more restrictive languages to which it is easier to apply pumping. So:
if L were regular, then the complement of L, L¢ would also be regular.
L¢ = {w Î {0, 1}* : #0(w) = #1(w)}.
It is easy to show, using pumping, that L¢ is not regular: Let w = 0k1k. y must occur in the initial string of
0’s, since |xy| £ k. So y = 0i for some i ³ 1. Let q of the pumping theorem equal 2 (i.e., we will pump in
one extra copy of y). We now have a string that has more 0’s than 1’s and is thus not in L¢. Thus L¢ is not
regular. So neither is L. Another way to prove that L¢ isn’t regular is to observe that, if it were, L¢¢ = L¢ Ç
0*1* would also have to be regular. But L¢¢ is 0n1n, which we already know is not regular.
k) {w Î {a, b}* : w = wR}.
Not regular, which we show by pumping. Let w = akbkbkak. So y must be ap for some nonzero p. Pump in
once. Reading w forward there are more a’s before any b’s than there are when w is read in reverse. So
the resulting string is not in L.
l) {w Î {a, b}* : $x Î {a, b}+ (w = x xR x)}.
Not regular, which we show by pumping: Let w = akbbakakb. y must occur in the initial string of a’s,
since |xy| £ k. So y = ai for some i ³ 1. Let q of the pumping theorem equal 2 (i.e., we will pump in one
extra copy of y). That generates the string ak+ibbakakb. If this string is in L, then we must be able to
divide it into thirds so that it is of the form x xR x. Since its total length is 3k + 3 + i, one third of that
(which must be the length of x) is k + 1 + i/3. If i is not a multiple of 3, then we cannot carve it up into
three equal parts. If i is a multiple of 3, we can carve it up. But then the right boundary of x will shift two
characters to the left for every three a’s in y. So, if i is just 3, the boundary will shift so that x no longer
contains any b’s If i is more than 3, the boundary will shift even farther away from the first b. But there
are b’s in the string. Thus the resulting string cannot be in L. Thus L is not regular.
m) {w Î {a, b}* : the number of occurrences of the substring ab equals the number of occurrences of the
substring ba}.
Regular. The idea is that it’s never possible for the two counts to be off by more than 1. For example, as
soon as there’s an ab, there can be nothing but b’s without producing the first ba. Then the two counts are
equal and will stay equal until the next b. Then they’re off by 1 until the next a, when they’re equal again.
L = a*È a+b+a+(b+a+)* È b* È b+a+b+(a+b+)*.
15
n) {w Î {a, b}* : w contains exactly two more b’s than a’s}.
Not regular, which we’ll show by pumping. Let w = akbk+2. y must equal ap for some p > 0. Set q to 0
(i.e., pump out once). The number of a’s changes, but the number of b’s does not. So there are no longer
exactly 2 more b’s than a’s.
o) {w Î {a, b}* : w = xyz, |x| = |y| = |z|, and z = x with every a replaced by b and every b replaced by a}.
Example: abbbabbaa Î L, with x = abb, y = bab, and z = baa.
Not regular, which we’ll show by pumping. Let w = akakbk. This string is in L since x = ak, y = ak, and z =
bk. y (from the pumping theorem) = ap for some nonzero p. Let q = 2 (i.e., we pump in once). If p is not
divisible by 3, then the resulting string is not in L because it cannot be divided into three equal length
segments. If p = 3i for integer i, then, when we divide the resulting string into three segments of equal
length, each segment gets longer by i characters. The first segment is still all a’s, so the last segment must
remain all b’s. But it doesn’t. It grows by absorbing a’s from the second segment. Thus z no longer = x
with every a replaced by b and every b replaced by a. So the resulting string is not in L.
p) {w: w Î {a – z}* and the letters of w appear in reverse alphabetical order}. For example, spoonfeed Î
L.
Regular. L can be recognized by a straightforward 26-state FSM.
q) {w: w Î {a – z}* every letter in w appears at least twice}. For example, unprosperousnessÎ L.
Regular. L can be recognized by an FSM with 263 states.
r) {w : w is the decimal encoding of a natural number in which the digits appear in a non-decreasing order
without leading zeros}.
Regular. L can be recognized by an FSM with 10 states that checks that the digits appear in the correct
order. Or it can be described by the regular expression: 0*1*2*3*4*5*6*7*8*9*.
s) {w of the form:
and
124+5=129 Î L.
Not regular.
t) L0*, where L0 = {baibjak, j ³ 0, 0 £ i £ k}.
Regular. Both i and j can be 0. So L = (b+a*)*.
u) {w : w is the encoding (in the scheme we describe next) of a date that occurs in a year that is a prime
number}. A date will be encoded as a string of the form mm/dd/yyyy, where each m, d, and y is drawn from
{0-9}.
Regular. Finite.
v) {w Î {1}* : w is, for some n ³ 1, the unary encoding of 10n}. (So L = {1111111111, 1100, 11000, …}.)
Not regular, which we can prove by pumping. Let w = 1t, where t is the smallest integer that is a power of
ten and is greater than k. y must be 1p for some nonzero p. Clearly, p can be at most t. Let q = 2 (i.e.,
16
pump in once). The length of the resulting string s is at most 2t. But the next power of 10 is 10t. Thus s
cannot be in L.
2) For each of the following languages L, state whether L is regular or not and prove your answer:
a) {w Î {a, b, c}* : in each prefix x of w, #a(x) = #b(x) = #c(x))}.
Regular. L = {e}.
b) {w Î {a, b, c}* : $ some prefix x of w (#a(x) = #b(x) = #c(x))}.
Regular. L = S*, since every string has e as a prefix.
c) {w Î {a, b, c}* : $ some prefix x of w (x ¹ e and #a(x) = #b(x) = #c(x))}.
Not regular, which we prove by pumping. Let w = a2kba2k.
3) Define the following two languages:
La = {w Î {a, b}* : in each prefix x of w, #a(x) ³ #b(x)}.
Lb = {w Î {a, b}* : in each prefix x of w, #b(x) ³ #a(x)}.
a) Let L1 = La Ç Lb. Is L1 regular? Prove your answer.
Regular. L1 = {e}.
b) Let L2 = La È Lb. Is L2 regular? Prove your answer.
Not regular. First, we observe that L2 = {e} È {w: the first character of w is an a and w Î La}
È {w: the first character of w is a b and w Î Lb}
We can show that L2 is not regular by pumping. Let w = a
2kb2k. y must be ap for some 0 < p £ k. Pump out. The resulting string w¢ = a2k-pb2k. Note that w¢ is a prefix of itself. But it is not in L2 because it is not e, nor is it in La (because it has more b’s than a’s) or in Lb (because it has a as a prefix). 4) For each of the following languages L, state whether L is regular or not and prove your answer: a) {uwwRv : u, v, w Î {a, b}+}. Regular. Every string in L has at least 4 characters. Let w have length 1. Then wwR is simply two identical characters next to each other. So L consists of exactly those strings of at least four characters such that there’s a repeated character that is not either the first or last. Any such string can be rewritten as u (all the characters up to the first repeated character) w (the first repeated character) wR (the second repeated character) v (all the rest of the characters). So L = (a È b)+ (aa È bb) (a È b)+. 17 b) {xyzyRx : x, y, z Î {a, b}+}. Not regular, which we show by pumping. Let w = akbabaakb. Note that w is in L because, using the letters from the language definition, x = akb, y = a, and z =b. Then y (from the Pumping Theorem) must occur in the first a region. It is ap for some nonzero p. Set q to 2 (i.e., pump in once). The resulting string is ak+pbabaakb. This string cannot be in L. Since its initial x (from the language definition) region starts with a, there must be a final x region that starts with a. Since the final x region ends with a b, the initial x region must also end with a b. So, thinking about the beginning of the string, the shortest x region is ak+pb. But there is no such region at the end of the string unless p is 1. But even in that case, we can’t call the final aakb string x because that would leave only the middle substring ab to be carved up into yzyR. But since both y and z must be nonempty, yzyR must have at least three characters. So the resulting string cannot be carved up into xyzyRx and so is not in L. 21 For each of the following claims, state whether it is True or False. Prove your answer.: c) There are uncountably many non-regular languages over S = {a, b}. True. There are uncountably many languages over S = {a, b}. Only a countably infinite number of those are regular. d) The union of an infinite number of regular languages must be regular. False. Let L = È ({e}, {ab}, {aabb}, {aaabbb}, …) Each of these languages is finite and thus regular. But the infinite union of them is {anbn , n ³ 0}, which is not regular. e) The union of an infinite number of regular languages is never regular. Nothing says the languages that are being unioned have to be different. So, Let L = È (a*, a*, a*, …), which is a*, which is regular. f) If L1 and L2 are not regular languages, then L1 È L2 is not regular. False. Let L1 = {a p : p is prime}. Let L2 = {a p : p is greater than 0 and not prime}. Neither L1 nor L2 is regular. But L1 È L2 = a +, which is regular. g) If L1 and L2 are regular languages, then L1 Ä L2 = {w : w Î (L1 - L2) or w Î (L2 - L1)} is regular. True. The regular languages are closed under union and set difference. h) If L1 and L2 are regular languages and L1 Í L Í L2, then L must be regular. False. Let L1 = Æ. Let L2 = {a È b)*. Let L = {a nbn : n ³ 0}, which is not regular. i) The intersection of a regular language and a nonregular language must be regular. False. Let L1 = (a È b)*, which is regular. Let L2 = {a nbn , n ³ 0}, which is not regular. Then L1 Ç L2 = {anbn , n ³ 0}, which is not regular. A simpler example is: Let L1 = a*, which is regular. Let L2 = {a p: p is prime}, which is not regular. L1 Ç L2 = L2. j) The intersection of a regular language and a nonregular language must not be regular. False. Let L1 = {ab} (regular). Let L2 = {a nbn , n ³ 0} (not regular). L1 Ç L2 = {ab}, which is regular. 18 k) The intersection of two nonregular languages must not be regular. False. Let L1 = {a p: p is prime}, which is not regular. Let L2 ={b p: p is prime}, which is also not regular. L1 Ç L2 = Æ, which is regular. l) The intersection of a finite number of nonregular languages must not be regular. False. Since two is a finite number, we can used the same counterexample that we used above in part i. Let L1 = {a p: p is prime}, which is not regular. Let L2 ={b p: p is prime}, which is also not regular. L1 Ç L2 = Æ, which is regular. m) It is possible that the concatenation of two nonregular languages is regular. True. To prove this, we need one example: Let L1 = {a ibj, i, j ³ 0 and i ¹ j}. Let L2 = {b nam, n, m ³ 0 and n ¹ m. L1L2 = {a ibjak such that: • If i and k are both 0 then j ³ 2. • If i = 0 and k ¹ 0 then j ³ 1. • If i ¹ 0 and k = 0 then j ³ 1. • If i and k are both 1 then j ¹ 1. • Otherwise, j ³ 0}. In other words, L1L2 is almost a*b*a*, with a small number of exceptions that can be checked for by a finite state machine. n) It is possible that the union of a regular language and a nonregular language is regular. True. Let L1 = a*, which is regular. Let L2 = {a p: 2 £ p and p is prime}, which is not regular. L1 È L2 = a*, which is regular. o) If L is a language that is not regular, then L* is not regular. False. Let L = Primea = {a n : n is prime}. L is not regular. L* = {e} È {an : 1 < n}. L* is regular. p) If L* is regular, then L is regular. False. Let L = Primea = {a n : n is prime}. L is not regular. L* = {e} È {an : 1 < n}. L* is regular. q) The nonregular languages are closed under intersection. False. Let L1 = {a nbn, where n is even}. L1 is not regular. Let L2 = {a nbn, where n is odd}. L2 is not regular. L = L1 Ç L2 = Æ, which is regular. r) Every subset of a regular language is regular. False. Let L = a*, which is regular. Let L' = ap, where p is prime. L' is not regular, but it is a subset of L. 19 s) Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular. True. Example: Let L1 = {e}. L1 is regular. Let L2 = a*. L2 is regular. Let L3 = a p, where p is prime. L3 is not regular. L4 = a k, where k ³ 2 L4 is regular, because it is defined by aaa*. t) If L is regular, then so is {xy : x Î L and y Ï L}. True. {xy : x Î L and y Ï L} can also be described as the concatenation of L and ¬L. Since the regular languages are closed under complement, this means that it is the concatenation of two regular languages. The regular languages are closed under complement. u) Every infinite regular language properly contains another infinite regular language. True. Let L be an infinite regular language and let w be a string in L. Then L - {w} is also both infinite and regular. 20 9 Decision Procedures for Regular Languages 1) Define a decision procedure for each of the following questions. Argue that each of your decision procedures gives the correct answer and terminates. a) Given two DFSMs M1 and M2, is L(M1) = L(M2)R? 1. From M1, construct MR, which accepts L(M1)R, using the algorithm presented in the solution to Exercise 8.7 (c). 2. Determine whether M1 and M2 accept the same language, using the algorithm equalFSMs, presented in Section 9.1.4. b) Given two DFSMs M1 and M2 is |L(M1)| < |L(M2)|? 1. If L(M1) is infinite, return False. 2. If L(M2) is infinite, return True. /* Now we know that both languages are finite. We need to count the number of elements in each. 3. Run every string in SM1* of length less than |KM1| through M1, counting the number that are accepted. Call that number C1. 4. Run every string in SM2* of length less than |KM2| through M2, counting the number that are accepted. Call that number C2. 5. If C1 < C2 then return True. Else return False. c) Given a regular grammar G and a regular expression a, is L(G) = L(a)? 1. From G, create a NDFSM MG that accepts L(G). 2. From a, create an FSM Ma that accepts L(a). 3. Determine whether MG and Ma are equivalent. d) Given two regular expressions, a and b, do there exist any even length strings that are in L(a) but not L(b)? 1. From a, build FSM Ma, such that L(Ma) = L(a). 2. From b, build FSM Mb, such that L(Mb) = L(b). 3. Build Meven, such that L(Meven) = the set of all even length strings over the alphabet Sa. 4. Build M¢a, such that L(M¢a) = L(Ma) Ç L(Meven). 5. Build M¢¬b to accept the complement of L(Mb). 6. Build MF, such that L(MF) = L(M¢a) Ç L(M¢¬b). 7. If L(MF) is not empty, return True. Else return False. e) Let S = {a, b} and let a be a regular expression. Does the language generated by a contains all the even length strings in S*. 1. From a, build FSM Ma, such that L(Ma) = L(a). 2. Build M1 to accept all even length strings over S. 4. Build M2 to accept L(M1) - L(Ma). 5. See if L(M2) is empty. If it is, return True. Else return False. 21 f) Given an FSM M and a regular expression a, is it true that L(M) and L(a) are both finite and M accepts exactly two more strings than a generates? 1. From a, build FSM P, such that L(P) = L(a). 2. If L(M) is infinite, return False. 3. If L(P) is infinite, return False. /* Now we know that both languages are finite. Thus neither machine accepts any strings of length equal to or greater than the number of states it contains. So we simply count the number of such “short” strings that each machine accepts. 4. Run every string in SM* of length less than |KM| through M, counting the number that are accepted. Call that number CM. 5. Run every string in SP* of length less than |KP| through P, counting the number that are accepted. Call that number CP. 6. If CM = CP+2, return True; else return False.