SWE1017 – Natural

Language Processing

Fall 2025-26

Module 1

[Link]
Professor
School of Computer Science and Engineering

1
Module -1-Overview of Natural Language
Processing(NLP)
Introduction to Natural Language Understanding NLP Overview:
Prerequisite technologies-Subfields of NLP-Related fields of NLP-
Structures used in NLP

2
Introduction to NLP
What is NLP ?
Natural Language Processing (NLP) is a subfield of Artificial Intelligence
(AI) and Linguistics that focuses on enabling machines to understand,
interpret, generate, and interact using human (natural) languages like
English, Hindi, Tamil etc.

3
Prerequisites for NLP

Technology Importance
Python Main language for NLP (NLTK, spaCy, Transformers)
Mathematics Probability, linear algebra, statistics for models
Machine Learning (ML) Used for text classification, clustering, etc.
Deep Learning (DL) Advanced NLP tasks (translation, summarization)
Linguistics Understanding syntax, semantics, morphology
Data Structures Lists, dictionaries, trees, graphs for text processing
Regular Expressions Text pattern matching and preprocessing

4
NLP
• Goal is to enable computers to understand, generate and communicate with
people using human languages.

5
Challenges of NLP
• People have no trouble understanding language
• Common sense
• Reasoning capacity
• World knowledge
• Computers does not have all the above
• The goal of NLP is to go way beyond just string processing or keyword matching!
• Many hidden variables
• Knowledge about the world
• Knowledge about the context
• Knowledge about human communication techniques
• Problem of scale
• Many (infinite?) possible words, meanings, context
• Problem of sparsity
• Very difficult to do statistical analysis, most things (words, concepts) are never seen before
• Long range correlations

6
Various Levels of NLP

7
Natural Language Vs. Computer Languages

• Ambiguity is the primary difference between natural and

computer languages.
• Formal programming languages are designed to be
unambiguous, i.e. they can be defined by a grammar
(deterministic context-free languages (DCLFs) )that
produces a unique parse for each sentence in the
language.

8
Related fields of NLP
Related Field How It Relates to NLP

Linguistics Provides rules of language structure (syntax, semantics, etc.)

Artificial Intelligence NLP is a core area within AI focused on understanding language

Machine Learning Powers modern NLP through pattern learning and prediction

Statistics & Probability Used for language modeling and probabilistic predictions

Computer Science Supplies algorithms and data structures for language processing

9
Related fields of NLP
Information Retrieval Helps in search, ranking, and understanding user queries

Information Extraction Extracts structured information (e.g., names, dates) from text
Speech Processing Converts between speech and text (ASR & TTS)
Computational Linguistics Builds formal models combining linguistics and computing

Cognitive Science Inspires models based on human understanding of language

Text Mining/Analytics Discovers patterns, topics, and insights from text
Knowledge
Helps NLP systems understand meaning and context
Representation

10
Structures used in NLP
• Lexical Structures
• Syntactic Structures
• Semantic Structures
• Discourse Structures
• Statistical and Vector-Based Structures
• Pragmatic and Knowledge Structures
• Morphological Structures
• Logic-Based Structures
• Prosodic and Phonological Structures (Used in speech NLP)

11
Lexical Structures

• Tokens / Words: The basic units in NLP (e.g., "cat", "ran").

• Lemmas and Stems: Root forms of words (e.g., "running" → "run").
• Part of Speech (POS): Tags like noun, verb, adjective, etc.
Example
• Input:
• "Dr. Smith is working at U.N. headquarters."
• Question:
Tokenize the sentence properly.
• Expected Output:
['Dr.', 'Smith', 'is', 'working', 'at', 'U.N.', 'headquarters', '.']

12
Stemming is the process of reducing Lemmatization is the process of converting a
a word to its root or base form word to its base or dictionary form, known as
(called the stem), usually by the lemma. It uses vocabulary and
morphological analysis to ensure that the
removing prefixes or suffixes. word is mapped correctly based on its context
and part of speech (POS).
• Input Words:
Input Words:
• "connected", "connection", • "running", "flies", "mice", "better"
"connecting"
• Question:
• Question: Find the lemmas of the above words.
Apply stemming using Porter • Expected Output:
Stemmer. • running → run
• Expected Output: • flies → fly
• connect, connect, connect • mice → mouse
• better → good
13
POS Tagging in NLP
POS Tagging (Part-of-Speech Tagging) is the process of assigning a part of
speech to each word in a sentence based on its meaning and context.
Sentence:
"The cat sat on the mat."

Word POS Tag Description

The DT Determiner
cat NN Noun, singular
sat VBD Verb, past tense
on IN Preposition
the DT Determiner
mat NN Noun, singular
14
Common POS Tags
Tag Meaning Example
NN Noun, singular dog, car
NNS Noun, plural dogs, cars
VB Verb, base form eat, go
VBD Verb, past tense ate, went
Verb, gerund/present
VBG eating
participle
JJ Adjective blue, tall
RB Adverb quickly, very
DT Determiner the, a, an
PRP Personal pronoun he, she, it
IN Preposition/Subordinator on, in, because
15
What it modifies Adj - modifies a Noun or Pronoun Verb, Adjective, or another Adverb

Answers What kind? Which one? How many? How? When? Where? To what extent?

Examples tall boy, red car, happy child runs quickly, very tall, arrived yesterday

Example Word happy, blue, fast quickly, very, well, yesterday

16
Identify the adjectives and adverbs
• She wore a beautiful dress.
• She quickly ran to the store.
• The fast runner won the race.
• He runs fast
• He is very smart.

17
Example : POS Tagging
Priya Wore a beautiful dress
Word POS Tag Description
Priya NNP Proper noun, singular
wore VBD Verb, past tense
a DT Determiner
beautiful JJ Adjective
dress NN Noun, singular
. . Punctuation

18
Tools for POS Tagging

• NLTK (Python)
• spaCy (Python)
• Stanford NLP
• TextBlob
• CoreNLP

19
Syntactic Structures

• Used to analyse the grammar and structure of sentences.

• Parse Trees:
• Constituency Tree: Shows how words group into phrases (NP, VP).
• Dependency Tree: Shows how words depend on each other.
• Context-Free Grammar (CFG): Set of rules for generating valid
sentences.
• Phrase Structure Grammar: Breaks down a sentence into hierarchical
components.

20
What is CFG (Context-Free Grammar)?
• CFG, or Context-Free Grammar, is a type of formal grammar used
to describe the syntactic structure of a language — especially
programming languages and natural languages.
• In Natural Language Processing (NLP), CFG is used to generate
parse trees (or syntax trees) for sentences, showing how words
combine into phrases and sentences.

21
Formal Definition of CFG
• A Context-Free Grammar (CFG) is a 4-tuple: Symbol Meaning
• G = (V, Σ, R, S) A set of non-terminal symbols
V
where: (like S, NP, VP)
• Example of CFG Rules (for simple English) Σ
A set of terminal symbols
• Copy code (words like cat, the, chased)
• S → NP VP A set of production rules (like S
R
→ NP VP)
• NP → DT NN
The start symbol (usually S for
• VP → VBD NP S
Sentence)
• DT → 'the' | 'a'
• NN → 'cat' | 'dog'
• VBD → 'chased' | 'saw'
• This grammar says:
• A sentence (S) is made of a noun phrase (NP) and verb phrase (VP)
• A noun phrase is a determiner followed by a noun
• A verb phrase is a verb followed by a noun phrase
22
Parse Tree
A parse tree is a hierarchical tree diagram that shows how a sentence is
constructed from its parts (such as noun phrases, verb phrases, etc.),
based on the rules of a formal grammar.
• They help machines understand sentence structure.
• Used in machine translation, question answering, grammar
checking, etc.
• Foundation for syntactic parsers in NLP libraries (like NLTK, spaCy,
Core NLP).

23
Parse tree and its types
A parse tree is a tree diagram that represents the syntactic structure of a sentence according to a grammar. It
shows how words group together and how they relate to each other in a sentence.
There are 2 main types of parse trees
• Constituency Parse Tree (Phrase Structure Tree)
▪ Represents nested phrase structures (e.g., noun phrases, verb phrases).
▪ Follows the rules of a context-free grammar (CFG).
▪ Each internal node is a syntactic category (NP, VP, PP, etc.).

▪ Leaves are words (tokens).

24
Constituency Parse Tree (Phrase Structure
Tree)

S
Label Meaning Example
/. \
NP VP S Sentence Entire sentence
/\ / \ NP Noun Phrase "The sky"
DT NN VBZ ADJP
VP Verb Phrase "is blue"
| | | |
The sky is blue DT Determiner "The"
NN Noun (singular) "sky"
Verb (present, 3rd
VBZ "is"
person)
ADJP Adjective Phrase "blue"

25
Example
The Cat sat on the mat
Label Meaning Example
S Sentence Full sentence
S "The cat", "the
/ \ NP Noun Phrase
mat"
NP VP
VP Verb Phrase "sat on the mat"
/\ / \
DT NN VBD PP Prepositional
PP "on the mat"
| | | / \ Phrase
The cat. sat IN NP DT Determiner "The", "the"
/ \
NN Noun (singular) "cat", "mat"
on DT NN
| | VBD Verb (past tense) "sat"
the mat IN Preposition "on"

26
Dependency Parse Tree
• Shows direct grammatical relationships between words (head →
dependent).
• Each word (except root) depends on another word (its "head").
• Focuses more on function and roles than on phrase grouping

27
Example
Dependency
Token Head Description
(dep_)
is (ROOT) The det sky Determiner modifying "sky"
/ \
sky blue sky nsubj is Subject of the verb "is"
| | is ROOT is Main verb
The (acomp) blue acomp is Adjectival complement
(nsubj)

28
Example 2

sat (ROOT)
/ | \
cat on (nsubj)
| \
The mat
/
the

29
Summary of Parsers
Handles
Algorithm Type Grammar Build Parse Tree
Ambiguity
CYK Bottom-up CNF Yes Yes
Earley Top-down CFG Yes Yes
LL (e.g., RD) Top-down LL(k) No Yes
LR
Bottom-up LR(k) No Yes
(SLR/LALR)
Chart Parser Mixed CFG Yes Yes
Shift-
Bottom-up CFG (LR) No Yes
Reduce
Packrat
Top-down PEG No Yes
(PEG)
GLR Bottom-up CFG Yes Yes

30
What is Ambiguity in a Parser?

• In NLP and compiler design, ambiguity in a parser refers to a situation where a single sentence or input
can be parsed in more than one valid way — that is, it has multiple parse trees or structures.
• Ambiguity occurs when a grammar allows two or more different parse trees (or derivations) for the same
input string.
• Types of Ambiguity

Type Description Example

Multiple parse trees for the same
Syntactic Ambiguity "I saw the man with a telescope"
sentence
A word has multiple meanings or
Lexical Ambiguity "bear" (noun or verb)
parts of speech

31
Semantic Structures
• Semantic Structures
• Capture the meaning of words and sentences.
• Semantic Roles / Frame Semantics: Who did what to whom.
• Named Entity Recognition (NER): Identifies names, dates, places, etc.
• WordNet / Ontologies: Structured representation of word meanings
and relationships.
• Semantic Graphs / Concept Graphs: Represent entities and their
relationships.

32
Named Entity Recognition (NER)

Named Entity Recognition is the process of locating and categorizing key

information (named entities) in text into specific types such as names of people,
places, organizations, dates, etc.

Input:
• "Apple Inc. was founded by Steve Jobs in Cupertino."
Question:
Identify the named entities.
• Expected Output:
• Apple Inc. → ORGANIZATION
• Steve Jobs → PERSON
• Cupertino → LOCATION

33
Where it is used
Application Area Purpose of NER
Understand and index entities in queries
Search Engines
and documents
Chatbots &
Recognize user-intent and destinations
Assistants
Extract company names, amounts, dates
Finance
from news or reports
Identify names, case numbers, and laws
Legal
in documents
Detect diseases, drugs, symptoms in
Healthcare
clinical records
Social Media Track trending people, places, or events
Focus on people, organizations, and
News Summarization
places in summaries
Handle named entities accurately
Machine Translation 34
without literal translation
 what is WORDNET
WordNet is a large lexical database of English developed at Princeton University.
• Words are grouped into sets of synonyms called synsets.
• Each synset expresses a distinct concept.
• Synsets are interlinked by semantic relations like:
• Synonymy (e.g., car and automobile)
• Antonymy (e.g., hot vs cold)
• Hyponymy (e.g., dog is a kind of animal)
• Hypernymy (e.g., animal is a general term for dog, cat)
Example:
• For the word “bank”, WordNet may have:
• Synset 1: bank (financial institution)
• Synset 2: bank (side of a river)

35
Ontology
• An ontology is a formal, structured representation of knowledge that defines
• Concepts in a domain
• Relationships among those concepts
• Often includes rules, constraints, and hierarchies
• Ontologies are used in Semantic Web, AI, bioinformatics, question answering,
and more.
• Example:
In a medical ontology:
• HeartDisease is a subclass of Disease
• Patient can haveCondition → HeartDisease
• Doctor can treat → Patient

36
Discourse Structures

• Used for text beyond single sentences.-Maintain the context

• Coreference Chains: Link mentions of the same entity.
• Discourse Trees (RST - Rhetorical Structure Theory): Analyse
coherence of text.
• Dialogue Acts: Represent intent in conversations (e.g., question,
request, inform).

37
What is Discourse structure
• Discourse structure refers to how larger units of text (sentences,
paragraphs, dialogues) are organized and connected to convey
coherent meaning in language.
• It's a key concept in Natural Language Processing (NLP), linguistics,
and computational discourse analysis.

38
Statistical and Vector-Based Structures

• Used in machine learning and deep learning models.

• Bag-of-Words (BoW): Frequency of words, no order.
• TF-IDF: Word importance in a document.
• Word Embeddings: Dense vectors (e.g., Word2Vec, GloVe, FastText).
• Sentence Embeddings / Document Embeddings: Represent larger
text units.
• Attention Mechanisms & Transformers: Structure input for models
like BERT, GPT.
39
Pragmatic and Knowledge Structures

• Pragmatic and Knowledge Structures

• Used for reasoning, inference, and understanding context.
• Knowledge Graphs: Nodes (entities) and edges (relations).
• Common sense Knowledge Bases: e.g., ConceptNet, Cyc.
• Dialogue Trees / State Graphs: For conversation flow.

40
Morphological Structures

• Analyse internal word structure.

• Morphemes: Smallest units of meaning (e.g., un-break-able).
• Finite State Machines (FSM): For morphological parsing.

41
Logic-Based Structures

• Used in more formal NLP settings like question answering, reasoning,

or semantic parsing:
• First-Order Logic (FOL): e.g., ∀x [Person(x) → Mortal(x)]
• Predicate Logic Trees: Represent structured meaning.
• Lambda Calculus Representations: For mapping natural language to
logic.

42
Prosodic and Phonological Structures (Used in
speech NLP)
Prosodic and Phonological Structures (Used in speech NLP)
• Phonemes: Basic sound units of language.
• Stress, Intonation, Rhythm Patterns: Important in speech recognition
and speech synthesis.

43