Strict Right Linear Grammar

A Right-Linear Grammar where all Production Rules map to Empty String or Terminal followed by a Non-terminal

Definition

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

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

Theorems

• Languages Generated by Strict Right-Linear Grammars are Regular
• Every Regular Language can be Generated by a Strict Right-Linear Grammar

FSA

A strict right linear grammar represents the structure of a FSA. Given a strict right linear grammar $G=(V,\Sigma ,P,S)$, NFSA $M=(Q,\Sigma ,\delta ,s,F)$

• $Q=V$
• For every $A,B\in V$, $a\in \Sigma \cup \{ϵ\},\delta (A,a)=\{B:A\to aB\text{ is a production in }P\}$
• $s=S$
• $F=\{A:A\to ϵ\text{ is a production in }P\}$