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

kaushik is correct ....///@ chetna there is no contradiction....regular grammar is either left linear or linear is correct..but it doesn't mean that..there is only one grammar..for a language...there can be many grammars that can generate it...and all grammars need not 2 be regular...but there exist atleast one regular grammar 4 every regular language..

---

So the conclusion is :

 If a grammar is left or right linear, it is regular grammar.Otherwise it is not regular.

 

Am I right?

---

@tauhin n shantanu.. Thanks for ur reply but.. I know that this is not regular grammar but i am asking dt finite automata can be there only for regular grammar right..?

And this is not a regular grammar.. Its a cfg.. But we can draw a finite automata for this grammar.. Why.?

---

@tauhin n shantanu.. Thanks for ur reply but.. I know that this is not regular grammar but i am asking dt finite automata can be there only for regular grammar right..?

And this is not a regular grammar.. Its a cfg.. But we can draw a finite automata for this grammar.. Why.?

@shiva loyal

Yes u r right.. In fact every right linear grammar can be converted into left linear n vice-versa...

---

Yes, for a grammar to be regular it has to be either left or right linear and not a combination of both.

---

@chetnawadhwa - Because CFG is a super set of regular grammar.

You are right that finite automata can be given only for regular grammar and for the mentioned language the regular grammar is S-->aS/€.

And you can give n number of cfg for the same language.

Infact all the regular languages can be generated using regular grammar and using cfg as well.

Hope this helps.

Thanks

---

@chetna plz draw the FA  for this grammar...S------>SS|a|∈

how u will draw...let me know???

---

@shantanu- u mean that whichever language can be defined using a finite automata..there definitely exists a regular grammar for it and n no of nonregular grammars can also exist.. But at least one reg grammar will b dre... Is dt so..?

@tauhin-this grammar represents the language a*.. And we can draw a finite automata for it.. With  only one state as initial  n final with a loop on itself..!!

---

exactly

---

@shantanu can u pl answer this ques

S-->Sab|AB

A-->aA|epsilon

B-->bB|epsilon

Does this grammar generate regular language..?

Acc to me it is a regular lang.. Am i right?

---

@chetna u said "-this grammar represents the language a*.. And we can draw a finite automata for it.. With  only one state as initial  n final with a loop on itself..!!"

u cannot say like this.....use step by step...procedure..to convert regular grammar into dfa...and check the

S-->SS|a|∈

can u draw dfa 4 this  or not...

"A language is regular iff there exist a regular grammar"...it doesn't mean all the grammar's  that generates a language should be regular....

"A NON-REGULAR GRAMMAR CAN ALSO GENERATE REGULAR LANGUAGE"

....i hope u understand

---

@tauhin- thats what my question was.. Can non regular grammar also generate regular language..? When i was going step by step i was getting confused by the results as i was not craming rather trying to understand the concept behind that...

Thank u so much for ur help..

---

This is my attempt to answer your question:

---

ok chetna sorry  u were trying 2 understand

---

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