2 votes 2 votes Is a regular grammar either "completely LEFT LINEAR " OR "completely RIGHT LINEAR" or can it be a combination of both left linear and right linear ? Theory of Computation theory-of-computation + – Sourav_35 asked Apr 6, 2018 edited Apr 7, 2018 by Sourav_35 Sourav_35 1.8k views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments Mamta Satywali commented Apr 8, 2018 reply Follow Share @Ankit I understand your concern about exclusive OR and inclusive OR thing, I too faced that, so the point to note here is- In theoretical science and formal language theory, a regular grammar is a formal language that is right-regular or left-regular. Here, had it been "either/or" case then the Exclusive OR is considered, but we see just an "or" hence it means Inclusive OR. I had my share of Google search for "either/or Vs or" to satisfy myself with this thought. 0 votes 0 votes ankitgupta.1729 commented Apr 8, 2018 reply Follow Share @mamta ,so according to u , mixing of left linear and right linear grammar is allowed in regular grammar . ie. A ----> aB | Cb B -----> b C -------> c according to u , this grammar should be regular grammar ..right ? but S--> aA | aB | ε, A--> Ab | ε is not regular because its equivalent grammar S ---> aAb | aB | ε | a ;A--->Ab | ε contains S ---> aAb production which is the combination of left linear and right linear in right hand side..Am I right ? 0 votes 0 votes Mamta Satywali commented Apr 8, 2018 reply Follow Share Yes, you are right. That's a linear one. 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes regular grammar either "completely LEFT LINEAR " OR "completely RIGHT LINEAR" if we combine both then we may get nonregular language . so combination of left linear and right linear is not allowed for reguler grammar. abhishekmehta4u answered Apr 6, 2018 abhishekmehta4u comment Share Follow See all 4 Comments See all 4 4 Comments reply Mamta Satywali commented Apr 7, 2018 reply Follow Share @abhishekmehta4u But the ques says- "CAN it be a combination of both left linear or right linear"? So, we need to find a possible("CAN") grammar which is a combination of both and still become a regular grammar. like foll- S->Sb | aS | a | b Isn't this regular? 0 votes 0 votes abhishekmehta4u commented Apr 7, 2018 reply Follow Share I think it is not regular grammar. It is combination of both. 0 votes 0 votes Soumya29 commented Apr 7, 2018 reply Follow Share Mamta Satywali S->Sb | aS | a | b This is a linear grammar. Left linear grammar and right linear grammar are subsets of linear grammar. Regular grammars are the subset of linear grammar and CFGs are the superset of linear grammar. Regulars grammars are Either Left linear or Right linear but not both. 2 votes 2 votes abhishekmehta4u commented Apr 7, 2018 reply Follow Share Yes mamta is right 0 votes 0 votes Please log in or register to add a comment.