what is the regular expression equivalent to the DFA ?

Question

I tried it through state elimination method but I am getting stucked at the outgoing edge from D to A .

Comments

use a bigger image next time, this is not proper

Answer 1

I. Using State Elimination 

FA given :

Remove State B 

Removing State C

Simplify it 

Regular expression is (01+10)(11+1(01+10))*

II. Using Arden's Theorem 

A=∊ + D0   ------- I

B= A0+D1  -------II

C=A1     -----------III

D=B1+C0 --------- IV

Putting II and III in IV 

D= (A0+D1)1+A10

=A(01+10) +D11

Apply Arden's Theorem

D= A(01+10)(11)*  - - - - - V

Put V in I

A=∊+A(01+10)(11)*0

​Apply Arden's Theorem 

A= ((01+10)(11)*0)*  - - - - VI

​Put VI in V

​Regular expression, D = ((01+10)(11)*0)*(01+10)(11)*

= (01+10)(11)*(0(01+10)(11)*)* [ bcoz (pq)*p = p(qp)*] 

= (01+10)(11+0(01+10))* [ bcoz p*(qp*)* = (p+q)*]  

Comments

Sir , I couldn't get your simplification part , when u removed C then why didn't u made a self-loop at D regarding 010,can u plz explain that part once .

---

1.When by removing C, the path from D to D ( that you are saying regardind 010) is still there as A state is not remove (D to A then A to D, 0 then 10) 2. There is no path from D to D via C directly, it is as D-A-C-D, and we are removing C, so we need to worry about A-C-D.

---

Sir , can u plz check this one , I am getting regular expression as (00)*00(1+10)*

∈+0(01*1+00)*01*

where is my mistake ?

---

I think you are removing that state in center .

if yes instead of 00 on that edge from start ,say A to second final say B it should be 01  and one edge should be B to A for 00 , self loop at A of 00, self loop of 01 (not 10 you did ) at B , then try

---

sir ,plz check my pic again , I had actually made one transition wrong ,now where is my mistake ?

---

10 from second final to first (B to A) is missing

---

Sir Fine so I get now

(00+0010)*00(1+10+1000)*

sir I am getting stucked here becoz of two final states plz help me out with this .

---

radha on 1st final state ur missing sometng chech it their will be (00+001(1+10)*10)* on 1st final state

---

At first final (00+00(1+10)*10)*

At second final (00+00(1+10)*10)*00(1+10)*

Add them. 

(note:use arden's theorem if not comfortable with state elimination) 

---

@Praveen Saini, Why epsilon is added in the expression for A in Arden's method?

Shouldn't we add epsilon to D only as it is the final state?

---

In Arden's theorem, we need to add epsilon with start state, while writing the corresponding grammer, start state is already identifies by S, but to end the Non-Terminal in string, we have to add epsilon with final state