1
$\begingroup$

I am currently studying the textbook Speech and Language Processing, 3rd edition (draft), by Jurafsky and Martin. Chapter 2.1.1 Basic Regular Expression Patterns says the following:

The regular expression $\text{/[1234567890]/}$ specifies any single digit. While such classes of characters as digits or letters are important building blocks in expressions, they can get awkward (e.g., it's inconvenient to specify

$$\text{/[ABCDEFGHIJKLMNOPQRSTUVWXYZ]/}$$

to mean "any capital letter"). In cases where there is a well-defined sequence associated with a set of characters, the brackets can be used with the dash (-) to specify any one character in a range. The pattern $\text{/[2-5]/}$ specifies any one of the characters 2, 3, 4, or 5. The pattern $\text{/[b-g]/}$ specifies one of the characters b, c, d, e, f, or g. Some other examples are shown in Fig. 2.3. enter image description here

It then says the following:

This language consists of strings with a b, followed by at least two a's, followed by an exclamation point. The set of operators that allows us to say things like "some number of as" are based on the asterisk or $\ast$, commonly called the Kleene $\ast$ (generally pronounced "cleany star"). The Kleene star means "zero or more occurrences of the immediately previous character or regular expression". So $\text{/a$\ast$/}$ means "any string of zero or more as". This will match a or aaaaaa, but it will also match Off Minor since the string Off Minor has zero a's. So the regular expression for matching one or more a is $\text{/aa$\ast$/}$, meaning one a followed by zero or more as. More complex patterns can also be repeated. So $\text{/[ab]$\ast$/}$ means "zero or more a's or b's" (not "zero or more right square braces"). This will match strings like aaaa or ababab or bbbb.
For specifying multiple digits (useful for finding prices) we can extend $\text{/[0-9]/}$, the regular expression for a single digit. An integer (a string of digits) is thus $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)

I don't understand why an integer (a string of digits) isn't $\text{/[0-9]$\ast$/}$. For $\text{/[0-9][0-9]$\ast$/}$, it seems to me that, if we go by order of precedence, the first $\text{[0-9]}$ is a single digit, and then $\text{[0-9]$\ast$}$ is the next zero or more occurrences of digits, so this part makes sense. But it seems to me that $\text{/[0-9]$\ast$/}$ would just be the next zero or more occurrences of digits, so it seems that that would work as well, no? What am I misunderstanding here for $\text{/[0-9][0-9]$\ast$/}$ and $\text{/[0-9]$\ast$/}$?

$\endgroup$
5
$\begingroup$

The empty word $\epsilon$ isn't an integer. Integers are $0, 1, 2, 3, \dots, 10, 11, \dots$

Clearly none of them have $0$ letters when you write them, and hence they are not $\epsilon$.

Hence, you want an integer to be of the form $\text{/[0-9][0-9]$^\ast$/}$.

$\endgroup$
2
  • $\begingroup$ What do you mean by “empty word $\epsilon$”? $\endgroup$ Jun 22 at 11:43
  • 1
    $\begingroup$ $\epsilon$ is denoted to express the word without any letters in it. Literally. if you write $a\epsilon$ it becomes just $a$. Take a look at this wikipedia page, it might be helpful: en.wikipedia.org/wiki/Empty_string $\endgroup$
    – nir shahar
    Jun 22 at 11:45
2
$\begingroup$

$[0-9]*$ includes all finite strings of the digits including the empty string $\epsilon$ (Some books denote the empty string by $\lambda$). An integer, by definition, has at least one digit. Hence, $[0-9][0-9]*$ is the correct definition. It is not possible to obtain an empty string from this definition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.