Natural Language Processing

— Comprehensive Exam Notes —

1. Introduction & History of NLP

Natural Language Processing (NLP) is a branch of Artificial Intelligence (AI) that
helps computers understand, interpret, and manipulate human language. It trans-
forms raw human language into a structured form that machines can utilize.
Key Milestones in History:

• 1950s - The Dawn & Turing Test: Alan Turing proposed a test of machine
intelligence based on natural language conversation. The 1954 Georgetown-
IBM Experiment successfully translated over 60 Russian sentences into English
using rule-based systems.
• 1960s - Symbolic / Rule-Based Era: Development of ELIZA (1964-1966) by
Joseph Weizenbaum. ELIZA simulated a psychotherapist using pattern match-
ing and substitution, demonstrating superficial communication without true
contextual understanding. Other systems like SHRDLU emerged, operating in
highly restricted ”blocks worlds.”
• 1980s & 1990s - Statistical NLP Paradigm Shift: Researchers realized lan-
guage is too messy for rigid hand-written rules. The focus shifted to statistical
models (e.g., Hidden Markov Models - HMMs) that leveraged large datasets to
calculate probabilities. This era introduced machine learning algorithms that
could ”learn” patterns from annotated data.
• 2000s - Rise of Machine Learning: Algorithms like Support Vector Machines
(SVMs) and Latent Dirichlet Allocation (LDA) dominated, reducing reliance on
manual annotation.
• 2010s - Deep Learning Era: Neural networks revolutionized NLP. Techniques
like Word Embeddings (Word2Vec, GloVe) represented words as dense vec-
tors, capturing semantic relationships (e.g., King - Man + Woman = Queen).
Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTMs) im-
proved sequential data processing.
• 2017 to Present - The Transformer Revolution: Google introduced the Trans-
former architecture (”Attention Is All You Need”). Using self-attention mecha-
nisms, models like BERT (Bidirectional Encoder Representations from Trans-
formers) and GPT (Generative Pre-trained Transformer) can understand long-
range dependencies and context bidirectionally, achieving near-human per-
formance.

1
 2. Generic NLP System Architecture
A generic NLP system is a pipeline that processes language step-by-step:

Raw Text/Speech Input → Pre-processing (Tokenization, Normalization, Noise

Removal) →
Linguistic Analysis (Morphological, Syntactic, Semantic) →
Machine Learning / Rule-Based Model → Output (Classification, Translation,
Generation)

3. Levels of Language Processing in NLP

Language processing is typically divided into hierarchical levels to break down com-
plexity:

• Phonology / Phonetics: Deals with the physical sounds of language. Purpose:

Crucial for speech recognition and text-to-speech systems.
• Morphology: Studies the internal structure of words. Purpose: Breaks words
into morphemes (smallest units of meaning). Example: ”unbelievable” = un-
(prefix) + believe (root) + -able (suffix). Used for stemming and lemmatization.
• Syntax: Concerns sentence structure and grammar rules (parsing). Purpose:
Identifies how words form phrases and relate grammatically. Example: Subject
+ Verb + Object (”The dog chased the cat”).
• Semantics: Focuses on the exact literal meaning of words and sentences. Pur-
pose: Resolves basic ambiguity and assigns dictionary meanings. Example: Dis-
tinguishing ”bank” (river) vs. ”bank” (finance).
• Discourse Integration: Analyzes structure and meaning beyond a single sen-
tence. Purpose: Handles references and coherence across sentences. Exam-
ple: ”Ravi went to the store. He bought a book.” (Resolving ’He’ to ’Ravi’ via
co-reference resolution).
• Pragmatics: Understanding meaning in context, using real-world knowledge.
Purpose: Infers the speaker’s actual intent beyond the literal meaning. Exam-
ple: ”Can you pass the salt?” is a polite request, not a question about physical
ability.

4. Knowledge in Language Processing

For a machine to truly understand language, it requires distinct types of knowledge:

• Linguistic Knowledge: Understanding of dictionary meanings, morphology,

syntax, and grammatical rules.
• World / Common Sense Knowledge: General facts about how the world
works (e.g., water is wet, humans cannot fly unaided). Without this, resolving

2
 statements like ”The trophy didn’t fit in the suitcase because it was too large”
is impossible.
• Contextual Knowledge: Information about the specific situation, speaker in-
tent, or the surrounding text/dialogue history.

5. Ambiguity in Natural Language

Ambiguity is the central challenge in NLP. It occurs when a phrase has multiple in-
terpretations.

Detailed Types of Ambiguity:

• Lexical Ambiguity (Word-Level): A single word has multiple meanings.

Example: ”I swung the bat.” (Animal or sports equipment?). Requires con-
text to resolve.
• Syntactic Ambiguity (Structural): A sentence can be parsed in multiple
grammatical ways.
Example: ”I saw the man with the telescope.” (Did I use a telescope to see
him, or did he hold a telescope?).
• Semantic Ambiguity: The literal meaning doesn’t make logical sense
without deeper context, even if grammatically correct.
Example: ”He is cold.” (Temperature-wise or emotionally distant?).
• Pragmatic Ambiguity: The speaker’s intention is unclear.
Example: ”Great, another Monday!” (Literal excitement or sarcasm?). Re-
quires understanding tone and intent.
• Referential Ambiguity: Pronouns or phrases refer to unclear entities.
Example: ”John hit Peter and he cried.” (Who cried, John or Peter?). Han-
dled by coreference resolution.

6. Stages of NLP (The Analytical Pipeline)

1. Lexical Analysis: Scanning text and dividing it into paragraphs, sentences,
and words (Tokenization).
2. Syntactic Analysis (Parsing): Checking sentences against formal grammar
rules to build a parse tree showing relationships.
3. Semantic Analysis: Checking for logical meaningfulness based on dictionary
definitions. Rejecting anomalies like ”Hot ice cream”.
4. Discourse Integration: Evaluating how the meaning of a sentence is influ-
enced by preceding sentences.

3
 5. Pragmatic Analysis: The final stage, re-interpreting what was literally said
into what was actually intended by the user in the real world.

7. Major Challenges in NLP

• Resolving Ambiguity: As detailed above, context is notoriously difficult to en-
code algorithmically.
• Sarcasm, Irony, and Humor: Traditional sentiment analysis relies on fixed
word scores. ”Great, another error!” contains a positive word (”Great”) but has
a negative intent. Machines struggle to detect this tonal inversion.
• Slang, Idioms, and Cultural Nuance: Phrases like ”It’s raining cats and dogs”
or ”break a leg” cannot be translated literally; they require localized cultural
knowledge.
• Data Sparsity: While English has massive datasets, thousands of rare or in-
digenous languages lack the annotated data required to train modern deep
learning models effectively.
• Unstructured / Messy Input: User input is rarely perfect. Misspellings,
poor grammar, mixed languages (code-switching), and domain-specific jargon
present significant hurdles.

8. Applications of NLP
• Machine Translation: Google Translate, DeepL.
• Virtual Assistants & Chatbots: Siri, Alexa, ChatGPT.
• Sentiment Analysis: Analyzing customer reviews to see if they are positive,
negative, or neutral.
• Information Extraction: Pulling specific entities (names, dates, locations)
from large documents.
• Text Summarization: Automatically generating a short summary of a long
news article.
• Spell & Grammar Checking: Grammarly, Microsoft Word Editor.

9. Formal Language Concepts in NLP

To process language algorithmically, NLP relies heavily on concepts borrowed from
Automata Theory and Formal Languages. These concepts form the foundation for
tasks like tokenization and basic pattern matching.

4
Foundational Definitions:

• Alphabet (Σ): A finite, non-empty set of symbols.

Example: In English text processing, the alphabet might be
{a, b, c, ..., z, A, B, ..., Z, punctuation, space}.
• String (or Word): A finite sequence of symbols chosen from an alphabet. The
empty string is denoted by  (epsilon).
Example: ”nlp”, ”hello”, ”123”. The length of a string w is denoted as |w|.
• Language (L): A set of strings formed from a specific alphabet. A formal lan-
guage is defined by strict mathematical rules (unlike natural language, which
evolves organically).
Example: The set of all valid email addresses, or the set of all strings ending in
”ing”.

10. Regular Expressions and Finite Automata

Regular Expressions (Regex) are algebraic notations used to define regular lan-
guages. They provide a powerful, concise way to specify patterns for string match-
ing.

• Common Operations: Concatenation (AB), Union/Alternation (A|B), Kleene Star

(A*) meaning zero or more repetitions.
• NLP Application: Regex is heavily used in early pipeline stages for tokenization
(splitting text by spaces), stemming (removing suffixes like ’ing’ or ’ed’), and
extracting specific entities like phone numbers or dates.

Finite Automata (FA) are theoretical computing machines used to recognize regu-
lar languages. They are the computational implementation of regular expressions.
An FA reads an input string symbol by symbol and changes its internal state. If it
ends in a designated ”accepting” state, the string is valid.

Types of Finite Automata:

• Deterministic Finite Automata (DFA): For every state and input symbol,
there is exactly one defined next state. It is strict and straightforward to
implement in code.
• Non-Deterministic Finite Automata (NFA): For a given state and input
symbol, there can be multiple possible next states, or transitions on the
empty string (). While conceptually more complex (requiring backtrack-
ing or parallel execution paths), NFAs are often easier to design from a
Regex. Every NFA can be converted into an equivalent DFA.
• NLP Use Case: FAs are used in fast dictionary lookups, morphological pars-
ing, and spell-checking algorithms (like Levenshtein automata).

5
 11. Limitations of Regular Languages for Natural Language
While regular expressions and finite automata are excellent for basic text processing
(like finding emails or tokenizing), they are mathematically insufficient to fully model
the complexity of human syntax. This is a common exam topic!

• No Memory / Inability to Count: Finite Automata have a strictly finite number

of states. They cannot ”remember” how many times they have seen a symbol.

• Impact: They cannot handle structures requiring matching pairs, such as

ensuring an equal number of opening and closing parentheses ((...)),
or enforcing subject-verb agreement across a long sentence with many
intervening clauses.

• Inability to Handle Center-Embedding (Recursion): Natural language fre-

quently uses recursive, nested structures where a clause is embedded within
another clause.

• Example: ”The cat [that the dog [that the man saw] chased] ran away.”
• Impact: Regular languages cannot model this An B n nested pattern. To
properly parse grammatical structures like this, NLP systems must use
more powerful models, specifically Context-Free Grammars (CFGs) and
pushdown automata, which incorporate a stack for memory.

12. Context-Free Grammars (CFG) & Components

To overcome the limitations of regular languages (like handling nested structures
and recursion), NLP uses Context-Free Grammars (CFGs). A CFG is a set of recur-
sive rewriting rules used to generate patterns of strings.
Formal Components of a CFG:
A CFG is mathematically defined as a 4-tuple G = (N, Σ, P, S):

• N (Non-Terminals): A finite set of syntactic categories or variables that can

be further expanded. In NLP, these are often tags like S (Sentence), N P (Noun
Phrase), or V P (Verb Phrase).
• Σ (Terminals): A finite set of symbols that form the actual strings of the lan-
guage. In NLP, these are the actual words from the dictionary (e.g., ”cat”, ”the”,
”sleeps”). N and Σ are strictly disjoint sets.
• P (Production Rules): A set of rules defining how non-terminals can be rewrit-
ten. Each rule is of the form A → β, where A is a single non-terminal and β is
a sequence of terminals and/or non-terminals. (e.g., N P → Det N ).
• S (Start Symbol): A special non-terminal symbol from N that represents the
entire structure being generated (typically S for Sentence).

6
 13. Derivations and Parse Trees
Derivations
A derivation is the step-by-step process of applying production rules to generate a
string of terminals starting from the Start Symbol (S).

• Leftmost Derivation: At each step, the leftmost non-terminal in the sequence

is replaced.
• Rightmost Derivation: At each step, the rightmost non-terminal in the se-
quence is replaced.

Parse Trees
A parse tree (or syntax tree) is a visual, hierarchical representation of a derivation.
It shows the underlying grammatical structure of a sentence.

• Root Node: Always the Start Symbol (S).

• Internal Nodes: Always Non-terminals (e.g., N P, V P ).
• Leaf Nodes: Always Terminals (actual words).
• Yield: Reading the leaf nodes from left to right produces the generated sen-
tence.

Example Grammar:
S → NP V P
N P → Det N
VP →V
Det → ”The”, N → ”dog”, V → ”barks”
Derivation for ”The dog barks”: S ⇒ N P V P ⇒ Det N V P ⇒ ”The” N V P ⇒
”The” ”dog” V P ⇒ ”The” ”dog” ”barks”.

14. Ambiguity in CFGs

A Context-Free Grammar is considered ambiguous if there is at least one string in
its language that can be generated in more than one valid way.
Mathematically, a grammar is ambiguous if a sentence has:

• More than one distinct Parse Tree.

• More than one distinct Leftmost Derivation.
• More than one distinct Rightmost Derivation.

Impact on NLP:
Ambiguity in CFGs directly maps to Syntactic Ambiguity in natural language pro-
cessing (where sentences have multiple grammatical interpretations).

• Example Sentence: ”I shot an elephant in my pajamas.”

7
 • Parse Tree 1: The prepositional phrase (PP) ”in my pajamas” attaches to the
Verb Phrase (VP). Meaning: I was wearing the pajamas while shooting.
• Parse Tree 2: The PP attaches to the Noun Phrase (NP) ”an elephant”. Meaning:
The elephant was wearing my pajamas.

Resolving CFG Ambiguity:

Since pure CFGs cannot decide which parse tree is ”correct,” modern NLP uses
Probabilistic Context-Free Grammars (PCFGs). In PCFGs, every production
rule is assigned a probability based on real-world training data. The parser
calculates the total probability of each generated parse tree and selects the
most likely one based on context.

15. Spelling Correction and Edit Distance

Spelling correction is a fundamental NLP task dealing with identifying and fixing
typographical errors. Errors generally fall into two categories:

• Non-word Errors: The typed word is not in the dictionary (e.g., ”graffe” instead
of ”giraffe”).
• Real-word Errors: The typed word is valid, but it is the wrong word for the
context (e.g., ”piece” instead of ”peace”).

Minimum Edit Distance (MED)

MED is a metric used to quantify how dissimilar two strings are. It calculates the
absolute minimum number of editing operations required to transform a source
string into a target string.

The Three Basic Edit Operations:

1. Insertion: Adding a character. (e.g., cat → cart)

2. Deletion: Removing a character. (e.g., fast → fst)

3. Substitution: Replacing one character with another. (e.g., cat → bat)

16. Levenshtein Distance and Dynamic Programming

Levenshtein Distance is the most famous algorithm for measuring Minimum Edit
Distance. In the standard Levenshtein metric:
• Insertion and Deletion have a cost of 1.
• Substitution usually has a cost of 2 (because it can be viewed as one deletion

8
 followed by one insertion, though some versions assign a cost of 1).

How it is Computed: Dynamic Programming

Calculating MED naively for long strings is computationally expensive (exponential
time). To solve this efficiently, NLP uses Dynamic Programming.

• A matrix (grid) is created where the source string represents the rows and the
target string represents the columns.
• The algorithm fills the matrix step-by-step from the top-left to the bottom-
right, solving smaller sub-problems (comparing prefixes of the strings) and
saving the results.
• The value in the bottom-right cell of the matrix represents the final Minimum
Edit Distance between the two complete strings.

17. The Noisy Channel Model

The Noisy Channel Model is a probabilistic framework widely used in spelling cor-
rection, machine translation, and speech recognition.
The Core Idea: Imagine the user intended to write a correct word (w), but as they
typed, the word went through a ”noisy channel” (their fingers making a mistake, or
a bad phone signal), resulting in the misspelled observation (x). The system’s goal
is to reverse-engineer the channel to find the most likely intended word.

The Mathematics (Based on Bayes’ Rule):

To find the best intended word ŵ, the model calculates:
ŵ = arg max P (x|w) × P (w)
w

• P (w) – The Language Model (Prior): How common is the word w

in the English language? For example, P (”the”) is very high, while
P (”thesaurus”) is much lower.
• P (x|w) – The Error Model (Channel Model): What is the probability that
the user typed the error x when they actually meant w? This is often calcu-
lated using keyboard layout proximity (e.g., typing ’s’ instead of ’a’ is highly
probable because they are adjacent on a QWERTY keyboard) or using the
Edit Distance.

Example in Practice:
If a user types ”thew”, the system finds candidate words (e.g., the, threw, them, chew).
It calculates the Error Model (how likely is the typo for each candidate) and multi-
plies it by the Language Model (how common the candidate is). ”the” will likely win
because, despite needing an edit, P (”the”) is massively higher than the other op-
tions.

9
 18. Approaches to NLP
Historically and practically, NLP systems are built using one of three primary
paradigms, or a hybrid of them.

• Rule-Based Approach (Symbolic NLP):

• Concept: Relies on hand-crafted linguistic rules (like Regular Expressions

and Context-Free Grammars) and dictionaries created by human experts.
• Pros: High precision. The logic is entirely transparent and explainable.
Great for narrow, highly specific domains.
• Cons: Very rigid. Fails easily on noisy data (slang, typos). Incredibly ex-
pensive and time-consuming to scale, as every new language or domain
requires rewriting the rules.

• Data-Based Approach (Statistical / Machine Learning):

• Concept: Systems ”learn” language patterns autonomously by analyzing

massive amounts of text data (corpora). Uses probabilities (HMMs, Naive
Bayes) or neural networks (Deep Learning, Transformers).
• Pros: Highly scalable, adaptable to new languages, and robust to messy,
real-world text. Current state-of-the-art for almost all NLP tasks (e.g., GPT-
4, BERT).
• Cons: Requires massive datasets and immense computational power. Of-
ten acts as a ”black box” where it is difficult to explain why the model made
a specific decision.

• Knowledge-Based Approach:

• Concept: Uses explicit representation of the world’s knowledge through

Ontologies, Semantic Networks, or databases (like WordNet). It focuses
on the semantic relationships between concepts (e.g., knowing that a
”dog” is a ”mammal”).
• Pros: Excellent for deep semantic understanding, logical reasoning, and
complex Question-Answering systems.
• Cons: Building and maintaining comprehensive knowledge bases is a
massive, never-ending human effort.

19. Python-based NLP Libraries & Use Cases

Python is the dominant language for NLP. Different libraries serve distinct purposes
in the development lifecycle.

• NLTK (Natural Language Toolkit):

• Overview: The classic, most famous Python library for NLP. It is exhaustive,
providing over 50 corpora and lexical resources (like WordNet).

10
 • Characteristics: It is highly modular and allows you to see how algorithms
work under the hood. However, it is relatively slow and operates on strings
rather than complex objects.
• Use Cases: Education, academic research, prototyping, linguistic explo-
ration, and learning the fundamentals of NLP. Not recommended for high-
volume production.

• spaCy:

• Overview: Billed as ”Industrial-Strength NLP.” Written in Cython for ex-

treme speed and efficiency.
• Characteristics: Unlike NLTK (which offers 20 ways to do one thing), spaCy
provides one, highly-optimized, state-of-the-art way to do it. It is object-
oriented, returning parsed documents as rich objects.
• Use Cases: Real-world production environments, large-scale information
extraction, high-speed Named Entity Recognition (NER), and building
complex NLP pipelines.

• TextBlob:

• Overview: Built on the shoulders of NLTK and Pattern. It abstracts away

the complexity of NLP behind an incredibly simple, intuitive API.
• Characteristics: Treats text just like standard Python strings but with built-
in NLP methods (e.g., [Link]).
• Use Cases: Rapid prototyping, absolute beginners to NLP, and performing
quick, out-of-the-box tasks like basic sentiment analysis, spelling correc-
tion, or translation without needing deep ML knowledge.

End of Notes — Happy Studying!

11