Right-Linear Grammar

A restricted CFG where every Production is either the empty string or a string of terminals followed by a variable.

Definition

A CFG $G=(V,\Sigma ,P,S)$ is right linear if:

• Every production $P$ is of the form:
  • $A\to ϵ$
  • $A>xB$, $A,B\in V,x\in {\Sigma }^{\ast }$

Types

• Strict Right Linear Grammar