Natural language processing previous year question paper(2009)

                    CS/B.Tech/(CSE)/SEM-8-April/CS-802B/2009
                                              2009
                    NATURAL LANGUAGE PROCESSING

Time Allotted : 3 Hours                                                                    Full Marks : 70 

                              The figures in the margin indicate full marks.

               Candidates are required to give their answers in their own words 

                                               as far as practicable.

                                   GROUP – A
                ( Multiple Choice Type Questions )

1.  Choose the correct alternatives for the following.  10*1 = 10

i) / [ 0 1 2 3 4 5 6 7 8 9 ] / specifiees
a) single digit
b) multiple digit
c) any digit
d) none of these

ii) colou?r mztches
a) color
b) color or colour
c) colour
d) none of these

iii) Minimum edit distance is computed by
a) Phonology
b) Dynamic programming
c) Tautology
d) Hidden Markov Model ( HMM ).

iv) Word probability is calculated by
a) Likelihood probability
b) Prior probability
c) Baye's rule
d) none of these.

v) Viterbi algorithm is used in
a) speech processing
b) Language processing
c) Speech & Language processing
d) none of these.

vi) In deleted interpolation algorithm, which symbol is used ?
a)  α 
b)  β
c)  γ
d) μ

vii) Entropy is used to
a) measure the information
b)correct the information
c) detect the information
d) handle the noise.

viii) Open class contains
a) nouns
b)verbs
c) both (a) and (b)

d) none of these

ix) Phrase Structure Grammar is used in

a) a) Regular Grammar

b) Context–Free Grammar ( CFG )

c) Context–Sensitive Grammar ( CSG )

d) None of these.

x) Subcategorize of verbs is classified into
a) Transitive
c) both (a) & (b)
b) Intransitive
d) none of these.

                                                            GROUP -B

                                         ( Short Answer Type Questions )
                                      Answer any three of the following.   3*5=15

2) What is Regular Expression ? Write down the Regular
Expression for the following languages :
a) The set of all alphabetic strings
b) $ 199.99
c) 4.3 MHz. 

3 )Write down the differences between Inflectional Morphology
and Derivational Morphology with suitable example. What is
stem ? What is morpheme ?  
                  
4) Define two level Morphology with suitable example. Briefly
describe the different types of Error Handling mechanism.
   

5) Why POS ( Part – of – Speech ) Tagging is required in NLP
( Natural Language Processing ) ? Briefly compare the Top – Down & Bottom – Up Parsing techniques.  
                                                                                 
6) Write down the concept of feature structure. What is
unification ? What is Word Sense Disambiguation ( WSD ) ?
                                                                                                              

                                                GROUP – C
                                 ( Long Answer Type Questions )
                          Answer any three of the followin  : 3*15 =45

7) a) What is Smoothing ? Why is it required ?

b) Write down the equation for trigram probability estimation.

c) Write down the equation for the discount d = c /c for add-one smoothing. Do the same thing used for Written Bell smoothing. How do they differ?                                                          

8) Find one tagging error in each of the following sentence that are tagged with the

Penn Treebank tagset :

i) I/PRP need/VBP a/DT flight/NN from/IN Atlana/NN

ii) Does/VBZ this/DT flight/NN serve/VB dinner/NNS

iii) I/PRP have/VB a/DT friend/NN living/VBG in/IN Denver/NNP.

b) Briefly describe the roles of Finite State Transducer ( F S T ) with suitable

example.

c) Define Prior probability and likelihood probability using Bayesian Method.

d) What is Confusion Matrix ? Why is it required in NLP ( Natural Language

Processing ) ?                                                                                                                           
9. a) Compute Minimum edit by hand. Figure out whether the word intention is closer to the word execution and calculate a minimum edit distance.

b) Estimate p ( t / c ) as follows (where c p is the pth character of the word c ) using Kernigham et al. four confusion matrices, one for each type of single error.

c) Briefly describe Hidden Markov Model ( HMM ).

d) Compare open class & closed class word groups with suitable examples.                 

10. a)Draw tree structure for the following ATIS sentences :

I perfer a morning flight

i want a morning flight

Using S-->NP VP

NP-->Pronoun|

Pronoun-Noun

|Det Nominal

Nominal-->|Noun Nominal

|Noun

VP-->verb

|Verb NP

|Verb NP PP

| Verb PP

b) Write rules expressing the verbal subcategory of English auxiliaries with example.

d) How are Transformation Based Learning ( TBL ) Rules applied in NLP ( Natural Language Processing ) ?                                                                                                          

11. Write short notes on any three of the following :         

a) Two level morphology

b) Stochastic Part-of-Speech Tagging

c) HMM Tagging

d) Constituency & Agreement.     

e) Problems with the basic top down parser
f) orthographic rules

                                             -----------------------x-------------------