Regular language

Question

The following grammar

S$\rightarrow$SS|a|∈

can generate a*... which itself is a regular language but the grammar is neither right linear nor left linear... And we have studied that regular languages are always left or right linear.. Why is there such contradiction....?

Answer 1

The above mentioned grammar is context free grammar which is a superset of regular grammar i.e. All regular languages are context free but all context free languages are not regular.  Thus regular grammar can be expressed as cfg.

Hope this help.

Please drop a comment in case of a query.

Thanks

Comments

@shantanu-I also followed d same approach but the only difference is the regular grammar which u got from the automata u drew... How did u get it?? .. Bcz the way i followed, m gettng wrong regular grammar...!!  Plz tell

---

Once you have successfully built the FA for it then it is all mechanical. I'll tell you how.
 

1. Take the initial state of FA (A) as the Start state in regular grammar (S) and then write productions for each transition of initial state like S on 'a' goes to S (i.e. initial state A on 'a' goes to A)  itself and S on 'b' goes to next state A (State B of FA).
2. epsilon production is included as the initial state is final as well according to FA.
3. Repeat this for all the states in FA to complete the RG.

Please refer my answer in previous comment to co-relate to my statements here.

P.S.-I know I couldn't explain it very clearly. Please observe carefully to find the solution.

In my answer State A, B, C, D of FA correspond to variables S, A, B, C in grammar respectively

Thanks.

---

@shantanu - thanks a lot for ur help.. variable names were different.. Thats why i was getting confused..

Thank you so much..!!