Automata Theory and Formal Languages (ATFL) - ODD Sem 2022-23
Problem Sets for Course Outcome – 2
Session -11 to 13 : Context Free Grammars and Context Free Languages
Find context-free grammars for the following
Problem-1:
languages
(with n ≥ 0, m ≥ 0).
(a) L = {anbm : n ≤ m + 3}.
(b) L = {anbm : n ≠ m − 1}.
(c) L = {anbm : n ≠ 2m}.
(d) L = {anbm : 2n ≤ m ≤ 3n}. (e)L={w∈{a,b}*:na (w)≠nb
(w)}.
Problem-2: Find
a context-free grammar for Σ = {a, b} for the
language L = {anwwRbn : w ∈ Σ*, n ≥ 1}.
Problem-3: Show that the following language is context-free.
Problem-4: Show a derivation tree for the string aabbbb with
the grammar
Give a verbal description of the language generated by this
grammar.
Problem-5: Consider the grammar with productions
Problem Sets for Course Outcome – 2
Session -11 to 13 : Context Free Grammars and Context Free Languages
Find context-free grammars for the following
Problem-1:
languages
(with n ≥ 0, m ≥ 0).
(a) L = {anbm : n ≤ m + 3}.
(b) L = {anbm : n ≠ m − 1}.
(c) L = {anbm : n ≠ 2m}.
(d) L = {anbm : 2n ≤ m ≤ 3n}. (e)L={w∈{a,b}*:na (w)≠nb
(w)}.
Problem-2: Find
a context-free grammar for Σ = {a, b} for the
language L = {anwwRbn : w ∈ Σ*, n ≥ 1}.
Problem-3: Show that the following language is context-free.
Problem-4: Show a derivation tree for the string aabbbb with
the grammar
Give a verbal description of the language generated by this
grammar.
Problem-5: Consider the grammar with productions
