GNF (Greibach normal form)


Productions are one of the following two forms / A → σx where σ ∈ T and x ∈ V* (**Front terminal only**)
**Claim**
> Given a CFG G, we can compute an equivalent CFG G' in GNF. This implies that, for every CFL L, there exists a CFG in GNF for L
<details><summary>

**Proof**</summary>

eliminate the followings needed
(a) Front recursions: A → AB
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F6c62f519-e923-4e85-86cb-e3e6db928134%2FUntitled.png?table=block&id=f74ee6dd-a65e-4161-9bed-7f11a3b256a9&cache=v2)
> remove recursion production and add (other productions in same variable)(new variable)
> new variable → (part after recursion)(new variable) | (part after recursion)
> 
(b) Front non-terminals: A → BCa
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F65a69ae7-2aa4-421a-869c-0ef45423b066%2FUntitled.png?table=block&id=e5f7a5e8-3316-45c2-ace9-425a55e642e0&cache=v2)
> by substitution rule
> 
(c) Non-front terminals: A → bBaC
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ffccbbac1-aa09-45bc-9e5a-9c3e1ea112ff%2FUntitled.png?table=block&id=1795d516-08a6-4de4-bd06-151ef8c76b5f&cache=v2)
> like CNF make terminal to non-terminal
</details>












