Information Technology Reference
In-Depth Information
b) Convert the nondeterministic finite-state machine of part (a) to a deterministic
finite-state machine by the method of Section 4.2 .
4.15 Describe an algorithm to convert a regular expression to an NFSM using the proof of
Theorem 4.4.1 .
4.16 Design DFSMs that recognize the following languages:
a) a bca
b) ( a + c ) ( ab + ca ) b
c) ( a b ( b + c ) )
4.17 Design an FSM that recognizes decimal strings (over the alphabet
{
0, 1, 2, 3, 4, 5, 6,
7, 8, 9
representing the integers whose value is 0 modulo 3.
Hint: Use the fact that ( 10 ) k = 1 mod 3 (where 10 is “ten”) to show that ( a k ( 10 ) k +
a k− 1 ( 10 ) k− 1 +
}
+ a 1 ( 10 ) 1 + a 0 )mod 3 =( a k + a k− 1 +
+ a 1 + a 0 )mod 3.
4.18 Use the above FSM design to generate a regular expression describing those integers
whose value is 0 modulo 3.
4.19 Describe an algorithm that constructs an NFSM from a regular expression r and accepts
astring w if w contains a string denoted by r that begins anywhere in w .
···
···
THE PUMPING LEMMA
4.20 Show that the following languages are not regular:
a)
a n ba n
L =
{
|
n
}
0
0 n 1 2 n 0 n
L =
{
|
n
}
b)
1
a n b n c n
}
4.21 Strengthen the pumping lemma for regular languages by demonstrating that if L is
a regular language over the alphabet Σ recognized by a DFSM with m states and it
contains a string w of length m or more, then any substring z of w ( w = uzv )of
length m can be written as z = rst ,where
c)
L =
{
|
n
0
|
s
|≥
1 such that for all integers n
0,
urs n tv
L . Explain why this pumping lemma is stronger than the one stated in
Lemma 4.5.1 .
4.22 Show that the language L =
a i b j
is not regular.
4.23 Show that the following language is not regular:
a)
{
|
i>j
}
u n zv m zw n + m
{
|
n , m
}
1
PROPERTIES OF REGULAR LANGUAGES
4.24 Use Lemma 4.5.1 and the closure property of regular languages under intersection to
show that the following languages are not regular:
a)
ww R
} }
{
|
w
∈{
0, 1
b)
{
ww
|
where w denotes w in which 0's and 1's are interchanged
}
}
4.25 Prove or disprove each of the following statements:
a) Every subset of a regular language is regular
c)
{
w
|
w has equal number of 0's and 1's
Search WWH ::




Custom Search