Regular expression

Question

What will be the regular expression for following fa using recurrence relation method.

Comments

Don’t know recurrence relation method but you can do this by removal of states method. On removing state 2 you will get $(r1 +r_2r_4^*r_3)^*$

---

Can we solve this using kleens theorem?

---

@nbhatt The easiest way to do these qs is, go to the final state and write all the loops in it as union (+) sign and then use * to generate infinite of them just like @Sumit Singh Dhami has done. 

 

Answer 1

We can also use arden's theorem to converting F.A to R.E

Comments

Btw why are you considering 4 different inputs for this machine?

---

Can we use kleen theorem?

---

@nbhatt No

Kleene's Theorem states that: every regular language may be recognized by some FA, and every FA, language may be represented using a regular expression.(simply by the use of union, intersection, concatenation, kleen closure ..etc)

infact in Ardens thorem we also used these union, closure but here is restrictions

Conditions-

 

To use Arden’s Theorem, following conditions must be satisfied-

• The transition diagram must not have any ∈ transitions.
• There must be only a single initial state.

so for constructing regular expression from finite automata we have to use either State elimination method or Arden’s theorem.