Regular Expression to NFA

Topics

• Purpose
• The Constructive Proof
• Example with Questions

Purpose

• In this unit, our goal is to show that any regular expression r can be transformed into an "equivalent" NFA N where L_r = L(N).

• High Level Comments/Question

  • Question 1: Given that we can transform any NFA N into an equivalent FA M where L(N) = L(M), what does this result imply?

  • The key to understanding this transformation is understanding the general power of recursive algorithms and inductive proofs.

The Constructive Proof

• Preliminary Question

  • What will we perform induction on in this proof?

    • Any regular expression has finite length.

    • In particular, any regular expression applies the three operators *, +, and concatenation a finite number of times.

    • We will prove this result by induction on the number of operators in r

• We will prove that any regular expression r can be transformed into an NFA N such that L_r = L(N) by induction on the number of operators in r.

• The Basis Step

  • The number of operators is 0

  • Given a finite alphabet , there are only a finite number of regular expressions with 0 operators (how many?).

  • Below, we list each such regular expression which you can click on to see the appropriate NFA.

    • The empty set regular expression corresponding to the language {}.

    • , the regular expression which corresponds to the language {}.

    • Each of the || characters a in , the regular expression which corresponds to the language {a}.

• The Inductive Step

  • The Inductive Hypothesis (strong induction)

    • We assume that any regular expression rwith between 0 and n operators can be transformed into an equivalent NFA N where L_r = L(N) for n 0.

  • The Statement to Be Proven in the Inductive Step

    • Any regular expression rwith n+1 operators can be transformed into an equivalent NFA N where L_r = L(N) for n 0.

  • The proof of the Inductive Step

    • Let r be any regular expression with n+1 operators where n 0.

    • Examining the precedence of the n+1 operators, one of the operators must be the "last" to be applied.

    • This leads to three cases depending on which operator this last operator is:

      • concatenation:

        • In this case, r = st where both s and t are regular expressions with at most n operators. (Why?)

        • Since both s and t are regular expressions with at most n operators, we can apply the induction hypothesis to conclude that there exists two NFAs N_s and N_t such that L_s = L(N_s) and L_t = L(N_t).

        • We now show how NFAs N_s and N_t can be combined to form an NFA N_r such that L_r = L(N_r).

          • The NFA N_r will be the NFAs N_s and N_t connected as follows:

          • The initial state of NFA N_r will be the initial state of NFA N_s.

          • The set of final states of NFA N_r will be the set of final states of NFA N_t.

          • The set of transitions of NFA N_r will be the set of transitions of NFAs N_s and N_t plus transitions between all the final states of NFA N_s to the initial state of N_t.

          • Click here for a picture (not yet active).

        • Argument that L_r = L(N_r) (not yet filled in).

      • + (Choice):

        • In this case, r = s+t where both s and t are regular expressions with at most n operators.

        • Since both s and t are regular expressions with at most n operators, we can apply the induction hypothesis to conclude that there exists two NFAs N_s and N_t such that L_s = L(N_s) and L_t = L(N_t).

        • We now show how NFAs N_s and N_t can be combined to form an NFA N_r such that L_r = L(N_r).

          • The NFA N_r will be the NFAs N_s and N_t connected as follows:

          • The initial state of NFA N_r will be a new state q.

          • The set of final states of NFA N_r will be the set of final states of NFA N_s and the set of final states of NFA N_t.

          • The set of transitions of NFA N_r will be the set of transitions of NFAs N_s and N_t plus transitions between q and the initial state of both NFA N_s and NFA N_t.

          • Click here for a picture (not yet active).

        • Argument that L_r = L(N_r) (not yet filled in).

      • * (Closure):

        • In this case, r = s* where s is a regular expression with n operators.

        • Since s is a regular expression with n operators, we can apply the induction hypothesis to conclude that there exists an NFA N_s such that L_s = L(N_s).

        • We now show how NFA N_s can be altered to form an NFA N_r such that L_r = L(N_r).

          • The NFA N_r will be NFA N_s modified as follows:

          • The initial state of NFA N_r will be a new state q.

          • The set of final states of NFA N_r will be the set of final states of NFA N_s.

          • The set of transitions of NFA N_r will be the set of transitions of NFA N_s plus transitions between all the final states of NFA NFA N_s and the new state q as well as an transition between the new state q and the initial state of the NFA N_s.

          • Click here for a picture (not yet active).

        • Argument that L_r = L(N_r) (not yet filled in).

Example with Questions: r = (ab+b)^* + (a + ba)a

1. How many operators are in the regular expression r?

2. Which of the operators of r is the "last" operator of r?

3. Based on the answer to the above question, what would s and t be?

4. Answer the same three questions for the regular expression s that is at least part of the answer to question 3 above.

5. Applying the above construction without simplification, what does the transition diagram for the NFA corresponding to ab look like?

6. Applying the above construction without simplification, what does the transition diagram for the NFA corresponding to ab+b look like?

7. Applying the above construction without simplification, what does the transition diagram for the NFA corresponding to (ab+b)^* look like?

8. Applying the above construction without simplification, what does the complete transition diagram for the NFA N look like?

9. How does this proof fit into the generic element proof technique framework, and what basic property of regular expressions did we use?

10. Give a recursive algorithm description (in pseudocode or some programming language) of the transformation of a regular expression to an equivalent NFA.

• Complete list of answers to the above questions.

Regular Languages Chapter (up one level)
Table of Contents (up two levels)