Module-2

Word Level Analysis

Syntactic Analysis
 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.
 Introduction
• NLP carried out at word level, including characterizing word
sequences, identifying morphological variants, detecting
and correcting misspelled words, and identifying correct
part-of-speech of a word.
• Regular expressions are a beautiful means for describing
words. Regular expressions are used for describing text
strings.
• Finite state transducers, have found useful applications in
speech recognition and synthesis, spell checking, and
information extraction.
• Errors in typing and spelling are common in text
processing.
• An interactive facility to correct errors, Identifying word
with different meanings depending on the context.
 REGULAR EXPRESSIONS (regexes)
• Regular expressions, are a pattern-matching standard for string
parsing and replacement.
• Regular expressions can be used to parse dates, URLs and email
addresses, log files, configuration files, command line switches, or
programming scripts.
• They are useful tools for the design of language compilers and have
been used in NLP for tokenization, describing lexicons, morphological
analysis, etc.
• A simplified forms of regular expressions are used, such as the file
search patterns used by MS DOS, e.g., dir*.txt. The use of regular
expressions made popular 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 originally studied by Kleene (1956).
• RE is an algebraic formula consisting of Pattern, set of strings.
 REGULAR EXPRESSIONS (regexes)
• Regular expression is a sequence of simple characters; putting
characters in sequence is called concatenation.
• Using /…../ to search single to sequence of characters from the data.
• Regular expressions are case sensitive.

• The string of characters inside the braces specifies a disjunction of

characters to match.
• The pattern /[wW]/ matches patterns containing either w or W. This
/[1234567890]/ specifies any single digit.
 REGULAR EXPRESSIONS (regexes)
• The brackets can be used with the dash (-) to specify any one character in a
range. The pattern /[2-5]/ specifies any one of the characters 2, 3, 4, or 5.

• The caret ^ is the first symbol after the open square brace [, the resulting
pattern is negated. The pattern /[^a]/ matches any single character except a.
• The caret ^ has three uses: to match the start of a line, to indicate a negation
inside of square brackets, and just to mean a caret

• The question mark /?/, which means “the preceding character or nothing”
 REGULAR EXPRESSIONS
• The set of operators that allows us to say things like “some
number of a’s” are based on the asterisk or *, commonly called
the Kleene *.
• /b*/ =>Match any string containing zero or more occurrences of
b. such as ‘b’, ’bb’ or ‘ bbb’ etc.
• /[ab]*/ => zero or more occurrence of “a”s or “b”s. This will
match strings: ‘aa’ ,’bb’ or ‘abab’
• + => Specifies one or more occurrences of a preceding
character. + is called as Kleene +.
• /a+/ => one or more occurrences of ‘a’.
• Special character is the period (/./), a wildcard expression that
matches any single character. The wildcard expression /./
matches any single character. The regular expression /.at/
matches with any of the string cat, bat, rat, gat, kat, mat, etc.
• \b matches a word boundary, and \B matches a non word-boundary.
• The dollar sign, $, is an anchor that is used to specify a match at the end of the
line. /The dog\.$/ matches a line that contains only the phrase The dog.

• disjunction operator, also called the pipe symbol |

• /cat|dog/ matches either the string cat or the string dog.
• Apply the disjunction operator to a specific pattern, we need to enclose it
within parentheses. The parenthesis operator makes it possible to treat the
enclosed pattern as a single character for the purposes of neighbouring
operators.
Example: Suppose we need to check if a string is an email address
or not. An email address consist of a non-empty sequence of
characters followed by the 'at' symbol, @, followed by another
non-empty sequence of characters ending with pattern like .xx,
xxx, xxxx, etc. The regular expression for an email address is

^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}$

^[A-Za-z0-9_\-]*+@[A-Za-z0-9_\-]++[A-Za-z0-9_][A-Za-z0-9_]$
• Given example may not be accurate enough to match
all correct email addresses. It may accept non-working
email addresses and reject working ones. Fine-tuning
is required for accurate characterization.
• A regular expression characterizes a particular kind of
formal language, called a regular language.
• The language of regular expressions is similar to
formulas of Boolean logic. Like logic formulas, regular
expressions represent sets.
• Regular language is set of strings described by the
regular expression. Regular languages may be encoded
as finite state networks.
• A regular expression may contain symbol pairs. For example, the
regular expression (relation) /a:b/ represents a pair of string.

• A regular relation may be viewed as a mapping between two regular

languages. The a:b relation is simply the cross product of the
languages denoted by the expressions /a/ and /b/.

• The first symbol, a, can be called the upper symbol and the second
symbol, b, the lower symbol. The two components of a symbol pair
are separated by a colon (:) without any whitespace before or after.
For /a:a/ simply as /a/.

• It possible to encode regular languages using finite-state automata,

leading to easier manipulation of context free and other complex
languages.

• Regular relations can be represented using finite-state transducers.

 FINITE-STATE AUTOMATA
• Ludo/Monopoly/Snake and ladders-Game
• There is no skill or choice involved. The entire game is based on the
values of the random numbers.
• Consider all possible positions of the pieces on the board and call
them states. The state in which the game begins is termed the initial
state, and the state corresponding to the winning positions is termed
the final state.
• Game starts with the initial state, as the game progress pieces
changes from one state to another based on the value of the random
number.
• For each possible number, there is one and only one resulting state
given the input of the number and the current state. This continues
until one player wins (final state).
 FINITE-STATE AUTOMATA
• A simple machine with an input device, a processor, some memory, and
an output device.

• The machine starts in the initial state. It checks the input and goes to
next state, which is completely determined by the prior state and the
input. If all goes well, the machine reaches final state and terminates.

• If the machine gets an input for which the next state is not specified,
and it gets stuck at a non-final state, we say the machine has failed.

• A general model of this type of machine is called a finite automaton;

"finite' because the number of states and the alphabet of input symbols
in finite; 'automaton' because the machine moves automatically, i.e.,
the change of state is completely governed by the input.
 FINITE-STATE AUTOMATA
• This type of machine is more commonly called
deterministic.
• A finite automaton has the following properties:
1. A finite set of states, one of which is designated the initial or
start state, and one or more of which are designated as the
final states.
2. A finite alphabet set, Σ, consisting of input symbols.
3. A finite set of transitions that specify for each state and each
symbol of the input alphabet, the state to which it next goes.

• 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 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. 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.
• Finite-state automata have been used in a wide variety of areas,
including linguistics, electrical engineering, computer science,
mathematics, and logic.

• The regular expression can be represented by a finite automaton and

the language of any finite automaton can be described by a regular
expression.

• The deterministic and non-deterministic finite automaton, are taken

from Hopcroft and Ullman (1979).

• A deterministic finite-state automaton (DFA) is defined as a 5-tuple

(Q, Σ, δ, S, F), where Q is a set of states, Σ is an alphabet, S is the
start state, F ⃀ Q is a set of final states, and δ is a transition function.

• The transition function δ defines mapping from Q X Σ to Q. That is,

for each state q and symbol a.
• Unlike DFA, the transition function of a non-deterministic finite-
state automaton (NFA) maps Q X (Σ U (ε)) 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 state.

• There are two possible transitions from state q0 on input symbol a.

• 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.
• Consider the deterministic automaton with 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.

• For an input acb, 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 list of transition rules can be quite long. So we represent an
automaton 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 language consisting of all strings containing only as and bs and
ending with baa.
• The regular expression /(a|b) baa$/.
• The NFA implementing this regular expression;

State transition table for the NFA

• Two automata that define the same language are said to be equivalent. An NFA
can be converted to an equivalent DFA and vice versa.
 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.
• 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 2 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 prefix, suffix, infix, and circumfix.
 MORPHOLOGICAL PARSING
• 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.
• Prefixes and suffixes are quite common in Hindi, English…
• A word unhappy, is composed of the stem, happy, and the prefix, un-.
The English word, birds, is composed of the stem, bird, and the suffix,
s.
• The Hindi word, शीतलता is composed of a stem शीतल and the suffix
- ता.
• Telgu word గుర్రములు (gurramulu-plural form of gurramu, mearning
horse) is composed of the stem గుర్రము (gurramu) and suffix -లు (lu).
 Examples for Affixes
• Prefix-morphemes which appear before a stem
• Unhappy
• अपमान,संसार उपवन (Hindi), Suffix-morphemes applied to the end of the stem.
• ಅತೃಪ್ತಿ(Atripti)(Kannada) • trees, birds
• ಮರಗಳು,(upayōgisu)
• शीतलता

• Infix-morphemes that appear inside the stem.

• Common in Austronesian and Austroasiatic languages (Tagalog-
• -philippines, Khmer-cambodia)
• Kayu- ‘wood’=> kayu-in- => ‘kinayu’(gathered wood)
• basa-‘read’=>b·um·asa-‘readpast’
• sulat-‘write’=>s·um·ulat-‘wrote’
• Circumfix-morphemes applied to either end of the stem.
• in-correct-ly
• im-matur-ity
• un-bear-able
• re-cover-ed
• Suffixes are more common than prefixes which are more common than infixes
and circumfixes.
• There are three main ways of word formation: inflection, derivation, and
compounding. Morphological analysis and generation deal with these types.
• 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 nominalization.
• Compounding is the process of merging two or more words to form a new
word. For example, personal computer, desktop, overlook.
• Morphological analysis and generation are essential to many NLP
applications ranging from spelling corrections to machine translations.
• In information retrieval, morphological analysis helps identify the
presence of a query word in a document in spite of different
morphological variants.
• Parsing is taking a surface input and analysing its components and
underlying structure.
• 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 a set of tags showing its syntactical category
and morphological characteristics, e.g., possible part of speech and/or
inflectional properties (gender, number, person, tense, etc.).
• Example:
Goose -> goose +N +SG
Geese -> goose +N +PL
Gooses -> goose +V+3SG
• Morphological analysis and generation rely on 2 sources of
information: a dictionary of the valid lemmas of the
language and a set of inflection paradigms.
• A morphological parser uses following information
sources:
1. Lexicon: A lexicon lists stems and affixes together with
basic information about them.
2. Morphotactics: There exists certain ordering among the
morphemes that constitute a word. For example, rest-
less-ness is a valid word in English but not rest-ness-less.
Morphotactics deals with the ordering of morphemes. It
describes the way morphemes are arranged or touch
each other.
3. Orthographic rules: These are spelling rules that specify
the changes that occur when two given morphemes
combine. For example, the y→ier spelling rule changes
'easy' to 'easier’ and not to ‘easyer’.
• Morphological analysis can be avoided if an exhaustive lexicon is available that lists
features for all the word-forms of all the roots. For example, suppose an
exhaustive lexicon for Hindi contains the following entries for the Hindi root-word
ghodhaa.

• This approach has several limitations. First, it puts a heavy demand on memory.
We have to list every form of the word, which results in a large number of, often
redundant, entries in the lexicon.

• Second, an exhaustive lexicon fails to show the relationship between different

roots having similar word-forms. This fails to capture linguistic generalization,
which is essential to develop a system capable of understanding unknown words.

• Third, for morphologically complex languages, like Turkish, the number of possible
word-forms may be theoretically infinite. It is not practical to list all possible word-
forms in these languages.
• The simplest morphological systems are stemmers that collapse
morphological variations of a given word to one lemma or stem.
• Stemmers have been especially used in information retrieval.
• Two widely used stemming algorithms, developed by Lovins (1968) and
Porter (1980).
• Stemmers do not use a lexicon; instead, they make use of rewrite rules
of the form:
ier → y (e.g., earlier → early)
ing → φ (e.g., playing → play)
Stemming algorithms work in two steps:
i. Suffix removal: This step removes predefined endings from words.
ii. Recoding: This step adds predefined endings to the output of the first step.

• For example, Porter's stemmer makes use of the following

transformation rule: ational → ate
• To transform word such as 'rotational' into 'rotate'.
• It is difficult to use stemming with morphologically rich languages. Even in
English, stemmers are not perfect.

• Krovitz (1993) pointed out errors of omissions and commissions in the Porter
algorithm, such as transformation of the word 'organization' into 'organ' and
'noise' into 'noisy'. Another problem with Porter's algorithm is that it reduces
only suffixes; prefixes and compounds are not reduced.

• A more efficient two-level morphological model, first proposed by Koskenniemi

(1983), can be used for highly inflected languages. In this model, a word is
represented as a correspondence between its lexical level form and its surface
level form. The surface level represents the actual spelling of the word while
the lexical level represents the concatenation of its constituent morphemes.

• For example, the surface form 'playing' is represented in the lexical form as play
+V +PP. The lexical form consists of the stem 'play' followed by the
morphological information +V +PP, which tells us that 'playing' is the present
participle form of the verb.
• The surface form 'books' is represented in the lexical form as 'book + N
+ PL', where the first component is the stem and the second
component (N + PL) is the morphological information(plural noun).
• This model is usually implemented with a kind of finite-state
automata, called finite-state transducer (FST).
• A finite state transducer does this through a finite state automaton. An
FST can be thought of as a two-state automaton, which recognizes or
generates a pair of strings.
• FST passes over the input string by consuming the input symbols on
the tape it traverses and consists it to the output string in the form of
symbols.
• A FST has been defined by Hopcroft and Ullman (1979) as follows: A
finite-state transducer is a 6-tuple (Σ₁, Σ₂, Q, δ, S, F), where θ is set of
states, S is the initial state, and F ⃀ Q is a set of final states, Σ₁ is input
alphabet, Σ₂ is output alphabet, and δ is a function mapping Q x (Σ₁ U
(ε)) X (Σ₂ U (ε)) to a subset of the power set of Q.
• Transducers can be seen as automata with transitions labelled
with symbols from Σ₁ X Σ₂, where Σ₁ and Σ₂ are the alphabets of
input and output respectively.

• The FST is similar to an NFA except in that transitions are made

on strings rather than on symbols and, in addition, they have
outputs.

• A simple transducer that accepts two input strings, hot and cat,
and maps them onto cot and bat respectively. It is a common
practice to represent a pair like a:a by a single letter.
• Just as FSAs encode regular languages, FSTs encode regular
relations. Regular relation is the relation between regular
languages.
• The regular language encoded on the upper side of an FST is
called upper language and the one on the lower side is termed
lower language.
• If T is a transducer, and s is a string, then we use T(s) to
represent the set of strings encoded by T such that the pair (s,
t) is in the relation.
• The FSTs are closed under union concatenation, composition,
and Kleene closure.
• The two-level morphology using FST. To get from the surface
form of a word to its morphological analysis.
• Split the words up into its possible components (bird + s out of
birds), where + indicates morpheme boundaries.
• There are two possible ways of splitting up boxes, namely boxe +
s [Stem + suffix] and box + s. The second assumes that box the
stem is and that e has been introduced due to the spelling rule.
• The output of this step is a concatenation of morphemes, i.e.,
stems and affixes.
• There can be more than one representation for a given word.
• A transducer that does the mapping (translation) required by this step
for the surface form 'lesser’.
• This FST represents the information that the comparative form of the
adjective less is lesser, ε here is the empty string.
• The automaton is inherently bi-directional: the same transducer can
be used for analysis or for generation.

• In the second step, we use a lexicon to look up categories of the stems

and meaning of the affixes. So, bird + s will be mapped to bird+ N+ PL,
and box + s to box+ N + PL.
• We also find out now that boxe is not a legal stem. This tells us that
splitting boxes into boxe + s is an incorrect way of splitting boxes, and
should therefore be discarded.
• Orthographic rules are used to handle these spelling variations. For
instance, one of the spelling rules says add e after s, z, x, ch, sh before
the s (e.g., dish -> dishes, box -> boxes).
• The steps are implemented by the transducer. we need to build
two transducers: one that maps the surface form to the
intermediate form and another that maps the intermediate form
to the lexical form.
• FST-based morphological parser for singular and plural nouns in
English. The plural form of regular nouns usually end with-s or -
es.
• A word ending in 's' need not necessarily be the plural form of a
word (e.g., miss)
• One of the required translations is the deletion of the 'e' when
introducing a morpheme boundary, for words ending in xes, ses,
zes (e.g., suffixes and boxes).
• Develop a transducer for step 2 (mapping from the intermediate level
to the lexical level).
• The input to transducer has one of the following forms: Regular noun
stem + s, e.g., bird + s. Singular irregular noun stem, e.g., goose. Plural
irregular noun stem, e.g., geese.
• As in the fig.[1,2,5,9], the transducer has to map all symbols of the
stem to themselves and then output N and sg. In the path [1,2,5,8,9], it
has to map all symbols of the stem to themselves, but then output
Nand replaces PL with s. In the path [1,3,6,9], it has to do the same as
in the first case. In the path [1,4,7,9], the transducer has to map the
irregular plural noun stem to the corresponding singular stem.
• The mapping from State to State is carried out with the help of a transducer
encoding a lexicon.
• This lexicon maps the surface form geese, which is an irregular noun, to its
correct stem goose like; g:g e:o e:o s:s e:e
• Two representations are reduced to g e:o e:o s e and b i r d respectively.
• The plural nouns into the stem plus the morphological marker + pl and
singular nouns into the stem plus the morpheme + sg. Thus, a surface word
form birds will be mapped to bird + N + pl.
• ε maps to morphological feature +N, and s maps to morphological feature pl.
• The power of the transducer lies in the fact that the same transducer can be
used for analysis and generation.
 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 and identified a single
character omission, insertion, substitution, and reversal are the most
common typing mistakes.
• 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 misspelled 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/Transposition refers to a situation in which the sequence of
characters is reversed, e.g., 'aer' instead of 'are’.
• 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.
• OCR substitution errors are caused due to visual similarity such as
c→e, 1→l, 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 particular device. These errors can be corrected
using 'context' or by using linguistic structures.
• Speech recognition, will deal with strings of phonemes, and attempt to
match a spoken utterance with a dictionary of known utterances. The
misspell word is pronounced in the same way as the correct word.
• Phonetic errors are distorting the word by more than a single
insertion, deletion, or substitution. Phonetic variations are common in
transliteration.
• 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 a given lexicon
or is not a valid orthographic word form, it is termed a non-word error.
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. Real-word errors may cause local syntactic errors,
global syntactic errors, semantic errors, or errors at discourse or
pragmatic levels.
• 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.
• These sub-problems are addressed in two ways:
1. Isolated-error detection and correction

2. Context-dependent error detection and correction

• In isolated-word error detection and correction, each word is checked

separately, independent of its context.

• There are a number of problems associated with this simple strategy.

✓ The strategy requires the existence of a lexicon containing all correct words. Such
a lexicon would take a long time to compile and occupy a lot of space.

✓ Some languages are highly productive. It is impossible to list all the correct words
of such languages.

✓ This strategy fails when spelling error produces a word that belongs to the lexicon,
e.g., when 'theses' is written in place of 'these'. Such an error is called a real-word
error.

✓ The larger the lexicon, the more likely it is that an error goes undetected, because
the chance of a word being found is greater in a large lexicon.
• These sub-problems are addressed in two ways:
1. Isolated-error detection and correction
2. Context-dependent error detection and correction

• Context dependent error detection and correction methods,

utilize the context of a word to detect and correct errors.

• This requires grammatical analysis and is thus more complex and

language dependent. Even in context dependent methods, the
list of candidate words must first be obtained using an isolated-
word method before making a selection depending on the
context.

• The spelling correction algorithm has been broadly categorized

by Kukich (1992).
 Spelling Correction Algorithms
• Minimum edit distance: It is a distance between 2 strings is the minimum number of
operations (insertions, deletions, or substitutions) required to transform one string
into another.

• 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 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. This information can be used to handle non-word
error. 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.

• Neural nets: These have the ability to do associative recall based on incomplete and
noisy data. They can be trained to adapt to specific spelling error patterns. This is
computationally expensive.

• Rule-based techniques: 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.
 Minimum edit distance
• The minimum edit distance between 'tutor' and 'tumour' is 2: We
substitute 'm' for 't' and insert 'u' before 'r'. No smaller edit sequence
can be found for this conversion.
• Edit distance between two strings can be represented as a binary
function (ed), which maps two strings to their edit distance, ed is
symmetric. For any two strings, s and t, ed(s, t) is always equal to ed(t, s).
• 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.
t u t o - r
t u m o u r
• A dash in the upper string indicates insertion. A substitution occurs when
the two alignment symbols do not match (shown in bold).
• The Levensthein distance between two sequences is obtained by
assigning a unit cost to each operation. Another possible
alignment for this sequences is:
t u t - o - r
t u - m o u r
which has a cost of 3. We have a better alignment than this one.
• Dynamic programming algorithms can 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 solve problems by combining solutions to
sub-problems, 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.
 Another example

• Transformation of string “vintner” to “writers” and its

associated edit transcript (RIMDMDMMI).
• Minimum Edit Distance=5

* R-Replace, I-Insertion, D-Deletion

• The value in each cell is computed in terms of three possible paths.
• The substitution will be 0 if the ith character in the source matches with jth
character in the target.

• Minimum edit distance algorithms are also useful for determining accuracy in
speech recognition systems. Kemal Oflazer (1996) proposed an efficient
algorithm based on spelling correction with finite-state automata.
 WORDS AND WORD CLASSES
• Words are classified into categories called part-of-speech. These are
sometimes called word classes or lexical categories.
• Lexical categories are defined by their syntactic and morphological behaviours.
• The most common lexical categories are nouns and verbs. Other lexical
categories include adjectives, adverbs, prepositions, and conjunctions.
• Lexical categories and their properties vary from language to language. Word
classes are further categorized as open and closed word classes.
• Open word classes constantly acquire new members while closed word classes
do not. Nouns, verbs, adjectives, adverbs, and interjections are open word
classes. Prepositions, auxiliary verbs, delimiters, conjunction, and particles are
closed word classes.
 PART-OF-SPEECH TAGGING
• Part-of-speech tagging is the process of assigning a part-of-speech to
each word in a sentence.
• The input to a tagging algorithm is the sequence of words of a natural
language sentence and specified tag sets. The output is a single best
part-of-speech tag for each word.
• Many words may belong to more than one lexical category. 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’. In Hindi, a
word 'sona’ may mean 'gold' (noun) or 'sleep' (verb).
• To determine the correct lexical category of a word in its context. 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.
• For example, both eat and eats might be tagged as a verb in one
tag set, but assigned distinct tags in another tag set. Most tag
sets capture morpho-syntactic 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.
• Eat is the base form, ate its past tense, and the form eats
requires a third person singular subject. Similarly, eaten is the
past participle form and cannot occur in another grammatical
context. It is required after have or has.
• The following sentences are ungrammatical:
I like to eats guava.
They eaten all the apples.
• The number of tags used by different taggers varies substantially.
• Penn Treebank tag set contains 45 tags while C7 uses 164. For
English, which is not morphologically rich, the C7 tagset is too
big. The Penn Treebank tag set captures finer distinctions by
assigning distinct tags to distinct grammatical forms of a verb.
• The tagging process would yield too many mistagged words and
the result would have to be manually corrected.
• TOSCA-ICE for the International Corpus of English with 270 tags
(Garside 1997), or TESS with 200 tags.
• The larger the tag set, the greater the information captured
about a linguistic context. A bigger tag set for a morphologically
rich languages, uses without having too many tagging errors.
• The coarse-grained distinction may be appropriate for some
tasks, a fine-grained tag set captures more information.
• This is useful for tasks like syntactic pattern detection.
 Tags from Penn
Treebank tag set

Here is an example of a tagged sentence:

Speech/NN sounds/NNS were/VBD sampled/VBN by/IN a/DT microphone/NN.
Another tagging possible for this sentence is as follows:
Speech/NN sounds/VBZ were/VBD sampled/VBN by/IN a/DT microphone/NN.
The second tagged sequence is not correct, and it leads to semantic
incoherence.

Possible tags for

the word eat
• The Part-of-speech tagging is an early stage of text processing in many NLP
applications including speech synthesis, machine translation, information retrieval,
and information extraction.

• In information retrieval, part-of-speech tagging can be used for indexing (for

identifying useful tokens like nouns and phrases) and for disambiguating word
senses.

• Part-of-speech tagging methods fall under the three general categories.

1. Rule-based (linguistic): Rule-based taggers use hand-coded rules to assign tags to
words. These rules use a lexicon to obtain a list of candidate tags and then use rules
to discard incorrect tags.
2. Stochastic (data-driven): 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. Hidden Markov model (HMM) is the standard Stochastic
tagger. CLAWS (constituent likelihood automatic word-tagging system).
3. Hybrid: Hybrid taggers combine features of both these approaches. Like rule based
systems, they use rules to specify tags. 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.
 1. Rule-based Tagger
• Most 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.

• For example, consider the noun-verb ambiguity in the

sentence: The show must go on.

• The potential tags for the word show in this sentence is {VB,
NN}. We resolve this ambiguity by using the following 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.

• An 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. This process
may be repeated several times.

• Speed is an advantage of the rule-based tagger, they are deterministic.

In this system, time is spent in writing a rule-set. Another disadvantage
of the rule-based tagger is that it is usable for only one language.
 2. Stochastic Tagger
• The standard stochastic tagger algorithm is the 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 unigram model, were each token tagged and that 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.
For example, it will assign the tag JJ for each occurrence of fast, since
fast is used as an adjective more frequently than it is used as a noun,
verb, or adverb. This results in incorrect tagging in each of the
following sentences:
She had a fast (used as noun).
Those who were injured in the accident need to be helped fast (used as
adverb).
• For stochastic taggers, time is spent developing restrictions on
transitions and emissions to improve tagger performance.
• The accurate predictions can expect, if we took more context into
account when making a tagging decision.
• A bi-gram tagger uses the current word and the tag of the previous
word in the tagging process.
• The tag sequence "DT NN" is more likely than the tag sequence "DT JJ”.
• The n-gram model considers the current word and the tag of the
previous (n-1) words in assigning a tag to a word.
• The area shaded in grey represents the context.

Context used by a tri-gram tagger

• The objective of a tagger is to assign a tag sequence to a given sentence.

• The HMM tagger assigns the most likely tag sequence to a given sentence. It
uses two layers of states: a visible layer corresponding to the input words, and
a hidden layer learnt by the system corresponding to the tags.

• While tagging the input data, the words the tags (states) are hidden. States of
the model are visible in training, not during the tagging task.

• The HMM makes use of lexical and bi-gram probabilities estimated over a
tagged training corpus in order to compute the most likely tag sequence for
each sentence.

• To store the statistical information is to build a probability matrix. The

probability matrix contains both the probability that an individual word
belongs to a word class as well as the n-gram analysis,

• For example; in a bi-gram model, the probability that a word of class X follows
a word of class Y. This matrix is then used to drive the HMM tagger while
tagging an unknown text.
 Tagging a Sentence in Stochastic
• Input: Sequence of words (Sentence)
• Objective: 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., Tl=argmaxT P(T|W)

• P(W|T) → Probability of seeing a word sequence, given a tag sequence.

• Example: Probability of seeing; ‘The tomato is rotten’ given ‘DT NN VB JJ’
• Assumptions:
• The words are independent of each other.
• The probability of a word is dependent only on its tag
• Stochastic models have the advantage of being accurate and language
independent.

• The drawbacks of stochastic taggers is that they require a manually tagged

corpus for training.

• A tagger trained on a hand-coded corpus performs better than one trained on

an unannotated text. In order to achieve good performance a tagged corpus is
required.

• An example demonstrating how the probability of a particular part-of-speech

sequence for a given sentence can be computed. Consider the sentence: The
bird can fly and the tag sequence,
 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 and rules are automatically induced from the data.
• Transformation-based learning (TBL) of tags, also known as Brill
tagging, and introduced by E. Brill (in 1995). TBL is also a supervised
learning technique.
• Transformation-based error-driven
learning has been applied part-of-
speech tagging, speech generation, and
syntactic parsing.
• The input to Brill's TBL tagging
algorithm is a tagged corpus and a
lexicon. The initial state annotator uses
the lexicon to assign the most likely tag
to each word as the start state.
The process is iterated until some stopping criterion is reached. The
output of the algorithm is a ranked list of learned transformation that
transform the initial tagging close to the correct tagging.
• Each transformation is a pair of a re-write rule of the form t1→t2
and a contextual condition.

• Any allowable transformation is an instantiation of these

templates. Some of the transformation templates and
transformations learned by TBL tagging are listed in below;
• How the rules are applied in TBL tagger with the help of an
example. Assume that in a corpus, fish is most likely to be a noun.
P(NN/fish) = 0.91
P(VB/fish) = 0.09
• Now consider the following two sentences and their initial tags.
I/PRP like/VB to/TO eat/VB fish/NNP.
I/PRP like/VB to/TO fish/NNP.
• As the most likely tag for fish is NNP, the tagger assigns this tag to
the word in both sentences. In the second case, it is a mistake.
• After initial tagging when the transformation rules are applied, the
tagger learns a rule that applies exactly to this mis-tagging of fish:
Change NNP to VB if the previous tag is TO.
• As the contextual condition is satisfied, after the rule: like/VB
to/TO fish/NN→ like/VB to/TO fish/VB
• The algorithm can be made more efficient by indexing the words in a
training corpus using potential transformation. The use of finite state
transducers to compile pattern-action rules, combining them to yield a
single transducer representing the simultaneous application of all rules.
• Most of the work in part-of-speech tagging is done for English and
some European languages. In other languages, part-of-speech tagging,
and NLP research in general, is constrained by the lack of annotated
corpuses.
• A Bengali tagger based on HMM developed by Sandipan et al. (2004)
and a Hindi tagger developed by Smriti et al. (2006), used a decision
tree-based learning algorithm.
• POS tagging is an early stage of text processing in NLP applications:
• Speech synthesis
• Machine Translation
• Information Retrieval
• Information Extraction
 Syntactic Analysis-Introduction
• Word “syntax” refers to the grammatical arrangements of words in a sentence
and relationships with each other.
• Objective: To find syntactic structure of sentence.
• Structure represented as tree.
• Nodes in the tree represented as phrases and leaves as words
• Root of the tree is a whole sentence.

• Identification of syntactic structure is

done by parsing
• Syntactic analysis (Syntactic parsing)
also considered as ‘phrase markers’ to a
sentence
• Words are brought together to form
larger groups termed constituents or
phrases, which can be modelled using
context-free grammar.
 Context-Free Grammar (CFG)
• CFG is first defined for natural language by Chomsky(1957). Used for
algol programming language by Backus(1959)and Naur(1960).
• CFG also called as phrase-structure grammar.
• Context-free grammar is a set of rules or productions that tell which
elements can occur in a phrase and in what order.
• Consists of 4 components:
• A set of nonterminal symbols, N
• A set of terminal symbols, T
• A designated start symbol, S, one of the symbol from N
• 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.
• Example: S→NP VP, states that S consists of NP followed by VP, i.e., a
sentence consist of a noun phrase followed by a verb phrase.
• A language is defined through the concept of derivation
• Basic operation is of rewriting the symbol appearing on the left hand
side of production by its right hand side.
• Which can be represented using parse tree
• Parse tree represents mapping of a string to its parse tree
• Example: Consider the toy grammar sample parse tree

• We can also represent

compact bracketed notation
to represent a parse tree.
• The parse tree in a figure
above can be represented
using following notation:
[S [ NP [N Hena] ] [VP [V reads] [NP [Det a] [N book] ] ] ]
 Constituency
• Words group together to form larger constituents (phrases) and
eventually a sentence.
• Example: The bird, The rain, The Wimbledon court, The beautiful
garden → Noun phrases
• These constituents combine with others to form sentence constituent.
• Example: The bird, can combine with verb phrase, flies, to form
sentence “The bird flies”
Phrase Level Constructions:
• In natural language certain group of words behave as constituents.
• Constituents decide whether a group of words is a phrase, if it can be
substituted with some other group of words without changing the
meaning.
• If substitution is possible then the set of words forms a phrase.
• This is called the substitution test
 Phrase Level Constructions

Example: We can substitute number of phrases like:

Hena reads a book.
Hena reads a story book.
Those girls read a book
She reads a comic book
• Constituents are: Hena, She and Those girls, and a book, a story book and a
comic book. These forms phrase.
• Phrase types are defined after their head, which is lexical category that
determines properties of the phrase.
• If the head is noun, phrase is noun phrase. If head is verb then phrase is verb
phrase
• Example: A sentence with NP, VP, PP
 Noun Phrase
• Phrase whose head is a noun or pronoun
• Modifiers of a noun phrase can be determiners or adjective
phrases
• These structures can be represented using phrase structure rule as
below:
• Here,() represents optional
• That is, Noun possibly preceded by determiner and an adjective.
 Noun Phrase
• Noun phrase may include post modifiers more than one adjective.
• It may include Prepositional Phrase(PP).
• After incorporating rule: NP → (Det) (AP) Noun (PP)
• Examples: Noun phrases:

• A Noun sequence is termed as: nominal

• To handle the nominal we can write phrase structure rule as below:
• NP → (Det) (AP) Nom (PP)
• Nom → Noun | Noun Nom
• Noun phrase can act as subject, an object or predicate.
• Examples:
 Verb Phrase
• Headed by verb
• Wide range of phrases can modify a verb→ complex
• Organizes the various elements of the sentence depends on the syntactic
structure.

• In general, number of NP’s limited to two but it is possible to add more than two
PPs.
• Rule will be as follows: VP → Verb (NP) (NP) (PP)*
• Here, objects may also be entire clauses in the sentence like: I know that Taj is
one of the seven wonders.
• So, alternative phrase statement rule, which NP is replaced by S as: VP→ Verb S
 Prepositional Phrase
• Prepositional Phrases (PP) are headed by a preposition.
• They consist of a preposition, possibly followed by some other
constituent, a noun phrase.
• Example: We played volley ball on the beach
• Preposition phrase that consists just a preposition
• Example: John went outside
• Phrase structure rule that captures the above eventualities as
follows:
PP→ Prep (NP)
 Adjective Phrase
• Adjective Phrases (AP) are headed by a adjectives.
• They consist of a adjectives, may be preceded by an adverb and
followed by a PP.
• Examples: Ashish is clever.
The train is very late.
My sister is fond of animals.
• Phrase structure rule as follows: AP → (Adv) Adj (PP)

Adverb Phrase
• Adverb Phrases (AdvP) are consists of adverb.
• Preceded by a degree adverb.
• Example: Time passes very quickly
• Phrase structure rule as follows: AdvP → (Intens) Adv
 Sentence level Constructions
• A sentence can have varying structures
• 4 commonly known structures are: Declarative structure, Imperative
structure, Yes-no question structure, Wh-question structure
• Declarative sentence - subject followed by a predicate (verb gives info
about subject)
• Where, subject is Noun Phrase and predicate is Verb Phrase
• Example: I like horse riding
• Phrase structure rule for declarative sentence as follows: S→ NP VP
• Imperative sentence - begin with verb phrase and lack subject
• Subject is implicit in sentence and understood to be ‘you’.
• These sentences are used for commands and suggestions
• Phrase structure rule for imperative sentence as follows: S → VP
• Examples: Look at the door, Give me the book, Stop talking, Show me
the latest design.
 Sentence level Constructions
• Sentences with 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 VP
• Phrase structure rule for yes-no sentence as follows: S → Aux NP
VP
• Examples: Do you have a red pen? Is there a vacant quarter? Is
the game over? Can you show me your album?
• Sentences with wh-question structure are complex.
• Begin with a wh-words -> who, which, where, what, why and
how
• It may have wh-phrase as a subject or may include another subject
• Rule for Wh-sentence as follows: S → Wh-NP VP
• Example: Which team won the match?
 Sentence level Constructions
• Another type of wh-question involves more than one NP.
• Here, Auxiliary verb comes before the subject NP
• Rule for Wh-questions as follows: S → Wh-NP Aux NP VP
• Example: Which cameras can you show me in your shop?

Summary of grammar rules

 Sentence level Constructions

• Sentence-level structures that cannot be modelled by the rules,

Coordination is one of that
• Conjoining phrases with conjunctions like ‘and’, ‘or’, ‘but’.
• A coordinate noun phrase can consist of two other noun phrases,
separated by a conjunction 'and’.
• Examples: I ate [NP [NP an apple] and [NP a banana]]
• VP can be conjoined as: It is [VP [VP dazzling] and [VP a raining]]
• Sentence can be conjoined as below: [S [S I am reading the book]
and [S I am also watching the movie]]
• Rule for Conjunction as follows: NP → NP and NP, VP → VP
and VP, S → S and S
 Sentence level Constructions
• Agreement
• Most verbs use 2 different forms in present tense - Third person, singular
subjects and other kind of subjects.
• Third person singular (3sg) form ends with –s, Non-3sg does not end with -s
• Whenever there is verb that has noun acting as subject, This agreement is
confirmed.
• Examples: Does [NP Priya] sing?
• Here, subject NP is singular, so -es form of ‘do’, ie. 'does' is used.
• Do[NP they] eat? It has a plural NP subject. Hence, the form 'do' is being used.
• Rules used to handle yes-no questions: S → Aux NP VP
• To take care of subject-verb agreement, were place the above rule as follows:
S → 3sgAux 3sgNP VP
S → Non3sgAux Non3sgNP VP
• Lexicon can be like: 3sg Aux → does|has|can
Non 3sg Aux → do|have|can
 Sentence level Constructions
• Feature Structures: Sets of feature-value pairs
• Used to efficiently capture the properties of grammatical categories.
• Example: Number property of a noun phrase can be represented by NUMBER
feature
• The value of NUMBER feature n can take SG(singular) and PL(plural) Values can
be atomic symbols or feature structures.
• Represented by matrix like diagram called Attribute Value Matrix(AVM)

• AVM consists single NUMBER feature with value SG is represented as below:

[NUMBER SG]
• Value of feature can be left unspecified and represented as below:
[NUMBER [] ]
 Sentence level Constructions
• Feature structure can be used to encode the grammatical category
of a constituent and features associated to it.
• Feature Structures
• Example: Third person singular noun phrase can be represented
as below:

• Example: Third person plural noun phrase can be represented as

below:

• Here, Value of feature CAT and PERSON remain same in both

the structures.
 Sentence level Constructions
• Feature values not only atomic but it can have another feature
structure
• Example: Consider the case of combining the NUMBER and
PERSON features into a single AGREEMENT feature.
• In grammatical sense, grammatical subjects must agree with their
predicates in NUMBER and PERSON properties.
• Using this new feature, grammatical category 3-PL NP by
following structure:
 Sentence level Constructions
• Using Feature structures can perform operations.
• Operations are: Merging the information content of 2 structures
• These computational techniques are called as unification.
• Unification implemented using binary operator - ⵡ
• Advantages: CFG rules can have feature structures to realize on the
constraints of the sentence.
• Example: Performs an equality check
• [NUMBER PL] ⵡ [NUMBER PL]=[NUMBER PL]
• Example: Performs a result as non-null values when unspecified
structure is given
• [NUMBER PL] ⵡ [NUMBER []]=[NUMBER PL]
• Example: result fails as non-null values
• [NUMBER PL] ⵡ [NUMBER SG]=Fails
 Parsing
• CFG defines syntax of language but does not define how structures are
assigned.
• Parsing is a task that uses rewrite rules of a grammar to:
• Generate a particular sequence of words or
• Reconstruct its derivation(Phrase structure tree)
• Syntactic parser recognizes a sentence and assigns syntactic structure
to it.
• Phenomena associated with Syntactic Parsing:
• Syntactic ambiguity
• Garden pathing
• Syntactic ambiguity
• A sentence can have multiple parses.
• Many different phrase structure trees deriving the same sequence of words.
• Garden pathing
• Process of constructing a parse by exploring the parse tree along different
paths, one after the other till, eventually, the right one is found.
• Eg: The horse ran past the barn fell
 Parsing
• In Eg: The horse ran past the barn fell
• In first attempt, come up with the parse corresponding to the
sentence The horse ran past the barn, leaving no possibility for the
word fell to be added incrementally in the sentence.
• Finding the right parse -> Search process
• Search finds all trees: whose root is the start symbol, S and whose
leaves cover exactly the word in the input.
• Constraints that guide the Search Process
1. Input: First constraint comes from words in the input sentence.
Valid parse is one that covers all the words in a sentence. Words
must constitute the leaves of the final parse tree.
2. Grammar Second constraint comes from the grammar. Root of the
final parse tree must be the start symbol of the grammar.
• Constraints give rise to two Search strategies:
• Top-down (Goal-directed search)
• Bottom-up (Data-directed search)
 Top-down Parsing
• Start the search from the root node S and work downwards towards the
leaves
• Assumption: Input can be derived from the designated start symbol, S,
of the grammar.
• Find all subtrees which can start with S. Expand the root node using all
the grammar rules with S on their LHS–Subtrees of the second-level
search.
• Similarly, expand each non-terminal symbol in the resulting sub-trees
using the grammar rules having matching non terminal symbol on their
LHS.
• RHS of the grammar rules provides the nodes to be generated, which
are then expanded recursively.
• The tree grows downward and eventually reaches a state where the
bottom of the tree consists only of POS categories.
• All trees whose leaves do not match words in the input sentence are
rejected, leaving trees representing successful parse.
• A tree which matches exactly with the words in the input sentence –
Successful Parse.
Example: Consider the Sentence: Paint the door and construct
top down parsing.
Consider the following Grammar as below:

S -> NP VP
Noun -> paint | door
S -> VP VP->Verb NP
NP -> Det Nominal VP->Verb
NP -> Noun PP ->Preposition NP
NP -> Pronoun Det->this|that|a|the
Verb->sleeps|sings|open|saw| paint
NP -> Det Noun PP
Preposition->from|with|on|to
Nominal -> Noun
Pronoun->she|he|they
Nominal -> Noun Nominal
 Bottom-up Parsing
• Starts with the words in the input sentence.
• Attempts to construct a parse tree in an upward direction
towards the root.
• Look for rules in the grammar where the RHS matches
some of the portions in the parse tree constructed so far,
reduces it using the LHS of the production.
• Parser reduces the tree to start symbol → Successful
parse.
Example: Consider the Sentence: Paint the door and
construct top down parsing.
Consider the following Grammar as below:

S -> NP VP VP-> Verb NP

VP-> Verb
S -> VP
PP -> Preposition NP
NP -> Det Nominal Det-> this|that|a|the
NP -> Noun Verb-> sleeps|sings|open|saw| paint
NP -> Pronoun Preposition-> from|with|on|to
Pronoun-> she|he|they
NP -> Det Noun PP
Nominal -> Noun
Nominal -> Noun Nominal Noun -> paint | door
 Advantages & Disadvantages
• Top-down
• Never wastes time exploring a tree leading to a different root.
• Wastes considerable time exploring S trees that eventually result
in words that are inconsistent with the input.
• Top-down parser generates trees before seeing the input

• Bottom-up
• Never explores a tree that does not match the input.
• Wastes considerable time generating trees that have no chance of
leading to an S-rooted tree.
 CYK Parser
• Cocke-Younger-Kasami
• Dynamic programming parsing algorithm.
• Follows Bottom-up approach in parsing.
• Builds a parse tree incrementally.
• Each entry in the table is based on previous entries.
• Process is iterated until entire sentence is parsed.
• Assumes the grammar in Chomsky normal Form(CNF)
• A CFG is a 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.
• This is a chart-based algorithm.
 CYK Parser
• The algorithm builds smaller constituents before attempting to construct larger
ones.
• Terminal Derivation rules of the grammar are used to generate the [i,1]th entries.
• These entries represent non terminals that derive the individual words appearing in
the sentence, wi1= wi, for 1≤i≤n, where n is the length (number of words) of the
sentence.
• A=> wi1, if A→ wi is a rule in the grammar.
• This continues with a sub-string of length two, three, and so on. For every non-
terminal A in the grammar, the algorithm determines if A* => wij.
• A could derive if there existed a rule of the form A = B C such that B derives the
first k words of the wij (i.e. B -> wik) and C derives the remaining j-k words (C→
wkj). A* => wij if
• A→ B C
• B* → wik
• C* → wkj
• For a sub-string wij of length j starting at i, the algorithm considers all possible
ways of breaking it into two parts wik and wkj. Since s = w1n, we have to verify that
S* => w1n
CYK algorithm
 CYK Parser
Step-1
Applying CYK parsing method for a
string w = aabb using sequence of
states created in chart (step by step)
and for a given simplified CNF below;
S→ AB|BB
A→ CC|AB|a
B→ BB|CA|b
C→ BA|AA|b

Step-3 Step-2
 • Applying CYK parsing method for a string
CYK Parser w = aabb using sequence of states created in
chart and given simplified CNF
 CYK Parser
• Obtain the parse tree using CYK parser for a sentence, “The girl
wrote an essay”.
• Let w = The girl wrote an essay S→ NP VP
VP→ Verb NP
NP→ Det Noun
Det→ an|the
Verb→ wrote
Noun → girl
Noun→ essay
 The parse tree using CYK
parser for a sentence, “The
girl wrote an essay”.