CODEWITHSUNDEEP
regexautomatadfaminimization
Fulla
Fulla

Reputation: 77

find a regular expression for the language accepted by the following automata

Find a regular expression for the language accepted by the following automata.

  1. Eliminate q1 

    q0: ab
q2: ba*
q0 to q2: b+aa
q2 to q0 : bb

  2. Eliminate q2 

    q0: ab+b+aa(ba)*

automaton diagram

(not sure if my way is right)

Upvotes: 1

Views: 1664

Answers (1)

Patrick87
Patrick87

Reputation: 28302

There are two rules:

  1. if X -> s and Y -> rXt then you can replace the latter with Y -> rst.
  2. if X -> sX | r then you can replace this with X -> s*r.

A regular grammar for this DFA is the following:

(q0) -> b(q2) | a(q1) | (q3)
(q1) -> b(q0) | a(q2)
(q2) -> b(q1)
(q3) -> lambda

We can begin eliminating states. (q3) is easy to get rid of:

(q0) -> b(q2) | a(q1) | lambda
(q1) -> b(q0) | a(q2)
(q2) -> b(q1)

We can get rid of (q2) pretty easily:

(q0) -> bb(q1) | a(q1) | lambda
(q1) -> b(q0) | ab(q1)

We need to get rid of the self-reference in the productions for (q1):

(q0) -> (bb+a)(q1) | lambda
(q1) -> (ab)*b(q0)

Now, we can get rid of (q1):

(q0) -> (bb+a)(ab)*b(q0) | lambda

Now, let's get rid of the self-reference:

 (q0) -> ((bb+a)(ab)*b)*

So, the regular expression ((bb+a)(ab)*b)* should work. This gets us back to state (q0) and (q3), the accepting state, is in the lambda-closure of (q0). Trying a few terms suggests we have found a good expression.

Upvotes: 1

Related Questions