2.8 normal forms gnf & problems

what is normal forms?
Grebach Normal Form (GNF)

1. Greibach Normal Form (GNF) Sampath Kumar S, AP/CSE, SECE

2. Greibach Normal Form (GNF): A CFG is in Greibach Normal Form (GNF), if the right-hand side of each rule has one terminal followed by zero or more non-terminals: A → a B, where a ∈ T and B ∈ V*. For converting the given grammar to GNF, we use 2 lemmas. 8/30/2017 Sampath Kumar S, AP/CSE, SECE 2 Zero or more non-terminal symbols One terminal symbol

3. Example of a grammar in GNF 8/30/2017 Sampath Kumar S, AP/CSE, SECE 3 S → aB | bA A → a | aS | bAA B → b | bS | aBB Every right-hand side consists of exactly one terminal followed by zero or more non-terminals.

4. Example of a grammar not in GNF 8/30/2017 Sampath Kumar S, AP/CSE, SECE 4 S → aBc B → b Not in Greibach Normal Form Terminal at end is not allowed

5. Lemma 1: Substitution Rule Let G = {V, T, P, S} be a CFG. Let A → α B γ be a production in P and B is B → β 1 | β 2 | β 3 | β 4 The equivalent grammar can be obtained by substituting B in A . Then the resulting grammar is A → αβ 1 γ | αβ 2 γ | αβ 3 γ | αβ 4 γ 8/30/2017 Sampath Kumar S, AP/CSE, SECE 5

6. Lemma 2: Elimination of Left recursion Grammar of the form A → A α | β is called left recursive grammar. To eliminate left recursion, rewrite the grammar as A → β Z Z → α Z| ε If we eliminate ε production, then we get A → β Z | β Z → α Z| α We can generalize this grammar. If there is a CFG as A → A α 1 |A α 2 |A α 3 |….A α n | β 1 | β 2 | β 3 …… β n The equivalent grammar without left recursion is A → β 1 Z| β 2 Z| β 3 Z|…| β 1 | β 2 | β 3 …… Z → α 1 Z| α 2 Z| α 3 Z|……| α 1 | α 2 | α 3 8/30/2017 Sampath Kumar S, AP/CSE, SECE 6

7. Procedure for converting to GNF: Simplify the CFG ( i.e., eliminate null production, unit production and useless symbols ) and convert to Chomsky Normal Form (CNF). Convert the rules to ascending order. Rename the Non Terminals as A 1 , A 2 …. with S = A 1 . For each production of the form A i → A j α , apply the following: (a) if j> i – Leave the production as it is. (b) if j= i – Apply elimination of left recursion rule. (c) if j< i – Apply substitution rule. For each production of the form A i → A j α , where j> i , apply the substitution lemma if A j is in GNF, to bring A i to GNF. 8/30/2017 Sampath Kumar S, AP/CSE, SECE 7

8. Problems to discuss: 104. Convert the following CFG to GNF S → AA|a A→ SS|b Solution: Step 1: Simplify the CFG and convert to CNF – Given grammar is in CNF form. Step 2: Rename the variables as S=A 1 , A=A 2 A 1 → A 2 A 2 |a ….(1) A 2 → A 1 A 1 |b ….(2) 8/30/2017 Sampath Kumar S, AP/CSE, SECE 8

9. Problems to discuss: Step 3.1: In (1) j> i so leave the production as it is . Step 3.2: In (2) j< i so apply substitution rule . A 2 → A 2 A 2 A 1 |aA 1 |b ….(new 2) Step 3.3: In (new 2) j= i so apply elimination of left recursion rule. A 2 → aA 1 A 3 |b A 3 |aA 1 |b ….(new 2) A 3 → A 2 A 1 A 3 |A 2 A 1 ….(3) Step 3.4: In (3) j< i so apply substitution rule . A 3 → aA 1 A 3 A 1 A 3 |bA 3 A 1 A 3 |aA 1 A 1 A 3 |bA 1 A 3 | aA 1 A 3 A 1 |bA 3 A 1 |aA 1 A 1 |bA 1 ….(new 3) 8/30/2017 Sampath Kumar S, AP/CSE, SECE 9

10. Problems to discuss: Step 4: Now (1) is in A i → A j α where j< i so we apply substitution rule to convert it to GNF. A 1 → aA 1 A 2 |bA 2 |aA 1 A 3 A 2 |bA 3 A 2 |a …(new 1) Final production rule: A 1 → aA 1 A 2 |bA 2 |aA 1 A 3 A 2 |bA 3 A 2 |a A 2 → aA 1 A 3 |bA 3 |aA 1 |b A 3 → aA 1 A 3 A 1 A 3 |bA 3 A 1 A 3 |aA 1 A 1 A 3 |bA 1 A 3 | aA 1 A 3 A 1 |bA 3 A 1 |aA 1 A 1 |bA 1 Now the given CFG is converted to GNF. 8/30/2017 Sampath Kumar S, AP/CSE, SECE 10

11. Problems to discuss: 105. Convert the following CFG to GNF S → XA|BB B → b|SB X → b A → a 106. Convert the following CFG to GNF S → CA A→ a C → aB|b 107. Convert the following CFG to GNF S → AB A→ BS|b B → SA|a 8/30/2017 Sampath Kumar S, AP/CSE, SECE 11

12. Problems to discuss: 108. Convert the following CFG to GNF S → ABA A→ aA| ε B → bB | ε 109. Convert the following CFG to CNF S → AB C→ AB|b B → CA A → a 110 . Convert the following CFG to CNF S → BC|a B → AC|b C → a A → b 8/30/2017 Sampath Kumar S, AP/CSE, SECE 12

13. Problems to discuss: 108. Convert the following CFG to GNF S → ABA A→ aA| ε B → bB | ε 109. Convert the following CFG to CNF S → AB C→ AB|b B → CA A → a 110 . Convert the following CFG to CNF S → BC|a B → AC|b C → a A → b 8/30/2017 Sampath Kumar S, AP/CSE, SECE 13

14. 8/30/2017 Sampath Kumar S, AP/CSE, SECE 14

15. 8/30/2017 Sampath Kumar S, AP/CSE, SECE 15