# Question 10.2.3: as we said, the difficulty appears because there are several......

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?

Step-by-Step
The 'Blue Check Mark' means that this solution was answered by an expert.

The longest prefix-suffix X determines all other prefix-suffixes.
Namely, prefix-suffixes of the processed part are prefixes of X that are also suffixes of X.
It is easy to write a transition table and a program for any fixed pattern. How-ever, we want to write a general program that will search for any given pattern in any given input string. The following approach may be used. Consider a program that has two stages. In the first stage, it examines the pattern and constructs a transition table for that pattern. In the second stage, it reads the input string and behaves according to the transition table. Such an approach is often used for more complicated patterns (see below), but for substring search there is more direct and
efficient method called Knuth-Morris-Pratt algorithm. (A similar approach was suggested by Yu. Matijasevich.) We start with some auxiliary lemmas.

Question: 10.2.1

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

A problem arises when the pattern contains repetit...
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). ...

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. ...

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

## Where have you seen a similar argument? ...

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). ...

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. ...

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}. ...

 ((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. ...

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. ...

 ((a\mid b\mid c)\ast bac (a \mid b \mid c)...