Nfas To Regular Expression

The basic approach to convert NFA, to Regular Expressions is as follows:

1. If an NFA has more than one final state, convert it to an NFA with only one final state. Make the original final states nonfinal, and add a l-transition from each to the new (single) final state.
2. Consider the NFA to be a generalized transition graph, which is just like an NFA except that the edges may be labeled with arbitrary regular expressions. Since the labels on the edges of an NFA may be either l or members of each of these can be considered to be a regular expression.
3. Removes states one by one from the NFA, relabeling edge as you go, until only the initial and the final state remain.
4. Read the final regular expression from the two state automaton that results.
5. The regular expression derived in the final step accepts the same language as the original NFA.

Example 1: Represent the following sets by regular expression

(a) {Ù, ab}

(b) {1,11,111,KK}

(c) {ab, a, b, bb}

Solution

• The set {Ù, ab} is represented by the regular expression Ù ab
• The set {1,11,111,KK} is got by concatenating 1 and any element of {1}*. Therefore 1(1)* represent the given set.
• The set {ab, a, b, bb} represents the regular expression

ab a b bb.

\Example 2: Obtain the regular expressions for the following sets:

• The set of all strings over {a, b} beginning and ending with ‘a’.
• {b², b⁵, b⁸, } KK
• {a 2n 1 | n > 0}

Solution

(a)    The regular expression for ‘the set of all strings over {a, b} beginning and ending with ‘a’ is given by:

a (a b)*a

(b)    The regular expression for {b2 , b5 , b8 , } KK is given by:

bb (bbb)*

(c)    The regular expression for {a 2n 1 | n > 0} is given by:

a (aa)*

Example 3: Give Regular expressions for the following on

S = {a, b, c}

1. all strings containing exactly one a
2. all strings containing no more than three a’s
3. all strings which contain at least one occurrence of each symbol in S.
4. all strings which contain no runs of a’s of length greater than two.
5. all strings in which all runs of a’s have lengths that are multiples of three.