Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 51 views

    Context Free Grammars Normal

    Uploaded by

    tariqravian
    The document discusses different techniques for simplifying and transforming context-free grammars. It introduces substitution rules to derive equivalent grammars. It also discusses removing nullable and unit productions. Useless productions that do not generate any strings are identified and removed. The goal is to derive a grammar containing only useful variables and productions. Finally, the document explains Chomsky normal form, where each production is either of the form A→BC or A→a, and provides an example of converting a grammar to this normal form.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Context Free Grammars Normal

    Uploaded by

    tariqravian
    51 views38 pages
    The document discusses different techniques for simplifying and transforming context-free grammars. It introduces substitution rules to derive equivalent grammars. It also discusses removing nullable and unit productions. Useless productions that do not generate any strings are identified and removed. The goal is to derive a grammar containing only useful variables and productions. Finally, the document explains Chomsky normal form, where each production is either of the form A→BC or A→a, and provides an example of converting a grammar to this normal form.

    Original Description:

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses different techniques for simplifying and transforming context-free grammars. It introduces substitution rules to derive equivalent grammars. It also discusses removing nullable and unit productions. Useless productions that do not generate any strings are identified and removed. The goal is to derive a grammar containing only useful variables and productions. Finally, the document explains Chomsky normal form, where each production is either of the form A→BC or A→a, and provides an example of converting a grammar to this normal form.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    51 views38 pages

    Context Free Grammars Normal

    Uploaded by

    tariqravian
    The document discusses different techniques for simplifying and transforming context-free grammars. It introduces substitution rules to derive equivalent grammars. It also discusses removing nullable and unit productions. Useless productions that do not generate any strings are identified and removed. The goal is to derive a grammar containing only useful variables and productions. Finally, the document explains Chomsky normal form, where each production is either of the form A→BC or A→a, and provides an example of converting a grammar to this normal form.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 38

    Simplifications

    of
    Context-Free Grammars

    Fall 2005 Costas Buch - RPI 1


    A Substitution Rule

    Equivalent
    grammar
    S  aB
    S  aB | ab
    A  aaA
    Substitute A  aaA
    A  abBc Bb A  abBc | abbc
    B  aA
    B  aA
    Bb
    Fall 2005 Costas Buch - RPI 2
    S  aB | ab
    A  aaA
    A  abBc | abbc
    B  aA
    Substitute
    B  aA

    S  aB | ab | aaA
    A  aaA Equivalent
    A  abBc | abbc | abaAc grammar
    Fall 2005 Costas Buch - RPI 3
    In general: A  xBz

    B  y1

    Substitute
    B  y1

    equivalent
    A  xBz | xy1z grammar
    Fall 2005 Costas Buch - RPI 4
    Nullable Variables

      production : X 
    Nullable Variable: Y  
    Example: S  aMb
    M  aMb
    M 

    Nullable variable   production


    Fall 2005 Costas Buch - RPI 5
    Removing   productions
    S  aMb S  aMb | ab
    Substitute
    M  aMb M  M  aMb | ab
    M 

    After we remove all the   productions


    all the nullable variables disappear
    (except for the start variable)
    Fall 2005 Costas Buch - RPI 6
    Unit-Productions
    Unit Production: X Y
    (a single variable in both sides)

    Example: S  aA
    Aa
    A B
    Unit Productions
    BA
    B  bb
    Fall 2005 Costas Buch - RPI 7
    Removal of unit productions:

    S  aA
    S  aA | aB
    Aa
    Substitute Aa
    A B A B B  A| B
    BA
    B  bb
    B  bb

    Fall 2005 Costas Buch - RPI 8


    Unit productions of form XX
    can be removed immediately

    S  aA | aB S  aA | aB
    Aa Remove Aa
    B  A| B BB BA
    B  bb B  bb

    Fall 2005 Costas Buch - RPI 9


    S  aA | aB
    S  aA | aB | aA
    Aa Substitute
    BA Aa
    BA
    B  bb
    B  bb

    Fall 2005 Costas Buch - RPI 10


    Remove repeated productions

    Final grammar
    S  aA | aB | aA S  aA | aB
    Aa Aa
    B  bb B  bb

    Fall 2005 Costas Buch - RPI 11


    Useless Productions

    S  aSb
    S 
    SA
    A  aA Useless Production

    Some derivations never terminate...

    S  A  aA  aaA    aa aA  
    Fall 2005 Costas Buch - RPI 12
    Another grammar:

    SA
    A  aA
    A
    B  bA Useless Production
    Not reachable from S

    Fall 2005 Costas Buch - RPI 13


    In general:

    If there is a derivation
    S    xAy    w  L(G )
    consists of
    terminals
    Then variable A is useful

    Otherwise, variable A is useless

    Fall 2005 Costas Buch - RPI 14


    A production A  x is useless
    if any of its variables is useless

    S  aSb
    S  Productions
    Variables SA useless
    useless A  aA useless
    useless B  C useless

    useless CD useless


    Fall 2005 Costas Buch - RPI 15
    Removing Useless Variables and Productions

    Example Grammar: S  aS | A | C
    Aa
    B  aa
    C  aCb

    Fall 2005 Costas Buch - RPI 16


    First: find all variables that can produce
    strings with only terminals or 
    (these are possible useful variables)

    S  aS | A | C Round 1: { A, B}
    Aa (the right hand side of a production
    has only terminals)

    B  aa
    Round 2: { A, B, S }
    C  aCb (the right hand side of a production
    has terminals and
    variables of previous round)

    This process can be generalized


    Fall 2005 Costas Buch - RPI 17
    Then, remove productions that use variables
    other than { A, B, S }

    S  aS | A | C
    Aa S  aS | A
    B  aa Aa
    C  aCb B  aa

    Fall 2005 Costas Buch - RPI 18


    Second: Find all variables
    reachable from S

    Use a Dependency Graph

    S  aS | A
    Aa S A B
    B  aa not
    reachable

    Fall 2005 Costas Buch - RPI 19


    Keep only the variables
    reachable from S

    Final Grammar
    S  aS | A
    S  aS | A
    Aa
    Aa
    B  aa
    Contains only
    useful variables

    Fall 2005 Costas Buch - RPI 20


    Removing All
    Step 1: Remove Nullable Variables

    Step 2: Remove Unit-Productions

    Step 3: Remove Useless Variables

    This sequence guarantees that


    unwanted variables and production
    are removed
    Fall 2005 Costas Buch - RPI 21
    Normal Forms
    for
    Context-free Grammars

    Fall 2005 Costas Buch - RPI 22


    Chomsky Normal Form

    Each productions has form:

    A  BC or Aa

    variable variable terminal

    Fall 2005 Costas Buch - RPI 23


    Examples:

    S  AS S  AS
    S a S  AAS
    A  SA A  SA
    Ab A  aa
    Chomsky Not Chomsky
    Normal Form Normal Form

    Fall 2005 Costas Buch - RPI 24


    Convertion to Chomsky Normal Form

    Example: S  ABa
    Not Chomsky
    A  aab Normal Form
    B  Ac

    We will convert it to Chomsy Normal Form

    Fall 2005 Costas Buch - RPI 25


    Introduce new variables for the terminals:
    Ta , Tb , Tc
    S  ABTa
    S  ABa A  TaTaTb
    A  aab B  ATc
    B  Ac Ta  a
    Tb  b
    Tc  c
    Fall 2005 Costas Buch - RPI 26
    Introduce new intermediate variable V1
    to break first production:
    S  AV1
    S  ABTa
    V1  BTa
    A  TaTaTb
    A  TaTaTb
    B  ATc
    B  ATc
    Ta  a
    Ta  a
    Tb  b
    Tb  b
    Tc  c
    Tc  c
    Fall 2005 Costas Buch - RPI 27
    Introduce intermediate variable: V2
    S  AV1
    S  AV1
    V1  BTa
    V1  BTa
    A  TaV2
    A  TaTaTb
    V2  TaTb
    B  ATc
    B  ATc
    Ta  a
    Ta  a
    Tb  b
    Tb  b
    Tc  c
    Fall 2005 Costas Buch - RPI Tc  c 28
    Final grammar in Chomsky Normal Form:
    S  AV1
    V1  BTa
    A  TaV2
    Initial grammar
    V2  TaTb
    S  ABa B  ATc
    A  aab Ta  a
    B  Ac Tb  b

    Fall 2005 Costas Buch - RPI


    Tc  c 29
    In general:

    From any context-free grammar


    (which doesn’t produce  )
    not in Chomsky Normal Form

    we can obtain:
    an equivalent grammar
    in Chomsky Normal Form

    Fall 2005 Costas Buch - RPI 30


    The Procedure

    First remove:

    Nullable variables

    Unit productions

    Fall 2005 Costas Buch - RPI 31


    Then, for every symbol a:

    Add production Ta  a

    In productions: replace a with Ta

    New variable: Ta
    Fall 2005 Costas Buch - RPI 32
    Replace any production A  C1C2 Cn

    with A  C1V1
    V1  C2V2

    Vn2  Cn1Cn

    New intermediate variables: V1, V2 ,  ,Vn2


    Fall 2005 Costas Buch - RPI 33
    Observations

    • Chomsky normal forms are good


    for parsing and proving theorems

    • It is easy to find the Chomsky normal


    form for any context-free grammar

    Fall 2005 Costas Buch - RPI 34


    Greinbach Normal Form

    All productions have form:

    A  a V1V2 Vk k 0

    symbol variables

    Fall 2005 Costas Buch - RPI 35


    Examples:

    S  cAB
    S  abSb
    A  aA | bB | b
    S  aa
    Bb

    Greinbach Not Greinbach


    Normal Form Normal Form

    Fall 2005 Costas Buch - RPI 36


    Conversion to Greinbach Normal Form:

    S  aTb STb
    S  abSb S  aTa
    S  aa Ta  a
    Tb  b
    Greinbach
    Normal Form
    Fall 2005 Costas Buch - RPI 37
    Observations

    • Greinbach normal forms are very good


    for parsing strings (better than Chomsky Normal Forms)

    • However, it is hard to find the


    Greinbach normal of a grammar

    Fall 2005 Costas Buch - RPI 38

    You might also like