1b. Illustrate Context-Free Grammar (CFG).

Describe its components

and how it is used to generate sentences.
A Context-Free Grammar (CFG) is a formal system used in Computer Science to
describe the structure of languages. It is widely used in compiler design,
natural language processing, and syntax analysis.

🔹 Definition of CFG
A Context-Free Grammar is defined as a 4-tuple:
G = (V, T, P, S)
Where:
• V (Variables / Non-terminals): Symbols that can be replaced (e.g., S, A, B)
• T (Terminals): Actual symbols of the language (e.g., a, b)
• P (Productions): Rules that define how variables can be replaced
• S (Start Symbol): The symbol from which derivation begins

🔹 Components Explained
1. Non-terminals (V)
• Represent intermediate symbols
• Help define the structure of the language
2. Terminals (T)
• Final symbols that form the actual strings of the language
• Cannot be replaced further
3. Production Rules (P)
• Define how non-terminals are transformed
• General form:
A→α
where A is a non-terminal and α is a combination of terminals and/or
non-terminals
4. Start Symbol (S)
• The initial non-terminal from which strings are generated
🔹 Example of CFG
Let’s define a CFG:
• V = {S}
• T = {a, b}
• P:
o S → aSb
o S → ab
• S is the start symbol

🔹 How CFG Generates Sentences

A CFG generates strings by applying production rules step-by-step.

✔ Derivation Example:
Start with S:
1. S → aSb
2. aSb → aaSbb
3. aaSbb → aabb
So, the string “aabb” is generated.

🔹 Types of Derivation
• Leftmost derivation: Replace the leftmost non-terminal first
• Rightmost derivation: Replace the rightmost non-terminal first

🔹 Parse Tree (Illustration)

For string aabb, the parse tree would look like:

S
/|\
a S b
/\
a b
This tree shows how the string is derived from the start symbol.

🔹 Uses of CFG
• Syntax analysis in compilers
• Designing programming languages
• Natural language processing
• Pattern recognition

🔹 Conclusion
A Context-Free Grammar provides a structured way to define languages using
rules. By repeatedly applying production rules starting from the start symbol,
valid sentences of the language can be generated.

[Link] is Constituency in syntax? Explain phrase level and

sentence level constructions with examples.
Constituency:
• Words in a sentence are not tied together as a sequence of part-of-
speech.
• Language puts constraints on word order.
• Words group together to form constituents (often termed phrases),
each of which acts as a single unit. They combine with other
constituents to form larger constituents, and eventually, a sentence.
• Constituents combine with others to form a sentence constituent.
• For example: the noun phrase, The bird, can combine with the verb
phrase, flies, to form the sentence, The bird flies.
• Different types of phrases have different internal structures.

Phrase-Level Constructions
1. Noun Phrase (NP)
• Headed by a noun or pronoun.
• Can act as subject, object, or complement.
• May include determiners and adjectives.
• Rule: NP → (Det) (AP) Nom (PP)
• Nominal rule: Nom → Noun | Noun Nom
Examples:
• They
• The foggy morning
• A beautiful lake in Kashmir
• Cold banana shake
2. Verb Phrase (VP)
• Headed by a verb.
• Organizes elements dependent on the verb.
• Rule: VP → Verb (NP) (NP) (PP)* or VP → Verb S
Examples:
• Khushbu slept
 • The boy kicked the ball
• The boy gave the girl a book
3. Prepositional Phrase (PP)
• Headed by a preposition.
• Rule: PP → Prep (NP)
Example:
• on the beach
4. Adjective Phrase (AP)
• Headed by an adjective.
• Rule: AP → (Adv) Adj (PP)
Example:
• very late, fond of animals
5. Adverb Phrase (AdvP)
• Rule: AdvP → (Intens) Adv
• Example: very quickly
Sentence-Level Constructions
1. Declarative: Statement → S → NP VP
Example: I like horse riding
2. Imperative: Command → S → VP
Example: Open the door
3. Yes/No Question: → S → Aux NP VP
Example: Do you have a pen?
4. Wh-Question: → S → Wh-NP VP / Wh-NP Aux NP VP
Example: Where are you going?
Conclusion
 • Phrase-level rules explain structure of phrases.
• Sentence-level rules explain how phrases form complete
sentences.
• Grammar rules are not exhaustive and may not cover all
structures.
[Link] Top-down and Bottom-up parsing techniques. Compare
their working, advantages, and limitations.

Parsing
• A phrase structure tree constructed from a sentence is called a parse.
• The syntactic parser is thus responsible for recognizing a sentence and
assigning a syntactic structure to it.
Two most widely used search strategies by parsers,
1. Top-down or goal-directed search.
2. Bottom-up or data-directed search.
Top-Down Parsing
• Starts parsing from the root node (Start symbol S) and moves
downwards towards the leaves.
• The parser tries to generate the input sentence by expanding the start
symbol.

Working
• Begin with the start symbol S.
• Expand S using all grammar rules where S appears on the left-hand side.
• Generate possible sub-trees from these rules.
• Each non-terminal symbol in the sub-tree is further expanded using
appropriate grammar rules.
• The right-hand side of rules provides new nodes, which are expanded
recursively.
• The tree continues to grow downward until only terminal symbols
(words / parts of speech) remain.
• Parsing is successful when the generated tree exactly matches the input
sentence.
Bottom-Up Parsing
• A bottom-up parser starts with the input sentence words and builds the
parse tree upward toward the root (Start symbol S).
• It works by reducing the input string step-by-step into non-terminals.

Working
• Start with input words:
Begin with the words of the sentence as the leaves of the parse tree.
• Find matching grammar rules:
Look for grammar rules where the right-hand side (RHS) matches parts
of the input.
 • Apply reduction:
Replace the matched portion with the corresponding left-hand side
(LHS) non-terminal.
• Build tree upward:
Gradually construct the parse tree by moving from leaves to root.
• Repeat process:
Continue applying reductions step-by-step.
• Reach start symbol:
Stop when the entire input is reduced to the start symbol (S).

Advantages:
• Can handle left recursion
• More powerful and efficient
 • No backtracking required

✔ Limitations:
• More complex to implement
• Requires more memory
• Construction of parsing tables is difficult

[Link] the Naive Bayes classifier. Derive the formula using

Bayes’ theorem and discuss its assumptions.
Naive Bayes Classifier
The Naive Bayes classifier is a probabilistic model used for classification tasks
such as text classification, spam detection, and sentiment analysis. It assigns
a class to a document based on the maximum posterior probability.

🔹 Derivation Using Bayes’ Theorem

Let:
• 𝒅= document
• 𝒄= class
The goal is to find the class with highest probability:
𝒄̂ = 𝐚𝐫𝐠⁡ 𝐦𝐚𝐱⁡ 𝑷(𝒄 ∣ 𝒅)
𝒄∈𝑪

Step 1: Apply Bayes’ Theorem

𝑷(𝒅 ∣ 𝒄) 𝑷(𝒄)
𝑷(𝒄 ∣ 𝒅) =
𝑷(𝒅)

Step 2: Simplify
Since 𝑷(𝒅)is constant for all classes:
𝒄̂ = 𝐚𝐫𝐠⁡ 𝐦𝐚𝐱⁡ 𝑷(𝒅 ∣ 𝒄) 𝑷(𝒄)
𝒄∈𝑪

Step 3: Represent Document as Features

A document is represented as a set of features:
 𝒅 = (𝒇𝟏 , 𝒇𝟐 , . . . , 𝒇𝒏 )

So:
𝑷(𝒅 ∣ 𝒄) = 𝑷(𝒇𝟏 , 𝒇𝟐 , . . . , 𝒇𝒏 ∣ 𝒄)

Step 4: Apply Naive Bayes Assumption

Assuming conditional independence:
𝒏

𝑷(𝒇𝟏 , 𝒇𝟐 , . . . , 𝒇𝒏 ∣ 𝒄) = ∏ 𝑷( 𝒇𝒊 ∣ 𝒄)
𝒊=𝟏

🔹 Final Formula
𝒏

𝒄̂ = 𝐚𝐫𝐠⁡ 𝐦𝐚𝐱⁡ 𝑷(𝒄) ∏ 𝑷( 𝒇𝒊 ∣ 𝒄)

𝒄∈𝑪
𝒊=𝟏

This is the Naive Bayes classification rule.

🔹 Assumptions of Naive Bayes

1. Bag-of-Words Assumption
o Ignores word order and considers only frequency of words.
2. Conditional Independence Assumption
o Features (words) are independent given the class.
3. Feature-Based Representation
o Each word is treated as an independent feature.

[Link] how Naive Bayes classifies a sentence by referring to a

worked example.
Naive Bayes Classification of a Sentence
• The Naive Bayes classifier applies Bayes’ theorem to determine the
most probable class for a given sentence.
 • It assumes that the words (features) in a sentence are conditionally
independent given the class.

🔹 Working Steps
• Step 1: Training Phase
o Collect labeled sentences (e.g., Spam or Ham).
o Calculate prior probabilities of each class:
Number of documents in class
𝑃(𝐶) =
Total documents
• Step 2: Likelihood Estimation
o Compute probability of each word given a class:
Count of 𝑤𝑖 in class
𝑃(𝑤𝑖 ∣ 𝐶) =
Total words in class
• Step 3: Sentence Probability
o For a sentence 𝑋 = (𝑤1 , 𝑤2 , . . . , 𝑤𝑛 ):
𝑃(𝐶 ∣ 𝑋) ∝ 𝑃(𝐶)∏𝑃(𝑤𝑖 ∣ 𝐶)

• Step 4: Classification Decision

o Choose the class with the maximum posterior probability.
Worked example:
Let’s use a sentiment analysis domain with the two classes positive (+) and
negative (-), and take the following miniature training and test documents
simplified from actual movie reviews.
[Link] the step by step procedure how finite state transducer are
used in a two step morphological parser.
Finite State Transducer (FST) in Two-Step Morphological
Parser
A Finite State Transducer (FST) is an extension of a finite
automaton that maps between two levels of representation
(e.g., lexical form ↔ surface form). It is widely used in
morphological parsing.
A two-step morphological parser uses FSTs in two main
stages:
1. Morphological Analysis (Lexical Level)
2. Surface Realization (Surface Level)
🔹 Step-by-Step Procedure
Step 1: Input Word (Surface Form)
• The parser takes a word as input.
• Example: “cats”
Step 2: Lexicon FST (Morphological Analysis)
• The first FST maps the surface word into:
o Root (stem)
o Morphological features
• Example:
o cats → cat + Noun + Plural
👉 This step identifies:
• Stem
• Affixes (prefix/suffix)
• Grammatical features
Step 3: Intermediate Lexical Representation
• Output is in lexical form:
o Root + tags
• Example:
 o cat + N + PL

Step 4: Rule FST (Morphophonemic Rules)

• The second FST applies morphological rules:
o Handles spelling changes
o Applies phonological constraints
Examples:
• city + PL → cities (y → ies)
• stop + ed → stopped (doubling consonant)
Step 5: Mapping Between Levels
• FST connects:
o Lexical level (abstract form)
o Surface level (actual word)
Step 6: Output (Analysis Result)
• Final output:
o Root + grammatical features
• Example:
o cats → cat (noun, plural)