8.1.  Pattern

A pattern is a set of objects with some recognizable property.

In a world of computers, a pattern is typically a string. Recognizing patterns (keywords, identifiers ...) is an essential part of compiling.

A typical problem is to recognize a special string. For example: Find the words

--

if

--

while

--

1234.986

--

FUNCTION

in a program.

The problem is: develop an algorithm which solves

find .... in a file.

Examples:

1.

Write a program which recognizes the word ``applepie'' in a file.

% egrep 'applepie' words
applepie
pineapplepie
% egrep '^applepie$' words
applepie

2.

Write a program which recognizes the word ``applepie'' or 'applecake' in a file.

% egrep '^applepie$|^applecake$' words
applepie
applecake
% egrep '^apple(pie|cake)$' words
applepie
applecake

3.

Write a program which recognizes words with a sequences of the letters: aeiou

% egrep '.*a.*e.*i.*o.*u.*' words
adventitious
facetious
sacrilegious

4.

Write a program which recognizes words with and x as its first an last letter.

% egrep '^x.*x$' words
xerox

5.

Write a program which recognizes palindromes with 4 characters.

% grep '^\(.\)\(.\)\2\1$' words
deed
noon
peep
poop
teet
toot

6.

Write a program which recognizes words with

-- the first and the fourth character are equal
-- the second and the fifth character are equal
-- the third and the sixth character are equal
-- the length of the word is 6 characters

% grep '^\(.\)\(.\)\(.\)\1\2\3$' words
murmur
tartar
testes

One solution is: Finite State Machines

Last modified 22/May/97