Conversion of regular grammar to FA

Question

A->aB/bA/b

B->aC/bB

C->aA/bC/a

 

If the above regular grammar is converted into DFA then how many final states will be there?

According to me there should be 2 final states: A and C

But the resource from where I am reading it says only one final state will be there which will be A.

Kindly explain.

Comments

https://gateoverflow.in/173086/need-help-to-draw-a-dfa-from-a-right-linear-grammar

You can check the solution here .

Before checking the solution , think about the procedure how a Right linear grammar is converted to a Finite Automata?

And how would you justify that A and C shall both be the final states?

X->aB . Check this particular RLG production , if we would go to create a FA for this production , from state X on seeing 'a' we go to B.

But if X->a , then where do we go? Itself? No right? Otherwise we'd be having a self loop and the entire language might change , so a final state needs to be reachable from X on seeing 'a'.

Do you understand it now? 

---

Still I coudn't. But Thank you for the effort.

I need to give a specific time slot for it explore the things again

---

@Akash Kumar Roy

Make a DFA for the above grammar in which both 'A' and 'C' are final states. Now give the string "aa", according to you, it should be accepted if 'C' is a final state but it will not be accepted. For "aa" , first production A-->aB will be chosen then B-->aC will be chosen. Now here it should be stopped because we got "aa" but it will not be stopped.

Now, consider string "aaba" and check on which state, it will be accepted and goes through which productions.

Here, in A->aB/bA/b, observe if we reach state 'A', and string contains 'b' then we go to the same state 'A' by replacing 'A' by 'b' and here we got ended.

Now, in C->aA/bC/a, observe when you reach state 'C' and we see 'a' then we go to state 'A' and when we see 'b' then we go to same state. Now, suppose we are in state 'C' and we see 'a' then production C-->aA implies that we have to go to state 'A'. Now, suppose we are in state 'C' and we see 'ba' then production C-->bC and then b-->ba by replacing C by a, implies that we have to go to state 'A'.  C-->bC/a only tells that if you see b and after that a and then string got ended then we have to replace 'C' by 'a'

Answer 1

With the help of grammar we can make a NFA . then we create a minimal dfa then we get number of final state.

Comments

@abhishekmehta4u Can you please explain the concept/theory because of which on a or b goes to x from A and respectively?

and what do we have to do on c- (epsilon)

Instead of making x as final can we make A and C both as final?

---

if you make A as final state then machine accept null. But grammar dose not give null.

and if we make C as a final state then machine accept aa. But grammar dose not gives string aa. So we cant make A and S as a final state.

---

That's so meticulous explanation. Thank You.

so, If situation like this occur then always we have to make a new state which will be final, right?

Can I derive this from that explanation?

Answer 2

Make a DFA

then you got the answer

only A will be final state

Comments

bro, that is what I am asking why only A?

Grammar is allowing to stop yielding at C also. Then only A why?

---

we can stop yielding at A and C

there are hence two candidates for being the final states A & C

Now, see the productions of A & C:

---

A->aB/bA/b        put ε  in place of A in bA→ bε → b

B->aC/bB

C->aA/bC/a       put ε  in place of A in aA→ aε → a

---

note: you have reached terminal symbols in both the productions using ε in place of A only and not C!!

that’s why only A is the final state and not C.

 

---

pls correct me if I am wrong.