CODEWITHSUNDEEP
theoryautomatanfa
Tayyab Tauqir
Tayyab Tauqir

Reputation: 11

Convert the following regular expression into NFA

Convert the following regular expression into NFA: ab((ba)* + a*)

Upvotes: 0

Views: 722

Answers (1)

Patrick87
Patrick87

Reputation: 28292

There's a nifty algorithm for this that builds the NFA one step at a time based on the operations on the regular expression. The outermost operators here are concatenation: your regular expression is the concatenation of three terms:

(a)(b)((ba)* + a*)

This means there is an NFA that is the concatenation of three NFAs that accepts the language generated by this expression. NFAs for languages (a) and (b) are trivial:

L = {a}
q0--a-->q1

L = {b}
q2--b-->q3

Suppose we later get an NFA for the language (ba)* + a*, and its start symbol is q4. Then our NFA will look like this (unmarked transitions are epsilon/lambda/empty):

q0--a-->q1----->q2--b-->q3----->q4

We can repeat the algorithm for the subexpression (ba)* + a*. The outermost operation here is +; that means there's an NFA that looks like this, where q5 and q6 are starting states for the subexpressions on the left and right of the + operator:

q4----->q5
 |
 |
 V
 q6

An NFA for a* is easy enough:

q6-a-\
 ^   |
 \___/

I'll skip a couple of steps and just write down an NFA for (ba)*, but the algorithm (same as used to prove equivalence of NFAs and REs) has a simple rule for this too:

q5--b-->q7
 ^      |
 |      a
 \______/

Putting it al together gives this:

q0--a-->q1----->q2--b-->q3----->q4----->q5--b-->q7
                                 |       ^      |
                                 |       |      a
                                 V       \______/
                                 q6-a-\
                                  ^   |
                                  \___/

Upvotes: 1

Related Questions