Regular Expressions and Converting to a NFA


Contents

Definition
Creating a Regular Expression
Converting to a NFA


Definition

A regular expression is another representation of a regular language, and is defined over an alphabet (defined as Σ). The simplest regular expressions are symbols from λ, ∅, and symbols from Σ. Regular expressions can be built from these simple regular expressions with parenthesis, in addition to union, Kleene star and concatenation operators. In JFLAP, the concatenation symbol is implicit whenever two items are next to each other, and it is not explicitly stated. Thus, if one wishes to concatenate the strings “grass” and “hopper”, simply input “grasshopper”. The following is how JFLAP implements other special symbols for regular expressions:

( , ) are used to help define the order of operations

* is the Kleene star

+ is the union operator

! is used to represent the empty string.

The following are a few examples of regular expressions and the languages generated using these operators:

  1. a+b+c = {a, b, c}

  2. abc = {abc}

  3. (!+a)bc = {bc, abc}

  1. ab* = {a, ab, abb, abbb, ...}

  2. (ab)* = (λ, ab, abab, ababab, ...)

  3. (a+b)* = (λ, a, b, aa, ab, ba, bb, aaa, ...)

  1. a+b* = (a, λ, b, bb, bbb, ...)

  2. a+!* = (a, λ)

  3. (a+!)* = (λ, a, aa, aaa, aaaa, ...)

Since all regular languages accept finite acceptors, a regular expression must also be able to accept a finite automaton. There is a feature in JFLAP that allows the conversion of a regular expression to an NFA, which will be explained shortly. For knowledge of many of the general tools, menus, and windows used to create an automaton, one should first read the tutorial on finite automata.

Creating a Regular Expression

To create a new regular expression, start JFLAP and click the Regular Expression option from the menu, as shown below:

One should eventually see a blank screen that looks like the screen below.

Now one can enter whatever expression that one wishes. Note that there should be no blanks in the regular expression, as any blank will be processed as a symbol of Σ. One such expression is in the screen below. One can either type it in directly, or load the file regExprToNfa.jff.

Converting to a NFA

After typing in an expression, there is nothing else that can be done in this editor window besides converting it to an NFA, so let's proceed to that. Click on the “Convert → Convert to NFA” menu option. If one uses the example provided earlier, this screen should come up (after resizing the window a little).

Now, click on the “(D)e-expressionify Transition” button (third from the left, to the immediate left of the “Do Step” button). Then, click on the transition from “q0” to “q1”. You should now see, perhaps with a little resizing, a screen like this...

You're probably wondering what exactly you just did. Basically, you broke the regular expression into three sub-expressions, which were united into one expression by the implicit concatenation operator. Whenever you click on an expression or sub-expression through this button, it will subdivide according to the last unique operation in the order of operations. Thus, since concatenations are the last operation to be performed on the given expression, the expression is divided according to that operator.

Let's continue. Click on the second button from the left, the “(T)ransition Creator” button. Now, let's make our first transition. Create a transition from “q0” to “q2”. You will not be prompted by a label, as in this mode only “λ” transitions are created. These types of transitions are all that are needed to create a nondeterministic automaton. When finished, you should see a “λ” transition between q0 and q2. Now, try to create a transition from q0 to q4. You will be notified that such a transition is “invalid”. This is because, due to the concatenation operation between sub-expressions “a*” and “b”, any “b” must first process the “a*” part of the NFA. While it is possible to go to “q4” without processing any input, that will have to wait until the “a*” expression is decomposed. Thus, in order to get to “q4”, we need to go through “q3”, the final state of the “a*” expression. If you create a transition from “q3” to “q4”, it will be accepted.

Since “(a+b)” is the last expression, we will get to the final state after processing it. Because of this, try to establish a transition from “q7” to “q1”. However, you should be warned that although the transition may be correct, you must create the transitions in the correct order. Thus, add the transition from “q5” to “q6” before adding the “q7” to “q1” transition. When done, your screen should resemble the one below.

Now, decompose the “a*” expression. Two new states should be created, “q8” and “q9”, and you should add transitions from “q2” to “q8”, “q9” to “q3”, “q2” to “q3”, and “q3” to “q2”. You may wonder why we cannot just add a transition from “q0” to “q3”. While such a transition is legal, JFLAP forces the transition to go through “q2”, because that is the starting state for the “a*” expression. Continue decomposing the expression using the tools provided. If you are stuck, feel free to use the “Do Step” button, which will perform the next step in the decomposition. If you wish to simply see the completed NFA, press the “Do All” button. You will probably have to move the states around in the screen and/or resize the screen so the decomposition looks good, whichever option you choose. In any event, when done, you should see a screen resembling the one below. Notice the indeterminate fork through “q6”, representing the union operator, where one can process either an “a” or a “b” transition. When finished, click the "Export" button, and you now have a nondeterministic finite automaton that you may use as you see fit.


This concludes our brief tutorial on regular expressions and using them to build NFAs. Thanks for reading!