in Theory of Computation
98 views
0 votes
0 votes

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

in Theory of Computation
by
98 views

3 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)^*$
1
1
Can we solve this using kleens theorem?
0
0

@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. 

 

0
0

1 Answer

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

3 Comments

Btw why are you considering 4 different inputs for this machine?
0
0
Can we use kleen theorem?
0
0

@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.

0
0