انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

GNF

Greibach Normal Form  

Definition Greibach Normal Form (GNF)

A CFG is in Greibach Normal Form if all productions are of the form

A ? a X 

with  aIT  and  XIV*.

This means, all productions start with a terminal on the PRODUCTION and have only variables following.

Theorem  

For every CFG  G with ??L(G) exists an equivalent grammar G   in Greibach NF. 

Proof and algorithm

Firstly, we convert the given grammar into Chomsky NF:

 Start with a grammar G = ( V, T, P, S)

 Eliminate useless variables that cannot become terminals.

 Eliminate useless variables that cannot be reached.

 Eliminate ?-productions.

 Eliminate unit productions.

 Convert grammar to Chomsky Normal Form.

Then, we convert this grammar into an equivalent grammar in Greibach NF.

Convert a CNF grammar into Greibach Normal Form:

0. Re-label all variables such that the names are A₁, A₂, ... , A_m.

1. We want to order the productions, which are not terminal but contain     variables. We use for this purpose the indexing of the variables, so that

  A_i ? A_j ?   with i<j   for all  i = 1,...,m  and j = 2, ..., m

We perform the ordering process by substitution of the first variable on the PRODUCTION, if the production violates the condition above (see 2 and 3). 

2. We start the ordering with  A₁. 

A₁-productions can have only a higher numbered variable as first variable on the PRODUCTION, or a single terminal.

3. We assume now that all rules are okay up to A_k-1. The next rule we encounter, with A_k on the production, is the first one, which is not okay:

 A_k ? A_l ?  with k>l

We resolve this problem by substituting A_l. Since l<k, the A_l-rules have already gone through the sorting process and are in the proper format:

A_l ? A_j ?  with l<j

Now, we substitute the PRODUCTIONs of A_l in the A_k-rule, and come up with:

A_k ? A_l ? or A_k ? a   for some a

If l is still less than k, we substitute again. And again and again, until we get at least A_k on the PRODUCTION - all rules up to A_k-1 are already sorted and in proper form, and the first variable on the PRODUCTION of the A_k-1-production must be therefore at least A_k.

EXAMPLE 1: TRANSFORM A CFG INTO GREIBACH NORMAL FORM  

Bring the grammar G with V={S, A, B}, T={a, b} and productions P 

S ? A

A ? a B a | a 

B ? b A b | b

into GNF.

Solution:

1. Simplify G:

No useless variables or productions, no ?-productions.

Remove unit-production S ? A:

Replace A with PRODUCTION of A (after calculating transitive closure of unit-productions - but there is only one unit-dependency here A ? B): 

S ? a B a | a new rule

2. Transform G into an equivalent grammar G in Chomsky NF:

Substitute terminals on PRODUCTION with variables:

S ? C₁ B C₁ | a  C₁ ? a

A ? C₁ B C₁ | a   C₂ ? b

B ? C₂ A C₂ | b

Break down the rules:

S ? C₁ D₁ | a D₁ ? B C₁  C₁ ? a

A ? C₁ D₁ | a

B ? C₂ D₂ | b D₂ ? A C₂  C₂ ? b

3. Transform G into equivalent grammar G in Greibach NF: 

a. Rename the variables to V₁, V₂, ... in the productions P : 

S=V₁; A=V₂; B=V₃; C₁=V₄; C₂=V₅; D₁=V₆; D₂=V₇

V₁ ? V₄ V₆ | a V₆ ? V₃ V₄  V₄ ? a

V₂ ? V₄ V₆ | a

V₃ ? V₅ V₇ | b V₇ ? V₂ V₅  V₅ ? b

b. Order the productions:

V₁ ? V₄ V₆ | a   

V₂ ? V₄ V₆ | a

V₃ ? V₅ V₇ | b   

V₄ ? a

V₅ ? b

V₆ ? V₃ V₄

V₇ ? V₂ V₅

Rules for V₁, V₂, V₃, V₄, V₅ are okay.

Modify V₆-rule V₆ ? V₃ V₄:

Substitute PRODUCTIONs of V₃ in V₆-rule:

 V₆ ? V₅ V₇ V₄ | b V₄

Substitute PRODUCTIONs of V₅ in modified V₆-rule:

 V₆ ? b V₇ V₄ | b V₄    final V₆-rule

Modify V₇-rule V₇ ? V₂ V₅:

Substitute PRODUCTIONs of V₂ in V₇-rule:

 V₇ ? V₄ V₆ V₅ | a V₅

Substitute PRODUCTIONs of V₄ in modified V₇-rule:

 V₇ ? a V₆ V₅ | a V₅    final V₇-rule

c. Substitute to achieve Greibach Normal Form:

Everything already done in this case. Grammar is in GNF:

V₁ ? V₄ V₆ | a   

V₂ ? V₄ V₆ | a

V₃ ? V₅ V₇ | b   

V₄ ? a

V₅ ? b

V₆ ? b V₇ V₄ | b V₄

V₇ ? a V₆ V₅ | a V

DONE

Instructor: Mohamed U. Mahdi