Contest-Free-Grammar
Question 1 |
Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
{(ab)n (cb)n│n ≥ 1} | |
{(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1} | |
{(ab)n (cbm)n│m,n ≥ 1} | |
{(ab)n (cbn)m│m,n ≥ 1} |
Question 1 Explanation:
T→ bT | b, this production will generate any number of b’s > 1
S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:
Hence the language generated by the grammar is
L = {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:
Hence the language generated by the grammar is
L = {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
Question 2 |
Which of the following statements are true?
- I. Every left-recursive grammar can be converted to a
right-recursive grammar and vice-versa
II. All \epsilon productions can be removed from any context-free grammar by suitable transformations
III. The language generated by a context-free grammar all of whose productions are of the form X → w or X → wY (where, w is a string of terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
I, II, III and IV | |
II, III and IV only | |
I, III and IV only | |
I, II and IV only |
Question 2 Explanation:
Every left recursive grammar can be converted to a right-recursive grammar and vice-versa, the conversion of a left recursive grammar into right recursive is also known as eliminating left recursion from the grammar.
Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar).
Statement IV is also true, as in CNF the only productions allowed are of type:
A-> BC
A-> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar).
Statement IV is also true, as in CNF the only productions allowed are of type:
A-> BC
A-> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 3 |
Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → ε}
- I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
I only | |
I and III only | |
II and III only | |
I, II and III |
Question 3 Explanation:
Is ambiguous, as it has two parse tree for the string “abbaba”
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
There are 3 questions to complete.