Holooly Plus Logo
Holooly Plus Logo

Question 10.7.10: A nondeterministic finite automaton N is given. Construct an......

A nondeterministic finite automaton N is given. Construct an equivalent 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).

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

The states of the deterministic automaton are sets of vertices of the nondeterministic automaton. After a prefix X of the input string is read, the state s (X) of the deterministic automaton is the set of all vertices that are reachable from I along paths carrying the string X on it. In other words, consider all paths starting from I. Each path determines a string that can be read along it. If the string is X, include the end of the path into s (X).

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

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

Verified Answer:

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

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