Regular Grammar

Question

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 ?

Comments

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

---

@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 ?

---

Yes, you are right.

That's a linear one.

Answer 1

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.

Comments

@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?

---

I think it is not regular grammar.  It is combination of both.

---

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.

---

Yes mamta is right