Question 10.7.7: What regular expressions are equivalent to the patterns a?b ......

Algorithms and Programming: Problems and Solutions [1518855]

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

Step-by-Step

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

$((a\mid b\mid c \mid d\mid e)\ast a (a\mid b\mid c \mid d\mid e)b(a\mid b\mid c \mid d\mid e)\ast )$

$((a\mid b\mid c \mid d\mid e)\ast ab (a\mid b\mid c \mid d\mid e)∗cd(a\mid b\mid c \mid d\mid e)\ast )$

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