Holooly Plus Logo
Holooly Plus Logo

Question 10.2.1: Can the previous algorithm be used for any other string inst......

Can the previous algorithm be used for any other string instead of abcd?

Step-by-Step
The 'Blue Check Mark' means that this solution was answered by an expert.
Learn more on how do we answer questions.
Report Answer

A problem arises when the pattern contains repetitions. For example, suppose we are looking for substring ababc. Assume that a appears, then b, a, and b again. At this point, we are eagerly waiting for e. If the letter d appears instead, we should start from scratch. However, if the letter a appears, we still have a chance that b and c follow and the pattern is found.

Here is an illustration:

x y z  a b a b a b c …  ← input string

a  b a b c            ← pattern was expected here

a b a b c              ← but it is here

In other words, at the point

\begin{array}{rllllll|llll} \mathrm{x} & \mathrm{y} & \mathrm{z} & \mathrm{a} & \mathrm{b} & \mathrm{a} & \mathrm{b} & \quad \quad \quad \ \ \ \quad\leftarrow \text { input string } \\ & & & \mathrm{a} & \mathrm{b} & \mathrm{a} &\mathrm{b} &\mathrm{c} \quad \quad \quad \quad \leftarrow \text { pattern was expected here } \\ & & & && \mathrm{a} & \mathrm{b} & \mathrm{a} \quad \mathrm{b} \quad \mathrm{c} \quad\leftarrow \text { but it is here } \end{array}

there are two possible pattern positions to be tested.

Related Answered Questions

Question: 10.2.3

as we said, the difficulty appears because there are several possible positions of the pattern; each position corresponds to some prefix of the pattern that is also a suffix of the input string. The finite automaton remembers only the longest one. What about others? ...

Verified Answer:

The longest prefix-suffix X determines all other p...
Question: 10.7.13

Prove that the class of sets corresponding to regular expressions remains the same if we agree to use not only set union but also complementation (and therefore set intersection, since it can be expressed using set union and complement). ...

Verified Answer:

For the deterministic finite automata the transiti...
Question: 10.7.11

A nondeterministic finite automaton is given. Construct a regular expression that defines the same set. ...

Verified Answer:

Assume that the nondeterministic automaton has ver...
Question: 10.7.12

Where have you seen a similar argument? ...

Verified Answer:

In the Floyd algorithm for the shortest path (see ...
Question: 10.7.10

A nondeterministic finite automaton N is given. Construct an equiv- alent deterministic finite automaton (or a program with a finite number of states) that checks if an input string x is accepted by N (that is, if x can be read on a path from I to F). ...

Verified Answer:

The states of the deterministic automaton are sets...
Question: 10.7.9

A regular expression is given. Construct a nondeterministic finite automaton that corresponds to the same set. ...

Verified Answer:

This automaton is constructed inductively, followi...
Question: 10.7.7

What regular expressions are equivalent to the patterns a?b and ab∗cd used as examples earlier? (Please note that the symbol ∗ in the pattern ab∗cd has a completely different meaning compared to its use in regular expressions.) We assume that the alphabet is {a, b, c, d, e}. ...

Verified Answer:

((a\mid b\mid c \mid d\mid e)\ast a (a\mid...
Question: 10.7.8

Prove that for any regular expression there exists a finite automaton that recognizes the corresponding set of strings. ...

Verified Answer:

To prove this, we need the notion of a nondetermin...
Question: 10.7.6

Write a regular expression that defines a set of strings composed of a, b, c having bac as a substring. ...

Verified Answer:

((a\mid b\mid c)\ast bac (a \mid b \mid c)...
Question: 10.7.5

Find a regular expression corresponding to the set of all strings com- posed of a and b that contain an even number of as. ...

Verified Answer:

The expression b∗ defines the set of all strings w...