While this can make the result plausible, a rigorous proof requires that we
show that each step in the process generates an equivalent GTG. This is a
technical matter we leave to the reader.
Regular Expressions for Describing Simple Patterns
In Example 1.15 and in Exercise 16, Section 2.1, we explored the connection
between finite accepters and some of the simpler constituents of programming
languages, such as identifiers, or integers and real numbers. The relation
between finite automata and regular expressions means that we can also use
regular expressions as a way of describing these features. This is easy to see; for
example, in many programming languages the set of integer constants is defined
by the regular expression
sdd*,
where s stands for the sign, with possible values from { + , -,λ}, and d stands for
the digits 0 to 9. Integer constants are a simple case of what is sometimes called
a “pattern,” a term that refers to a set of objects having some common properties.
Pattern matching refers to assigning a given object to one of several categories.
Often, the key to successful pattern matching is finding an effective way to
describe the patterns. This is a complicated and extensive area of computer
science to which we can only briefly allude. The following example is a
simplified, but nevertheless instructive, demonstration of how the ideas we have
talked about so far have been found useful in pattern matching.
Example 3.12
An application of pattern matching occurs in text editing. All text editors allow
files to be scanned for the occurrence of a given string; most editors extend this
to permit searching for patterns. For example, the vi editor in the UNIX
operating system recognizes the command /aba*c/ as an instruction to search the
file for the first occurrence of the string ab, followed by an arbitrary number of
a’s, followed by a c. We see from this example the need for pattern-matching
editors to work with regular expressions.
show that each step in the process generates an equivalent GTG. This is a
technical matter we leave to the reader.
Regular Expressions for Describing Simple Patterns
In Example 1.15 and in Exercise 16, Section 2.1, we explored the connection
between finite accepters and some of the simpler constituents of programming
languages, such as identifiers, or integers and real numbers. The relation
between finite automata and regular expressions means that we can also use
regular expressions as a way of describing these features. This is easy to see; for
example, in many programming languages the set of integer constants is defined
by the regular expression
sdd*,
where s stands for the sign, with possible values from { + , -,λ}, and d stands for
the digits 0 to 9. Integer constants are a simple case of what is sometimes called
a “pattern,” a term that refers to a set of objects having some common properties.
Pattern matching refers to assigning a given object to one of several categories.
Often, the key to successful pattern matching is finding an effective way to
describe the patterns. This is a complicated and extensive area of computer
science to which we can only briefly allude. The following example is a
simplified, but nevertheless instructive, demonstration of how the ideas we have
talked about so far have been found useful in pattern matching.
Example 3.12
An application of pattern matching occurs in text editing. All text editors allow
files to be scanned for the occurrence of a given string; most editors extend this
to permit searching for patterns. For example, the vi editor in the UNIX
operating system recognizes the command /aba*c/ as an instruction to search the
file for the first occurrence of the string ab, followed by an arbitrary number of
a’s, followed by a c. We see from this example the need for pattern-matching
editors to work with regular expressions.