The Gateway to Computer Science Excellence
+2 votes

How to convert given finite state automaton into regular expression.

in Theory of Computation by (229 points)
edited by | 400 views
@joshi_nistish, Earlier I made a mistake while making FSA. I made correction and updated the question. Can you please write regular expression again for above diagram? and Can you also check whether I made correct FSA for this grammar or not:
                S        →        y | z | y S | z S | x B
                B       →        y | y S
Thank you.


(xy+y+z)* (xy+y+z) / (xy+y+z)+  

@hs_yadav Can you please explain how did you get the answer?


by using state elimination method:-

1.eliminate all intermediate state but no transition should be lost...

and in your grammar for RE is:-

 S        →        y | z | y S | z S | x B 
 B       →        y | y S


here you have taken as...

1.any no. y or any no. of z (at least one y or z) but every x should be followed by y. means (z++y++(xy)+)+

you can also do like this...

@hs_yadav I tried to solve this with state elimination method. But I confused how to remove q1 state as Y is going back to q0 state.
when you will remove q1, then loop 'xy' will be added on q0 as well as transition 'xy' will be added from q0->q2

let we have removed q1 then what is the all transitions which may be lost....

1. q0->q1->q0     xy    (it could be represented as self loop on q0)

2.q0->q1->q2      xy    (it could be obtained by taking transition from qo->q2 as xy)

I didn't knew how to handle this case. Thank you very much :)

2 Answers

0 votes
"  (X+Y)*X (Y(X+Y)X)* (X+Y) (Y+Z)   "  i got this RE
by Junior (795 points)
0 votes
by Junior (691 points)
Plz explain it with state elimination method
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,647 users