Java Reference
In-Depth Information
22. Write Lex regular expressions (using character classes if you wish) that
match the following sets of strings:
(a) The set of all unprintable ASCII characters (those before the blank
and the very last character)
(b) The string ["""] (that is, a left bracket, three double quotes, and a
right bracket)
(c) The string
x
345
(your solution should be far less than 12,345 char-
acters in length)
12
,
23. Write a Lex program that examines the words in an ASCII file and lists
the ten most frequently used words. Your program should ignore case
and should ignore words that appear in a predefined “don't care” list.
What changes in your program are needed to make it recognize singular
and plural nouns (for example, cat and cats) as the same word? How
about di
ff
erent verb tenses (walk versus walked versus walking)?
24. Let
Double
be the set of strings defined as
.
Double
contains
only strings composed of two identical repeated pieces. For example, if
you have a vocabulary of the ten digits 0 to 9, then the following strings
(and many more!) are in
Double
: 11, 1212, 123123, 767767, 98769876, . . . .
Assume you have a vocabulary consisting only of the single letter
a
.Is
Double
a regular set? Why or why not?
Assume you now have a vocabulary consisting of the two letters,
a
and
b
. Is Double a regular set? Why or why not?
{
s
|
s
=
ww
}
25. Let
Seq
(
x
,
y
) be the set of all strings (of length 1 or more) composed of
alternating
x
's and
y
's. For example,
Seq
(
a
,
b
)contains
a
,
b
,
ab
,
ba
,
aba
,
bab
,
abab
,
baba
,andsoon.
Write a regular expression that defines
Seq
(
x
,
y
).
Let
S
be the set of all strings (of length 1 or more) composed of
a
's,
b
's,
and
c
's that start with an
a
and in which no two adjacent characters are
equal. For example,
S
contains
a
,
ab
,
abc
,
abca
,
acab
,
acac
,... butnot
c
,
aa
,
abb
,
abcc
,
aab
,
cac
, . . . . Write a regular expression that defines
S
.Youmay
use
Seq
(
x
,
y
) within your regular expression if you wish.
26. Let
AllButLast
be a function that returns all of a string but its last character.
For example,
AllButLast
(
abc
)
=
ab
.
AllButLast
(
λ
) is undefined. Let
R
be
any regular expression that does not generate
.
AllButLast
(
R
)istheset
of strings denoted by
R
,with
AllButLast
applied to each string. Thus,
AllButLast
(
a
+
b
)
λ
=
a
+
. Show that
AllButLast
(
R
) is a regular set.
