**Introduction**

GNF (Greibach Normal Form) is a specialized form of Context-Free Grammar (CFG) where each production rule begins with a terminal symbol, followed by optional variables.

A **CFG (Context-Free Grammar)** is a **Greibach Normal Form**(GNF) if all of its production rules satisfy one of the following conditions:

- A non-terminal generating terminal. For example, B -> b.
- Start symbol generating Îµ. For example, S â†’ Îµ.
- A non-terminal generates a terminal followed by any number of non-terminals. For example, A -> aBCâ€¦N.

Also read about - Chomsky Hierarchy

**For example:**

```
G1 = {S â†’ aAB | bBA, A â†’ aA | a, B â†’ bB | b}
G2 = {S â†’ aAB | aBA, A â†’ aA | Îµ, B â†’ bB | Îµ}
```

- The production rules of Grammar G1 satisfy the above rules specified for GNF. Therefore, G1 is in GNF.
- However, the production rule of G2 does not satisfy the rules specified for GNF as A â†’ Îµ and B â†’ Îµ contains Îµ, but only the start symbol can generate Îµ. So the grammar G2 is not in GNF.

Also read, __Arden's theorem__

**Notes:**

- There can be more than one GNF for a given grammar.
- GNF produces the same language as CFG produces.

Also see, __Turing Machine in TOC____.__

**Steps for Converting CFG into GNF**

**Step 1 **- Convert the Grammar into __Chomsky Normal Form__(CNF): If the given Grammar is not in CNF, convert it.

**Step 2 **- If the grammar contains left recursion, remove it.

**Step 3 **- Convert the production rule into GNF form in the grammar.

Read About - __Simplification of CFG__

### Letâ€™s understand with an example,

**Question: **Consider the following Grammar G. Convert it into GNF.

```
S â†’ AA | BC
A â†’ a|SA
B â†’ a
C â†’ c
```

**Solution: **

We can skip steps 1 and 2 and move directly to step 3 because the given grammar G is already in CNF, and there is no left recursion.

- The production rule A â†’ SA is not in GNF, so we substitute S -> AA | BC in the production rule A â†’ SA as

```
S â†’ AA | BC
A â†’ a | AAA | BCA
B â†’ a
C â†’ c
```

2. The production rule S â†’ BC and A â†’ BCA is not in GNF, so we substitute B â†’ a in the production rule S â†’ BC and A â†’ BCA as

```
S â†’ AA | aC
A â†’ a | AAA | aCA
B â†’ a
C â†’ c
```

3. Next, we will remove the left recursion (A â†’ AAA), we get

```
S â†’ AA | aC
A â†’ aX | aCAX
X â†’ AAX | Îµ
B â†’ a
C â†’ c
```

4. Now remove the null production X â†’ Îµ, we get

```
S â†’ AA | aC
A â†’ aX | aCAX | a | aCA
X â†’ AAX | AA
B â†’ a
C â†’ c
```

5. Now, S â†’ AA and X â†’ AA are not in GNF, so we substitute A â†’ aX | aCAX | a | aCA in production rule S â†’ AA and X â†’ AA as

```
S â†’ aXA | aCAXA | aA | aCAA | aC
A â†’ aX | aCAX | a | aCA
X â†’ AAX
X â†’ aXA | aCAXA | aA | aCAA
B â†’ a
C â†’ c
```

6. Lastly, X â†’ AAX is not in GNF, so we substitute A â†’ aX | aCAX | a | aCA in production rule X â†’ AAX as

```
S â†’ aXA | aCAXA | aA | aCAA | aC
A â†’ aX | aCAX | a | aCA
X â†’ aXAX | aCAXAX | aAX | aCAAX
X â†’ aXA | aCAXA | aA | aCAA
B â†’ a
C â†’ c
```

Hence, it is the GNF of Grammar G, as all the production rules follow one of the rules mentioned above.

Also read - __Theory of Computation__