Scribd
Upload
14 views1 page

Tafl Assignment 3

This document outlines Assignment No. 3 for the B.TECH. (CSE, AIML) program, focusing on context-free and regular grammars. It includes objectives to assess students' understanding of grammars, ambiguity, and formal representations through various questions. The assignment is due on June 15, 2025, and will be evaluated based on alignment with course outcomes and Bloom's taxonomy levels.

Uploaded by

Animesh Garv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views1 page

Tafl Assignment 3

This document outlines Assignment No. 3 for the B.TECH. (CSE, AIML) program, focusing on context-free and regular grammars. It includes objectives to assess students' understanding of grammars, ambiguity, and formal representations through various questions. The assignment is due on June 15, 2025, and will be evaluated based on alignment with course outcomes and Bloom's taxonomy levels.

Uploaded by

Animesh Garv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

IQAC/25/05

ASSIGNMENT NO: 3
Assignment Title: TAFL- Context Free and Regular Grammars
Program Name: [Link].(CSE, AIML)
Program Code: 10, 153
Sem/Year:4TH SEM/2ND YEAR

Assignment Objectives
To assess students’ ability to work with grammars, derive languages, identify ambiguity, and convert
between formal representations using numerical and theoretical problems.
[Link] Questions Course Bloom Taxonomy
Outcomes Level
Q.1 Define a context-free grammar (CFG) and provide an example that
CO3 K1
generates balanced parentheses.
Q.2 Given a CFG: S → aSb | ε, derive the string 'aabb' and draw its derivation
CO3 K3
tree.
Q.3 Explain ambiguity in grammars. Show whether the grammar: S → SS | a is
CO3 K2,K4
ambiguous.
Q.4 Convert the FA accepting strings ending with '01' into a regular grammar. CO3 K3
Q.5 Convert the regular grammar: S → aS | bA, A → aS | ε into an FA. CO3 K3
Q.6 Simplify the following CFG by removing null and unit productions: S →
CO3 K4
aSb | A, A → ε.
Q.7 Convert the CFG: S → aSb | ab into Chomsky Normal Form & Greibach
CO3 K4
Normal Form.
Q.8 Explain Chomsky Hierarchy. Classify the following grammars: Type 0,
CO3 K2
Type 1, Type 2, Type 3.
Q.9 For the CFG: S → aSa | bSb | a | b, list 4 strings it generates and verify
CO3 K3
using derivations.
Q.10 Given a language L = {a^n b^n | n ≥ 0}, construct a CFG that generates it. CO3 K3
Q.11 Identify if the language L = {a^n b^m c^m d^n | n, m ≥ 1} is context-free.
CO3 K5
Justify your answer.
Q.12 Use the Pumping Lemma to show that the language L = {a^n b^n c^n | n
CO3 K6
≥ 1} is not context-free.
Q.13 Design a CFG that accepts all strings over {a, b} with an equal number of
CO3 K3
a's and b's.
Evaluation Criteria
Assignments will be assessed based on:
1. Alignment with course outcomes.
2. Demonstration of Bloom's taxonomy levels (1to6).
3. Clarity, accuracy, and depth of responses.

Faculty Sign: Principal/HOD Sign:

Assignment Issue Date: 06-06-2025 Assignment Submission Date:15-06-2025

You might also like