Article Preview
Buy Now
| Print: | |
| PDF: |
Feature
Multiple String Searches
An example of a finite state machine
Issue: 2.1 (August/September 2003)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 9,412
Starting Page Number: 30
RBD Number: 2114
Resource File(s):
2114.sit Updated: Monday, March 15, 2004 at 1:08 AM
Related Web Link(s):
http://home.earthlink.net/~thomasareed/realbasic/
http://www.monkeybreadsoftware.de/realbasic/plugins.html
Known Limitations: None
Excerpt of article text...
A finite state machine is commonly used to analyze a "language": any system of codes used to represent some meaning. One obvious example of a language would be English, in which 26 different symbols (letters) are used to build words. Another example would be the tokenized representation of C source code, created as an intermediate step in compilation by a C compiler. An array of objects in a REALbasic program could also be considered a language.
The finite state machine analyzes a language by using a set of states and transitions. The machine begins in an initial state, and each symbol in the language being analyzed transitions the machine to a new state. Certain states are "accept" states, meaning the state represents some target condition. For example, when analyzing an English language sentence, a non-alphabetic character might put a finite state machine into an accept state which signifies a word end, and the machine would add that word to a list.
In this article, I will discuss an example of a finite state machine that searches a block of text in a single pass for any number of keywords. For example, suppose you want to search a lengthy table of entree prices at restaurants all over town for "cod", "tuna", and "trout". Figure 1 illustrates a state machine containing these keywords. The algorithm begins in the start state-- state zero. Each character in the search text will trigger a transition into another state. In the event it reaches one of the accept states (3, 7, and 11 in the figure), a match has been found.
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
