Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    Understanding Natural Languages

    Uploaded by

    souravmaity94302

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Understanding Natural Languages

    Uploaded by

    souravmaity94302
    3 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    3 views2 pages

    Understanding Natural Languages

    Uploaded by

    souravmaity94302

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Understanding Natural Languages

    Parsing Techniques, Context-Free and Transformational Grammars, Recursive and Augmented


    Transition Nets.

    Context Free Grammar (CFG)


    The grammar in which each production has exactly one terminal symbol in its left hand side and at
    least one symbol at the right hand side is called context free grammar. A CFG is defined as four tuples −
    G=(V,T,P,S)
     G is a grammar, which consists of a set of production rules. It is used to generate the strings of a
    language.
     V is the final set of non-terminal symbols. It is denoted by capital letters
     T is the final set of terminal symbols. It is denoted by lower case letters.
     P is a finite set of production rules, each of the form A →, where
    A ∈ V and α ∈ (V ∪ T)*
     S is the start symbol (S ∈ V)

    Example
     The grammar ({A}, {a, b, c}, P, A), P : A → aA, A → abc.
     The grammar ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε

    Parse tree
    o Parse tree is the graphical representation of symbol. The symbol can be terminal or non-terminal.
    o In parsing, the string is derived using the start symbol. The root of the parse tree is that start symbol.
    o It is the graphical representation of symbol that can be terminals or non-terminals.
    o Parse tree follows the precedence of operators. The deepest sub-tree traversed first. So, the operator
    in the parent node has less precedence over the operator in the sub-tree.
    The parse tree follows these points:
    o All leaf nodes have to be terminals.
    o All interior nodes have to be non-terminals.
    o In-order traversal gives original input string.

    Transformational Grammar
    These are the grammars in which the sentence can be represented structurally into two stages.
    Obtaining different structures from sentences having the same meaning is undesirable in language
    understanding systems. Sentences with the same meaning should always correspond to the same internal
    knowledge structures.
    The transformation rules can produce a change from passive voice to active voice and vice versa. Let
    us see the structure of a sentence as given below.
    1. Ram is eating an apple (In Active Voice)
    2. An apple is being eaten by Ram (In Passive Voice)

    Both of the above sentences are two different sentences but they have same meaning. Thus it is an example
    of a transformational grammar. These grammars were never widely used in computational models of natural
    language. The applications of this grammar are changing of voice (Active to Passive and Passive to Active)
    change a question to declarative form etc.

    TRANSITION NETWORK
     It is a method to represent the natural languages.
     A transition network may consist of some states or nodes, some labeled arcs from one state to the next
    state through which it will move.
     The arc represents the rule or some conditions upon which the transition is made from one state to
    another state.
    For example, a transition network is used to recognize a sentence consisting of an article, a noun, an auxiliary,
    a verb, an article, a noun would be represented by the transition network as follows.

    The transition from N1 to N2 will be made if an article is the first input symbol. If successful, state
    N2 is entered. The transition from N2 to N3 can be made if a noun is found next. If successful, state N3 is
    entered. The transition from N3 to N4 can be made if an auxiliary is found and so on. Suppose consider a
    sentence “A boy is eating a banana”. So if the sentence is parsed in the above transition network then, first
    ‘A’ is an article. So successful transition to the node N1 to N2. Then boy is a noun (so N2 to N3), “is” is an
    auxiliary (N5 to N6) and finally “banana” is a noun (N 6 to N7) is done successfully. So the above sentence is
    successfully parsed in the transition network.

    Types of transition network


    There are generally two types of transition networks like
    1. Recursive Transition networks (RTN)
    2. Augmented Transition networks (ATN)

    You might also like