MODULE 2 NLP [BAI601]

MODULE 2
SYLLABUS:
Word Level Analysis: Regular Expressions, Finite-State Automata,
Morphological Parsing, Spelling Error Detection and Correction, Words and
Word Classes, Part-of Speech Tagging.
Syntactic Analysis: Context-Free Grammar, Constituency, Top-down and
Bottom-up Parsing, CYK Parsing.
_________________________________________________________________
Contents
2.1 Regular Expressions..........................................................................................2
2.1.1 Case Sensitivity in Regular Expressions ............................................... 3
2.1.2 Special Operators in Regular Expressions ............................................. 3
2.1.3 Anchors in Regular Expressions............................................................ 4
2.1.4 Wildcard Character (.) .......................................................................... 4
2.1.5 Regular Expressions for Validation ....................................................... 4
2.2 Finite-State Automata ..................................................................................5
2.3 Morphological Parsing ......................................................................................9
2.3.1 From the Surface to the Intermediate Form ......................................... 11
2.3.2 From the Intermediate Form to the Morphological Structure ............. 12
2.4 Spelling Error Detection and Correction ........................................................14
2.4.1 Minimum Edit Distance ....................................................................... 16
2.5 Part-Of-Speech Tagging .................................................................................18
2.5.1 Rule Based Tagger ............................................................................... 21
2.5.2 Stochastic Tagger ................................................................................ 22
2.5.3 Hybrid Taggers .................................................................................... 25
2.6 Context-Free Grammar ...................................................................................28
2.6.1 Phrase Level Constructions ................................................................. 28
2.6.2 Sentence Level Constructions ............................................................. 33
2.7 Parsing.............................................................................................................35
2.7.1 Top-Down Parsing ............................................................................... 36
2.7.2 Bottom-up Parsing ............................................................................... 39

1|Page
 MODULE 2 NLP [BAI601]

2.7.3 CYK Parsing ........................................................................................ 42

____________________LECTURE 07______________________

2.1 Regular Expressions

Regular expressions, or regex, are a powerful pattern-matching standard used
for string parsing, searching, and replacement. They are widely applied in
Natural Language Processing (NLP) to handle text processing tasks like
tokenization, information retrieval, and text validation.

Applications for Regular Expressions

• Parsing dates, URLs, and email addresses.

• Extracting patterns from log files, configuration files, or command-
line inputs.
• Searching for specific words or phrases in text documents.
• Preprocessing text for NLP tasks like tokenization and stemming.

We have used simplified forms of regular expressions, such as the file search
patterns used by MS DOS, e.g., dir*.txt. The use of regular expressions in
computer science was made by a Unix-based editor, ‘ed’.Perl was the first
language that provided integrated support for regular expressions. It used a
slash around each regular expression.

Regular expressions were first introduced by Kleene.A regular expression is

an algebraic formula whose value is a pattern consisting of a set of strings,
called the language of the expression.

The simplest kind of regular expression contains a single symbol.

Ex: /a/ denotes the set containing the string ‘a’.

A regular expression may specify a sequence of characters also.

Ex: /supernova/ denotes the set that contains the string ‘supernova’.

Simple Regular Expressions:

Regular Expression Example Patterns

/book/ The world is a book and those who do not travel
read only one page.
2|Page
 MODULE 2 NLP [BAI601]

/book/ Reporters who do not read the style book, should

not criticize their editors
/face/ Not everything is faced can be charged. But nothing
can be changed until it is faced.
/a/ Reason, observation and experience -the holy
trinity of science.

Character Classes:
Character classes define sets of characters to match specific patterns.
Regex Pattern Explanation Example Matches

[abcd] Matches any one of the given "a", "b", "c", "d"
characters
[^abcd] Matches any character except the "e", "f", "g"
given ones
[a-z] Matches any lowercase letter "m", "p", "z"
from a to z
[A-Z] Matches any uppercase letter "K", "X"
from A to Z
[0-9] Matches any digit from 0 to 9 "3", "7", "9"

2.1.1 Case Sensitivity in Regular Expressions

Regular expressions are case-sensitive by default.

• /s/matches lowercase "s", but not uppercase "S".

• To match both, use [sS].

2.1.2 Special Operators in Regular Expressions

Special operators modify how regex patterns match text.

Operator Function Example Matches

? Makes preceding character colou?r "color", "colour"
optional
* Matches zero or more go* "g", "go", "goo"
occurrences
+ Matches one or more go+ "go", "goo"
occurrences
{n} Matches exactly n \d{3} "123", "456"
occurrences

3|Page
 MODULE 2 NLP [BAI601]

{n,} Matches at least n a{2,} "aa", "aaa"

occurrences

2.1.3 Anchors in Regular Expressions

Anchors help match patterns at specific positions in a string.

Anchor Function Example Matches

^ Start of a line /^Hello/ "Hello world"
$ End of a line /world$/ "Goodbye world"

2.1.4 Wildcard Character (.)

• The dot (.) matches any single character except a newline.

• Example:
o /.at/ matches "cat", "bat", "rat", "hat".

2.1.5 Regular Expressions for Validation

Regular expressions can be used to validate structured input like email addresses.

Regex for Validating an Email Address

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

Explanation:

1. ^ → Ensures the match starts at the beginning of the string.

2. [a-zA-Z0-9._%+-]+ → Matches usernames with allowed characters.
3. @ → Ensures "@" appears exactly once.
4. [a-zA-Z0-9.-]+ → Matches the domain name (e.g., "[Link]").
5. \. → Matches the dot (.) before the extension.
6. [a-zA-Z]{2,} → Matches domain extensions (com, org, edu).
7. $ → Ensures the match ends at the end of the string.

Examples:

✔ Valid: user@[Link], [Link]@[Link]

✘ Invalid: user@com, user@.com, @[Link]

4|Page
 MODULE 2 NLP [BAI601]

REVIEW QUESTIONS

1. What is the purpose of using regular expressions in NLP?

2. What does the symbol . (dot) match in a regular expression?
3. Which regular expression symbol denotes zero or more occurrences of the
preceding element?
4. Give a regular expression to match any digit.
5. What does ^ represent when used at the beginning of a regular expression?

____________________LECTURE 10______________________
2.2 Finite-State Automata
Finite state automaton has a mathematical model which is quite
understandable; data can be represented in a compacted form using finite state
automaton and it allows automatic compilation of system components.
Finite state automata (deterministic and non-deterministic finite automata)
provide decisions regarding the acceptance and rejection of a string while
transducers provide some output for a given input. Thus the two machines are
quite useful in language processing tasks. Finite state automata are useful in
deciding whether a given word belongs to a particular language or not.
The term automata, derived from the Greek word “αὐτόματα” meaning “self-
acting”, is the plural of automaton which may be defined as an abstract self-
propelled computing device that follows a predetermined sequence of
operations automatically.
An automaton having a finite number of states is called a Finite Automaton
(FA) or Finite State automata (FSA).
Mathematically, an automaton can be represented by 5-tuple (Q, Σ, δ, q0, F),
where −
► Q is a finite set of states.
► Σ is a finite set of symbols, called the alphabet of the automaton
► δ is the transition function
► q0 is the initial state from where any input is processed (q0 ∈ Q)
► F is a set of final state/states of Q (F ⊆ Q)
A finite automaton can be deterministic or non-deterministic. In a non-
deterministic automaton, more than one transition out of a state is possible for
the same input symbol.
Example: Suppose ∑= {a, b}, the set of states = {q0, q1, q2, q3, q4} with q0

5|Page
 MODULE 2 NLP [BAI601]

being the start state and q4 the final state, we have the following rules of
transition:
1. From state q0 and with input a, go to state q1.
2. From state q1 and with input b, go to state q2.
3. From state q1 and with input c, go to state q3.
4. From state q2 and with input b, go to state q4.
5. From state q3 and with input b, go to state q4.
This finite state automaton is shown as a directed graph called transition
diagram as shown in figure 2.1. The nodes in this diagram correspond to the
states and the arcs to transitions. The arcs are labelled with inputs. The final
state is represented by a double circle. There is exactly one transition leading
out of each state. Hence this automaton is deterministic.

Figure 2.1 A deterministic FSA (DFA)

A deterministic finite-state automaton (DFA) is defined as a 5-tuple(Q, Σ, S, P,
δ),where Q is a set of states, Σ is an alphabet, S is the start state, Q is a set of
final states, and δ is a transition function. The transition function δ defines
mapping from Q* Σ to Q. That is, for each state q and symbol a, there is at most
one transition possible as shown in figure 3.1.

Unlike DFA, the transition function of a non-deterministic finite-state

automaton (NFA) maps Q* (Σ {}) to a subset of the power set of Q That is, for
each state, there can be more than one transition on a given symbol, each
leading to a different states,
This is shown in Figure 2.2, where there are two possible transitions from state
q0 on input symbol a.

6|Page
 MODULE 2 NLP [BAI601]

Figure 2.2 A non-deterministic FSA (NFA)

A path is a sequence of transitions beginning with the start state. A path leading
to one of the final states is a successful path. The FSAs encode regular
languages. The language that an FSA encodes is the set of strings that can be
formed by concatenating the symbols along each successful path. Clearly, for
automata with cycles, these sets are not finite.
Let us now examine what happens to various input strings that are presented to
finite state automata. Consider deterministic automation and the input, ac. We
start with state q0 and go to state q1. The next input symbol is c, so we go to
state q3. No more input is left, and we have not reached the final state, i.e., we
have an unsuccessful end. Hence, the string ac is not recognized by the
automaton.
This example illustrates how an FSA can be used to accept or recognize a
string. The set of all strings that leave us in a final state is called the language
accepted or defined by the FA. This means ac is not a word in the language
defined by the automaton.
Now, consider the input acb. Again, we start with state q0 and go to state q1.
The next input symbol is c, so we go to state q3. The next input symbol is b,
which leads to state q4. No more input is left and we have reached to final state,
i.e., this time we have a successful termination. Hence, the string acb is a word
of the language defined by the automaton.
The language defined by this automaton can be described by the regular
expression / abb|acb/.
The example considered here is quite simple. Typically, the list of transition
rules can be quite long. Listing all transition rules may be inconvenient, so
often we represent an automation as a state-transition table. The rows in this
table represent states and the columns correspond to input. The entries in the
table represent the transition corresponding to a given state-input pair. A Ф
entry indicates missing transition. This table contains all the information
needed by FSA. The state transition table for the automaton considered in the

7|Page
 MODULE 2 NLP [BAI601]

above example is shown in Table below:

Consider a language with all strings containing only as and bs and ending with
baa. We can specify this language by the regular expression /{a|b)*baa$/. The
NFA implementing this regular expression is shown in figure 2.3.

Figure 2.3 NFA for regular expression /{a|b)*baa$/

The state transition table for this NFA is shown below:

Two automata that define the same language are said to be equivalent. An NFA
can be converted to an equivalent DFA and vice versa. The equivalent DFA for
the NFA shown in Figure 2.3 is shown in Figure 2.4.

Figure 2.4 Equivalent DFA for NFA in figure 2.3

8|Page
 MODULE 2 NLP [BAI601]

2.3 Morphological Parsing

Morphology is a sub-discipline of linguistics. It studies word structure and the
formation of words from smaller units (morphemes). The goal of morphological
parsing is to discover the morphemes that build a given word.

Morphemes are the smallest meaning-bearing units in a language. For

example, the word 'bread' consists of a single morpheme and 'eggs' consist of two:
the morpheme egg and the morpheme -s. A morphological parser should be able
to tell us that the word 'eggs 'is the plural form of the noun stem 'egg'.

There are two broad classes of morphemes: stems and affixes. The stem is the
main morpheme, i.e., the morpheme that contains the central meaning. Affixes
modify the meaning given by the stem. Affixes are divided into prefixes, suffix,
infix, and circumfix. Prefixes are morphemes which appear before a stem, and
suffixes are morphemes applied to the end of the stem. Circumfixes are morphemes
that may be applied to either end of the stem while infixes are morphemes that
appear inside a stem.

There are three main ways of word formation: Inflection, Derivation and
compounding. In inflection a root word is combined with a grammatical
morpheme to yield a word of the same class as the original stem. Derivation
combines a word stem with a grammatical morpheme to yield a word belonging to
a different class. E.g formation of the noun computation from the verb compute.
The formation of a noun from a verb or adjective is called normalization.
Compounding is the process of merging two or more words to form a new word.
For example ,personal computer, desktop, overlook.

Morphological parsing takes as input the inflected surface form of each word in a
text. As output it produces the parsed form consisting of a canonical form(or
lemma) of the word and set of tags showing its syntactic category and
morphological characteristics. Ex possible part of speech and/or inflectional
properties. Morphological generation is the inverse of this process.

A morphological parser uses the following information sources:

i. Lexicon: A lexicon lists stems and affixes together with basic information
about them.
ii. Morphotactic: It is basically the model of morpheme ordering. In other
sense, the model explains which classes of morphemes can follow other
classes of morphemes inside a word. For example, the morphotactic fact is

9|Page
 MODULE 2 NLP [BAI601]

that the English plural morpheme always follows the noun rather than
preceding it.
iii. Orthographic rules: These spelling rules are used to model the changes
occurring in a word. For example, the rule of converting y to ie in word like
city+s = cities not citys.

The goal of morphological parsing is to find out what morphemes a given word is
built from. For example, a morphological parser should be able to tell us that the
word cats is the plural form of the noun stem cat, and that the word mice is the
plural form of the noun stem mouse. So, given the string cats as input, a
morphological parser should produce an output that looks like cat N PL. Here are
some more examples:

Morphological parsing yields information that is useful in many NLP applications.

In parsing, e.g., it helps to know the agreement features of words. Similarly,
grammar checkers need to know agreement information to detect such mistakes.
But morphological information also helps spell checkers to decide whether
something is a possible word or not, and in information retrieval it is used to search
not only cats, if that's the user's input, but also for a cat.

To get from the surface form of a word to its morphological analysis, we are
going to proceed in two steps. First, we are going to split the words up into its
possible components. So, we will make cat + s out of cats, using + to indicate
morpheme boundaries. In this step, we will also take spelling rules into account,
so that there are two possible ways of splitting up foxes, namely foxe + s and fox
+ s. The first one assumes that foxe is a stem and s the suffix, while the second one
assumes that the stem is fox and that the e has been introduced due to the spelling
rule that we saw above.

In the second step, we will use a lexicon of stems and affixes to look up the
categories of the stems and the meaning of the affixes. So, cat + s will get mapped
to cat NP PL, and fox + s to fox N PL. We will also find out now that foxe is not a
legal stem. This tells us that splitting foxes into foxe + s was actually an incorrect
way of splitting foxes, which should be discarded. But note that for the word houses
splitting it into house + s is correct.

10 | P a g e
 MODULE 2 NLP [BAI601]

Here is a picture illustrating the two steps of our morphological parser with some
examples.

2.3.1 From the Surface to the Intermediate Form

To do morphological parsing this transducer has to map from the surface form to
the intermediate form. For now, we just want to cover the cases of English singular
and plural nouns that we have seen above. This means that the transducer may or
may not insert a morpheme boundary if the word ends in s. There may be singular
words that end in s (e.g. kiss). That's why we don't want to make the insertion of a
morpheme boundary obligatory. If the word ends in ses, xes or zes, it may
furthermore delete the e when introducing a morpheme boundary. Here is a
transducer that does this. The ``other'' arc in this transducer stands for a transition
that maps all symbols except for s, z, x to themselves.

Let's see how this transducer deals with some of our examples. The following
graphs show the possible sequences of states that the transducer can go through
given the surface forms cats and foxes as input.
11 | P a g e
 MODULE 2 NLP [BAI601]

2.3.2 From the Intermediate Form to the Morphological Structure

Now, we want to take the intermediate form that we produced in the previous
section and map it to the underlying form. The input that this transducer must
accept is of one of the following forms:

• regular noun stem, e.g. cat

• regular noun stem + s, e.g. cat + s
• singular irregular noun stem, e.g. mouse
• plural irregular noun stem, e.g. mice

In the first case, the transducer must map all symbols of the stem to themselves
and then output N and SG. In the second case, it maps all symbols of the stem to
themselves, but then outputs N and replaces PL with s. In the third case, it does the
same as in the first case. Finally, in the fourth case, the transducer should map the
irregular plural noun stem to the corresponding singular stem (e.g. mice to mouse)
and then it should add N and PL. So, the general structure of this transducer looks
like this:

12 | P a g e
 MODULE 2 NLP [BAI601]

What still needs to be specified is how exactly the parts between state 1 and states
2,3, and 4 respectively look like. Here, we need to recognize noun stems and decide
whether they are regular or not. We do this by encoding a lexicon in the following
way. The transducer part that recognizes cat, for instance, looks like this:

And the transducer part mapping mice to mouse can be specified as follows:

Plugging these (partial) transducers into the transducer given above we get a
transducer that checks that input has the right form and adds category and numerus
information.

REVIEW QUESTIONS

1. What is the difference between deterministic and non-deterministic finite-

state automata?
2. What is the primary role of a finite-state automaton in NLP?
3. Which components make up finite-state automaton?
4. What is morphological parsing in the context of NLP?
5. Name the two stages of two-level morphological parsing.

13 | P a g e
 MODULE 2 NLP [BAI601]

____________________LECTURE 11______________________
2.4 Spelling Error Detection and Correction
In computer based information systems, errors of typing and spelling constitute a
very common source of variation between strings. These errors have been widely
investigated. All investigations agree that single character omission, insertion
,substitution and reversal are the most common typing mistakes. In an early
investigation, Damearu(1964) reported that over 80% of the typing errors were
single error misspellings:
1) Substitution of a single letter
2) omission of a single letter
3) Insertion of a single letter and
4) Transposition of two adjacent letters.

The most common type of single character error was substitution, followed by
omission of a letter and then insertion of a letter. Single character omission occurs
when a single character is missed (deleted), e.g., when 'concept' is accidentally
typed as `concpt'. Insertion error refers to the presence of an extra character in a
word, e.g. when 'error' is misspell as ‘errorn'. Substitution error occurs when a
wrong letter is typed in place of the right one, as in `errpr', where `p' appears in
place of 'o'. Reversal refers to a situation in which the sequence of characters is
reversed, e.g., `aer' instead of 'are'. This is also termed transposition.

Optical character recognition (OCR) and other automatic reading devices introduce
errors of substitution, deletion, and insertion but not of reversal. OCR errors are
usually grouped into five classes: substitution, multi-substitution(or framing),
space deletion or insertion, and failures. Unlike substitution errors made in typing,
OCR substitution errors are caused due to visual similarity such as c-->e, r-->n.
The same is true for multi-substitution, e.g., m—>rn. Failure occurs when the OCR
algorithm fails to select a letter with sufficient accuracy. The frequency and type
of errors are characteristics of the device. These errors can be corrected using
'context' or by using linguistic structures.

Unlike typing errors, spelling errors are mainly phonetic, where the misspell word
is pronounced in the same way as the correct word. Phonetic errors are harder to
set right because they distort the word by more than a single insertion, deletion, or
substitution. Phonetic variations are common in transliteration. For example,
spelling errors belong to one of two distinct categories: non-word errors and
real word errors. When an error results in a word that does not appear in each

14 | P a g e
 MODULE 2 NLP [BAI601]

lexicon or is not a valid orthographic word form, it is termed a non-word error.

Most of the early research on spelling errors focused on the detection of such non-
words. The two main techniques used were n-gram analysis and dictionary lookup.

A real-word error results in actual words of the language. It occurs due to

typographical mistakes or spelling errors, e.g substituting the spelling of a
homophone or near-homophone, such as piece for peace or meat for meet.

Spelling correction consists of detecting and correcting errors. Error detection is

the process of finding misspelled words and error correction is the process of
suggesting correct words to a misspelled one. The spelling correction algorithm
has been broadly categorized as follows:
Minimum Edit Distance: The minimum edit distance between two strings is the
minimum number of operations required to transform one string into another. This
is one of the most used algorithms.
Similarity key techniques: The basic idea in a similarity key technique is to
change a given string into a key such that similar strings will change into the same
key. The SOUNDEX system (Odell and Russell 1918) is an example of a system
that uses this technique in phonetic spelling correction applications.
n-gram based techniques: The n-grams can be used for both non-word and real-
word error detection because in the English alphabet, certain bi-grams and tri-
grams of letters never occur or rarely do so; for example the tri-gram qst and the
bi-gram qd. This information can be used to handle non-word error. Strings that
contain these unusual n-grams can be identified as possible spelling errors. n-gram
techniques usually require a large corpus or dictionary as training data, so that an
n-gram table of possible combinations of letters can be compiled. In case of real-
word error detection, we calculate the likelihood of one character following
another and use this information to find possible correct word candidates.
Neural nets: These can-do associative recall based on incomplete and noisy data.
They can be trained to adapt to specific spelling error patterns. The drawback of
neural nets is that they are computationally expensive.
Rule-based technique: In a rule-based technique, a set of rules (heuristics) derived
from knowledge of a common spelling error pattern is used to transform misspelled
words into valid words. For example, if it is known that many errors occur from
the letters ue being typed as eu, then we may write a rule that represents this.

15 | P a g e
 MODULE 2 NLP [BAI601]

2.4.1 Minimum Edit Distance

The minimum edit distance is the number of insertions, substitutions required to
change one string into another (Wagner and Fischer 1974). When we talk about
distance between two strings, we are talking of the minimum edit distance. For
example, the minimum edit distance between 'tutor' and 'tumor' is 2: We substitute
'in' for 't' and insert `u' before 'r'. No smaller edit sequence can be found for this
conversion. Therefore, the minimum edit distance is 2.

Edit distance can be viewed as a string alignment problem. By aligning two strings,
we can measure the degree to which they match. There may be more than one
possible alignment between two strings. The best possible alignment corresponds
to the minimum edit distance between the strings. The alignment shown here,
between tutor and tumour has a distance of 2.

A dash in the upper string indicates insertion. A substitution occurs when the two
alignment symbols do not match (shown in bold). We can associate a weight or
cost with each operation. The Levensthein distance between two sequences is
obtained by assigning a unit cost to each operation. Another possible alignment for
these sequences is:

which has a cost of 3. We already have a better alignment than this one.

The problem of finding minimum edit distance seems quite simple but in fact is
not so. A choice that seems good initially might lead to problems later. Dynamic
Programming Algorithm be quite useful for finding minimum edit distance
between two sequences. Dynamic programming refers to a class of algorithms that
apply a table-driven approach to solving problems by combining solutions to sub-
problems. The dynamic programming algorithm for minimum edit distance is
implemented by creating an edit distance matrix. This matrix has one row for each
symbol in the source string and one column for each matrix in the target string.

The (i,j)th cell in this matrix represents the distance between the first i character of
the source and the first j character of the target string. Each cell can be computed
as a simple function of its surrounding cells. Thus, by starting at the beginning of
the matrix, it is possible to fill each entry iteratively. The value in each cell is
computed in terms of three possible paths:

16 | P a g e
 MODULE 2 NLP [BAI601]

The substitution will be 0 if the ith character in the source matches with jth character
in the target. The minimum edit distance algorithm is given below:

Input: Two strings, X and Y

Output: The minimum edit distance between X and Y
m ← length(X)
n ← length(Y)

for i = 0 to m do
dist[i,0] ← i

for j = 0 to n do
dist[0,j] ← j

for i = 0 to m do
for j = 0 to n do
dist[i,j] ← min(
dist[i-1,j] + insert_cost,
dist[i-1,j-1] + subst_cost(Xᵢ, Yⱼ),
dist[i,j-1] + delete_cost
)

How the algorithm computes the minimum edit distance between tutor and tumour
is shown in Figure 2.5.

Figure 2.5 Minimum edit distance matrix

17 | P a g e
 MODULE 2 NLP [BAI601]

REVIEW QUESTIONS
1. What are the three basic edit operations used in computing minimum edit
distance?
2. What is the minimum edit distance between two identical strings?
3. Which algorithm is commonly used to compute the minimum edit distance
between two strings?
4. In minimum edit distance, what does substitution operation represent?

____________________LECTURE 12______________________

2.5 Part-Of-Speech Tagging

Part-of-speech tagging is the process of assigning a part-of-speech (such as a
noun, verb, pronoun, preposition, adverb, and adjective), to each word in a
sentence. For example, the English word 'book' can be a noun as in ‘I am reading
a good book' or a verb as in 'The police booked the snatcher'. The same is true for
other languages. For example, the Hindi word ‘sona' may mean 'gold' (noun) or
'sleep' (verb). However, only one of the possible meanings is used at a time. In
tagging, we try to determine the correct lexical category of a word in its context.
No tagger is efficient enough to identify the correct lexical category of each word
in a sentence in every case. The tag assigned by a tagger is the most likely for a
particular use of word in a sentence.

The collection of tags used by a particular tagger is called a tag set. Most part-of-
speech tag sets make use of the same basic categories, i.e., noun, verb, adjective,
and prepositions. However, tag sets differ in how they define categories and how
finely they divide words into categories. For example, both eat and eats might be
tagged as a verb in one tag set but assigned distinct tags in another tag set. In
addition, most tag sets capture morphosyntactic information such as
singular/plural, number, gender, tense, etc.

Consider the following sentences:

• Zuha eats an apple daily.

• Aman ate an apple yesterday.
• They have eaten all the apples in the basket.
• I like to eat guavas.

The word eat has a distinct grammatical form in each of these four sentences. Eat
is the base form, ate its past tense and the form eats requires a third person singular

18 | P a g e
 MODULE 2 NLP [BAI601]

subject. Similarly eaten is the past participle form and cannot occur in another
grammatical context. It is required after have or has. Thus the following sentences
are ungrammatical:

• I like to eats guava.

• They eaten all the apples.

The Penn Treebank tag set contains 45 tags while C7 uses [Link] a language like
English, which is not morphologically rich, the C7 tagset is too big. The tagging
process would yield too many mis tagged words and the result would have to be
manually corrected. The larger the tag set, the greater the information captured
about a linguistic context. The task of tagging becomes complicated and requires
manual correction.

A tag set that uses just one tag to denote all the verbs will assign identical tags to
all the forms of a verb. The Penn Treebank tag captures finer distinction by
assigning distinct tags to distinct grammatical forms of a verb.

Tags assigned to the four different forms of the word eat according to this tag set
are shown below.

eat → VB

ate → VBD

19 | P a g e
 MODULE 2 NLP [BAI601]

eaten → VBN

eats → VBP

Examples for tagged sentences:

• Example 1: "The quick brown fox jumps over the lazy dog.”

• The/DT quick/JJ brown/JJ fox/NN jumps/VBZ over/IN the/DT lazy/JJ

dog/NN.

• Example 2: "She is eating a delicious cake in the kitchen.”

• She/PRP is/VBZ eating/VBG a/DT delicious/JJ cake/NN in/IN the/DT

kitchen/NN

20 | P a g e
 MODULE 2 NLP [BAI601]

Part of speech tagging methods fall under the three general categories:

• Rule based (linguistic)

• Stochastic (data driven)
• Hybrid

Stochastic taggers have data driven approaches in which frequency-based

information is automatically derived from corpus and used to tag words. Stochastic
taggers disambiguate words based on the probability that a word occurs with a
particular tag. An early example of stochastic tagger was CLAWS constituent
likelihood automatic word tagging system).CLAWS is the Stochastic equivalent of
TAGGIT. Hidden Markov model(HMM) is the standard Stochastic tagger.
Hybrid taggers combine features of both these approaches. Like rule-based
systems, they use rules to specify tags. Like stochastic systems, they use machine
learning to induce rules from a tagged training corpus automatically. The
transformation based tagger or Brill tagger is an example of the hybrid approach.

2.5.1 Rule Based Tagger

Rule based taggers use hand coded rules to assign tags to words. Rule Based
Taggers have a two-stage architecture. The first stage is simply a dictionary look
up procedure, which returns a set of potential tags (parts of speech) and appropriate
syntactic features for each word. The second stage uses a set of hand coded rules
to discard contextually illegitimate tags to get a single part of speech for each word.
Example: The show must go on.
The potential tags for the word show in this sentence is {VB,NN}
RULE: IF preceding word is determiner, THEN eliminate VB tag
This rule simply disallows verbs after a determiner. Using this rule the word show
in the given sentence can only be noun.
Example of a rule that make use of morphological information is:
IF word ends in -ing and preceding word is a verb THEN label it a verb(VB).
Rule based taggers usually require supervised training. To induce rules untagged
text is run through a tagger. The output is then manually corrected. The corrected
text is then submitted to the tagger which learns correction rules by comparing the
two sets of data.
Speed is an advantage of the rule-based tagger and unlike stochastic taggers they
are deterministic. In the rule based system, time is spent in writing a rule set. For
stochastic taggers, time is spent developing restrictions on transitions and

21 | P a g e
 MODULE 2 NLP [BAI601]

emissions to improve tagger performance. Another disadvantage of rule-based

tagger is that it is useable for only one language. Using it for another one requires
a rewrite of most of the program.

2.5.2 Stochastic Tagger

The standard stochastic tagger algorithm is the Hidden Markov Model (HMM)
tagger. A Markov model applies the simplifying assumption that the probability of
a chain of symbols can be approximated in terms of its parts or n -grams. The
simplest n-gram model is the unigram model, which assigns the most likely tag
(part of speech) to each token.
The unigram model needs to be trained using a tagged training corpus before it can
be used to tag data. The context used by the unigram tagger is the text of the word
itself.
Given a sequence of words, the objective is to find the most probable tag sequence
for the sentence.
Let W be the sequence of words, W= w1,w2,…….wn. The task is to find the tag
sequence, T = t1,t2…….tn, which maximizes P(T|W) i.e
T=argmaxT P(T|W)
Applying Bayes Rule, P(T|W) can be estimated using the expression:
P(T|W) = P(W|T) * P(T)/P(W)
As the probability of the word sequence, P(W), remains the same for each tag
sequence, we can drop it. The expression for the most likely tag sequence becomes:
T = argmaxT P(W|T)*P(T)
Using the Markov assumption, the probability of a tag sequence can be estimated
as the product of the probability of its constituent n-grams, i.e

P(W/T) is the probability of seeing a word sequence, given a tag sequence.

Example: ‘The egg is rotten” given ‘DT NNP VB JJ’. The following two
assumptions are made:

• The words are independent of each other.

• The probability of a word is dependent only on its tag.

Using these assumptions, we obtain

22 | P a g e
 MODULE 2 NLP [BAI601]

Approximating the tag history using only the two previous tags, the transition
probability, P(T), becomes

We estimate these probabilities from relative frequencies via Maximum

Likelihood Estimation.

Stochastic models have the advantage of being accurate and language independent.
Most stochastic taggers have an accuracy of 96-97%. The accuracy seems to be
quite high but it should be noted that this is measured as a percentage of words. An
accuracy of 96%means that for a sentence containing 20 words, the error rate per
sentence will be 1-0.9620=56%. This corresponds to approximately one word per
sentence. One of the drawbacks of stochastic taggers is that they require a manually
tagged corpus for training.
Example: Consider the sentence “The bird can fly” and the tag sequence DT NNP
MD VB

23 | P a g e
 MODULE 2 NLP [BAI601]

Exercise:
"She plays football."
Two possible POS tag sequences:

1. She/PRP plays/VBZ football/NN

2. She/NN plays/PRP football/VBZ

1. Probability of She/PRP plays/VBZ football/NN

24 | P a g e
 MODULE 2 NLP [BAI601]

2. Probability of She/NN plays/PRP football/VBZ

Thereby She/PRP plays/VBZ football/NN is the better tagging.

2.5.3 Hybrid Taggers

Hybrid approaches to tagging combine the features of both the rule based and
stochastic approaches. They use rules to assign tags to words. Like the stochastic
taggers, this is a machine learning technique, and rules are automatically induced
from the data. Transformation based learning of tags, also known as Brill tagging,
is an example of hybrid approach.

Figure 2.6 illustrates the TBL process. Like most HMM taggers, TBL is also a
supervised learning technique.

25 | P a g e
 MODULE 2 NLP [BAI601]

Figure 2.6 TBL Learner

The steps involved in the TBL tagging algorithm are shown below:

INPUT: Tagged corpus and lexicon (with most frequent information)

Step 1: Label every word with most likely tag (from dictionary)
Step 2: Check every possible transformation and select one which most
improves tagging
Step 3: Re-tag corpus applying the rules
Repeat 2–3 Until some stopping criterion is reached
RESULT: Ranked sequence of transformation rules

The input to Brill's TBL tagging algorithm is a tagged corpus and a lexicon (with
most frequent information as indicated in the training corpus). The initial state
annotator uses the lexicon to assign the most likely tag to each word as the start
state. An ordered set of transformation rules are applied sequentially. The rule that
results in the most improved tagging is selected. A manually tagged corpus is used
as reference for truth. The process is iterated until some stopping criterion is
reached, such as when no significant information is achieved over the previous

26 | P a g e
 MODULE 2 NLP [BAI601]

iteration. At each iteration, the transformation that results in the highest score is
selected. The output of the algorithm is a ranked list of learned transformation that
transform the initial tagging close to the correct tagging. New text can then be
annotated by first assigning the most frequent tag and then applying the ranked list
of learned transformations in order.

Example: Assume the word "fish" is most likely to be a noun.

Observation

• The most likely tag for "fish" is NNP, so both sentences are tagged with
NNP.
• This is incorrect in the second sentence.

Rule Learned by the Tagger

• Change NNP to VB if the previous tag is TO

Applied Transformation

• Sentence 2 is corrected:

27 | P a g e
 MODULE 2 NLP [BAI601]

REVIEW QUESTIONS

1. What is the main goal of Part-of-Speech (POS) tagging?

2. Give one example of a word that can belong to multiple word classes.
3. What does the POS tag ‘VB’ represent?
4. Which model is commonly used for statistical POS tagging?
5. What does ‘NNP’ stand for in POS tagging?

____________________LECTURE 13______________________

2.6 Context-Free Grammar

Context-free grammar (CFG) was first defined for natural language by Chomsky
(1957). A CFG (also called phrase-structure grammar) consists of four
components:

1. A set of non-terminal symbols, N

2. A set of terminal symbols, T
3. A designated start symbol, S, that is one of the symbols from N
4. A set of productions, P, of the form: A → α, where A ∈ N and α is a string
consisting of terminal and non-terminal symbols.

The rule A → α says that constituent A can be rewritten as α. This is also called
the phrase structure rule.

2.6.1 Phrase Level Constructions

A fundamental notion in natural language is that certain groups of words behave

as constituents. These constituents are identified by their ability to occur in similar
contexts. One of the simplest ways to decide whether a group of words is a phrase,
is to see if it can be substituted with some other group of words without changing
the meaning. If such a substitution is possible then the set of words forms a phrase.

28 | P a g e
 MODULE 2 NLP [BAI601]

This is called the substitution test. Consider the sentence Hena reads a book. We
can substitute several other phrases:

• Hena reads a book.

• Hena reads a storybook.
• Those girls read a book.
• She reads a comic book.

We can easily identify the constituents that can be replaced for each other in these
sentences. These are Hena, she, and Those girls and a book, a storybook, and a
comic book. These are the words that form a phrase. In linguistics, such
constituents represent a paradigmatic relationship. Elements that can substitute
each other in certain syntactic positions are said to be members of one paradigm.

Phrase types are named after their head, which is the lexical category that
determines the properties of the phrase. Thus, if the head is a noun, the phrase is
called a noun phrase, if the head is a verb, the phrase is called a verb phrase and so
on for other lexical categories like adjective and preposition.

Noun Phrase: A noun phrase is a phrase whose head is a noun or a pronoun,

optionally accompanied by a set of modifiers. It can function as subject, object, or
complement. The modifiers of a noun phrase can be determiners or adjective
phrases. The obligatory constituent of a noun phrase is the noun head—all other
constituents are optional. These structures can be represented using the phrase
structure rule. As discussed earlier, phrase structure rules are of the form A → BC,
which states that constituent A can be rewritten as two constituents B and C. These
rules specify which elements can occur in a phrase and in what order. Using this
notation, we can represent the phrase structure rules for a noun phrase as follows:

• NP → Pronoun
• NP → Det Noun

29 | P a g e
 MODULE 2 NLP [BAI601]

• NP → Noun
• NP → Adj Noun
• NP → Det Adj Noun

We can combine all these rules in a single phrase structure rule as follows:

NP → (Det) (Adj) Noun | Pronoun

The constituents in parentheses are optional. This rule states that a noun phrase
consists of a noun, possibly preceded by a determiner and an adjective (in that
order). This rule does not cover all possible NPs.

The noun phrase may include post-modifiers and more than one adjective. For
example, it may include a prepositional phrase (PP). More than one adjective is
handled by allowing an adjective phrase (AP) for the adjective in the rule. After
incorporating PP and AP in the phrase structure rule, we get the following:

NP → (Det) (AP) Noun (PP)

The following are a few examples of noun phrases:

• They (1a)
• The foggy morning (1b)
• Chilled water (1c)
• A beautiful lake in Kashmir (1d)
• Cold banana shake (1e)

Let us see how the phrases (1a–e) can be generated using phrase structure rules.
The phrase (1a) consists only of a pronoun; (1b) consists of a determiner, an
adjective (foggy) that stands for an entire adjective phrase, and a noun; (1c)
comprises an adjective phrase and a noun; (1d) consists of a determiner (the), an
adjective phrase (beautiful), a noun (lake), and a prepositional phrase (in Kashmir);

30 | P a g e
 MODULE 2 NLP [BAI601]

and (1e) consists of an adjective followed by a sequence of nouns. A noun sequence

is termed as nominal. None of the phrase structure rules discussed so far can handle
nominals. So, we modify our rules to cover this situation.

NP → (Det) (AP) Nom (PP)

Nom → Noun | Noun Nom

A noun phrase can act as a subject, an object, or a predicate. The following

sentences demonstrate each of these uses.

• The foggy damped weather disturbed the match. (2a)

• I would like a nice cold banana to shake. (2b)
• Kula botanical garden is a beautiful location. (2c)

In (2a), the noun phrase acts as a subject. In (2b), it acts as an object, and in (2c),
it is a predicate.

Verb Phrase: Analogous to the noun phrase is the verb phrase, which is headed
by a verb. There is a wide range of phrases that can modify a verb. This makes
verb phrases a bit more complex. The verb phrase organizes various elements of
the sentence that depend syntactically on the verb.

The following are some examples of verb phrases:

• Khushbu slept. (3a)

• The boy kicked the ball. (3b)
• Khushbu slept in the garden. (3c)
• The boy gave the girl a book. (3d)
• The boy gave the girl a book with blue cover. (3e)

As you can see from these examples a verb phrase can have a verb [VP → Verb in
(3a)]; a verb followed by an NP [VP → Verb NP in (3b)]; a verb followed by a PP

31 | P a g e
 MODULE 2 NLP [BAI601]

[VP → Verb PP in (3c)]; a verb followed by two NPs [VP → Verb NP NP in (3d)];
or a verb followed by two NPs and a PP [VP → Verb NP NP PP in (3e)]. In general,
the number of NPs in a VP is limited to two, whereas it is possible to add more
than two PPs.

VP → Verb (NP) (NP) (PP)*

Things are further complicated by the fact that objects may also be entire clauses
as in the sentence, I know that Taj is one of the seven wonders.
Hence, we must also allow for an alternative phrase statement rule, in which NP is
replaced by S.

VP → Verb S

Prepositional Phrase: Prepositional phrases are headed by a preposition. They

consist of a preposition, possibly followed by some other constituent, usually a
noun phrase, for example, we played volleyball on the beach.
We can have a preposition phrase that consists of just a preposition, for example,
John went outside.

The phrase structure rule that captures the above eventualities is as follows:
PP → Prep (NP)

Adjective Phrase: The head of an adjective phrase (AP) is an adjective. APs

consist of an adjective, which may be preceded by an adverb and followed by a
PP.
Here are a few examples:

• Ashish is clever.
• The train is very late.
• My sister is fond of animals.

32 | P a g e
 MODULE 2 NLP [BAI601]

The phrase structure rule for adjective phrase is:

AP → (Adv) Adj (PP)

Adverb Phrase: An adverb phrase consists of an adverb, possibly preceded by a

degree adverb. Here is an example: Time passes very quickly.
AdvP → (Intens) Adv

2.6.2 Sentence Level Constructions

Having discussed phrase structures, we now focus our attention on sentences. A

sentence can have varying structure. The four commonly known structures are
declarative structure, imperative structure, yes-no question structure, and wh-
question structure.

Sentences with a declarative structure have a subject followed by a predicate. The

subject of a declarative sentence is a noun phrase and the predicate is a verb phrase,
e.g., I like horse riding. The phrase structure rule for declarative sentences is:
S → NP VP

Sentences with an imperative structure usually begin with a verb phrase and lack
subject. The subject of these types of sentences is implicit and is understood to be
‘you’. These types of sentences are used for commands and suggestions and hence
are called imperative. The grammar rule for this kind of sentence structure is:
S → VP

Examples of this kind of sentences are as follows:

• Look at the door.

• Give me the book.
• Stop talking.
• Show me the latest design.

33 | P a g e
 MODULE 2 NLP [BAI601]

Sentences with the yes-no question structure ask questions which can be answered
using yes or no. These sentences begin with an auxiliary verb, followed by a subject
NP, followed by a VP. Here are some examples:

• Do you have a red pen?

• Is there a vacant quarter?
• Is the game over?
• Can you show me your album?

We expand our grammar by adding another rule for the expansion of S, as follows:
S → Aux NP VP

Sentences with wh-question structure are more complex. These sentences begin
with a wh-word—who, which, where, what, why, and how. A wh-question may
have a wh-phrase as a subject or may include another subject. Consider the
following wh-question:

Which team won the match?

This sentence is similar to a declarative sentence except that it contains a wh-word.

A simple rule to handle this type of sentence structure is:
S → Wh-NP VP

Another type of wh-question structure is one that involves more than one NP. In
this type of questions, the auxiliary verb comes before the subject NP, just as in
yes-no question structures.

Which cameras can you show me in your shop?

The rule for this type of wh-questions is:

S → Wh-NP Aux NP VP

34 | P a g e
 MODULE 2 NLP [BAI601]

A simplified view of the grammar rules discussed so far is summarized below:

_________________________________________________________________
• S → NP VP
• S → VP
• S → Aux NP VP
• S → Wh-NP VP
• S → Wh-NP Aux NP VP
• NP → (Det) (AP) Nom (PP)*
• VP → Verb (NP) (NP) (PP)*
• VP → Verb S
• AP → (Adv) Adj (PP)
• PP → Prep (NP)
• Nom → Noun (PP)*
REVIEW QUESTIONS

1. Define context-free grammar.

2. What are the four components of a CFG?
3. Which type of languages are generated by context-free grammar?
4. True or False: A CFG can generate both regular and non-regular languages.
5. What is the difference between a terminal and a non-terminal symbol in a
CFG?

____________________LECTURE 14______________________

2.7 Parsing
A CFG defines the syntax of a language but does not specify how structures are
assigned. The task that uses the rewrite rules of grammar to either generate a
particular sequence of words or reconstruct its derivation (or phrase structure tree)
is termed parsing. A phrase structure tree constructed from a sentence is called a
parse. The syntactic parser is thus responsible for recognizing a sentence and
assigning a syntactic structure to it. It is possible for many different phrase

35 | P a g e
 MODULE 2 NLP [BAI601]

structure trees to derive the same sequence of words. This means a sentence can
have multiple parses. This phenomenon is called syntactic ambiguity.

2.7.1 Top-Down Parsing

As the name suggests, top-down parsing starts its search from the root node S and
works downwards towards the leaves. The underlying assumption here is that the
input can be derived from the designated start symbol, S, of the grammar. The next
step is to find all sub-trees which can start with S. To generate the sub-trees of the
second-level search, we expand the root node using all the grammar rules with S
on their left-hand side. Likewise, each non-terminal symbol in the resulting sub-
trees is expanded next using the grammar rules having a matching non-terminal
symbol on their left-hand side. The right-hand side of the grammar rules provides
the nodes to be generated, which are then expanded recursively. As the expansion
continues, the tree grows downward and eventually reaches a state where the
bottom of the tree consists only of part-of-speech categories. At this point, all trees
whose leaves do not match words in the input sentence are rejected, leaving only
trees that represent successful parses.

Example 1: Perform top-down parsing for the sentence “Paint the Door” using the
grammar given below:

S → NP VP
S → VP
NP → Det Nominal
NP → Noun
NP → Det Noun PP
Nominal → Noun
Nominal → Noun Nominal
VP → Verb NP
VP → Verb
PP → Preposition NP
Det → this | that | a | the
Verb → sleeps | sings | open | saw | paint
Preposition → from | with | on | to
Pronoun → she | he | I | they

A top-down approach begins with a start symbol of the grammar. The given
grammar has two rules with S. These rules are used to expand the tree, which gives

36 | P a g e
 MODULE 2 NLP [BAI601]

us two partial trees at the second level search. Further expansion is generated based
on non-terminals given in grammar.

37 | P a g e
 MODULE 2 NLP [BAI601]

Example 2: "The cat sleeps on the mat"

38 | P a g e
 MODULE 2 NLP [BAI601]

2.7.2 Bottom-up Parsing

A bottom-up parser starts with the words in the input sentence and attempts to
construct a parse tree in an upward direction towards the root. At each step, the
parser looks for rules in the grammar where the right-hand side matches some of
the portions in the parse tree constructed so far, and reduces it using the left hand
side of the production. The parse is considered successful if the parser reduces the
tree to the start symbol of the grammar.
Example 1: The bottom-up parsing for the sentence “Paint the Door” is given
below:

39 | P a g e
 MODULE 2 NLP [BAI601]

The complete parsing for the sentence:

Example 2: "the cat chased the dog"

40 | P a g e
 MODULE 2 NLP [BAI601]

Each of these parsing strategies has its advantages and disadvantages.

• As the top-down search starts generating trees with the start symbol of
grammar, it never wastes time exploring a tree leading to a different root.
• However, it wastes considerable time exploring S trees that eventually
result in words that are inconsistent with the input. This is because a top-
down parser generates trees before seeing the input.
• On the other hand, a bottom-up parser never explores a tree that does not
match the input.
• However, it wastes time generating trees that have no chance of leading to
an S-rooted tree. (The left branch of the search space in example 1, that
explores a sub-tree assuming paint as a noun, is an example of wasted
effort.)

REVIEW QUESTIONS

1. What is the main difference between top-down and bottom-up parsing?

2. Which parsing approach constructs the parse tree from leaves to root?
3. Name one advantage of bottom-up parsing over top-down parsing.
4. Which parsing method is more predictive in nature — top-down or bottom-
up?

41 | P a g e
 MODULE 2 NLP [BAI601]

____________________LECTURE 15______________________

2.7.3 CYK Parsing

The CYK (Cocke-Younger-Kasami) is a dynamic programming parsing
algorithm. However, it follows a bottom-up approach in parsing. It builds a parse
tree incrementally. Each entry in the table is based on previous entries. The process
is iterated until the entire sentence has been parsed. The CYK parsing algorithm
assumes the grammar to be in Chomsky normal form (CNF). A CFG is in CNF if
all the rules are of only two forms:

A → BC
A → w, where w is a word.
The algorithm first builds parse trees of length one by considering all rules which
could produce words in the sentence being parsed. Then, it constructs the most
probable parse for all the constituents of length two. The parse of shorter
constituents constructed in earlier iterations can be used in constructing the parse
of longer constituents.
The steps involved in algorithm are shown below:
_________________________________________________________________

for i := 1 to n do
for all rules A → wᵢ do
chart[i,1] = {A}

for j := 2 to n do
for i := 1 to n - j + 1 do
begin
chart[i,j] = ϕ
for k := 1 to j - 1 do
chart[i,j] := chart[i,j] ∪ {A | A → BC is a production and
B ∈ chart[i,k] and
C ∈ chart[i+k, j-k]}
End

if S ∈ chart[1,n] then accept else reject

_________________________________________________________________

42 | P a g e
 MODULE 2 NLP [BAI601]

Example: Tabulate the sequence of states created by CYK algorithm while parsing
“the flight includes a meal”.

Consider the following simplified grammar in CNF:

S → NP VP
NP → Det N
VP → V NP
V → includes
Det → the
Det → a
N → meal
N → flight

For filling the CYK table for the sentence: "the flight includes a meal", the
words - ["the", "flight", "includes", "a", "meal"]
are indexed from 1 to 5.
0 the 1 flight 2 includes 3 a 4 meal 5

43 | P a g e
 MODULE 2 NLP [BAI601]

For each pair (i, j) such that j - i + 1 = 2, we combine possible constituents:

Cell [1,2] (the flight)
• [1,1] = Det
• [2,2] = N
• Check rule: NP → Det N
So, chart[1][2] = NP

Cell [2,3] (flight includes)

• N + V → No matching rule

Cell [3,4] (includes a)

• V + Det → No matching rule

Cell [4,5] (a meal)

• Det + N → NP
So, chart[4][5] = NP

44 | P a g e
 MODULE 2 NLP [BAI601]

Updated table:

Cell [2,4] (flight includes a)

Try:
• [2,2] N + [3,4] V/Det → No match
So chart[2][4] = ∅

Cell [3,5] (includes a meal)

• [3,3] = V, [4,5] = NP
• Check: VP → V NP
So, chart[3][5] = VP

Cell [1,3] (the flight includes)

• [1,2] = NP, [3,3] = V
• NP + V → No match

Cell [2,5] (flight includes a meal)

• [3,5] = VP, [2,2] = N
• No applicable rule

Cell [1,5] (whole sentence)

• [1,2] = NP
• [3,5] = VP
• Check: S → NP VP
So chart[1][5] = S

45 | P a g e
 MODULE 2 NLP [BAI601]

Final Table:

REVIEW QUESTIONS

1. What is the required form of grammar for applying the CYK algorithm?
2. Is CYK parsing a top-down or bottom-up approach?
3. What data structure is primarily used in CYK parsing?
4. What is the time complexity of the CYK algorithm?

46 | P a g e