ContextFreeLanguage
Question 1 
Consider the following languages:

I. {a^{m}b^{n}c^{p}d^{q} ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^{m}b^{n}c^{p}d^{q} ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^{m}b^{n}c^{p}d^{q} ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^{m}b^{n}c^{p}d^{q} ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are contextfree?
I and IV only  
I and II only
 
II and III only  
II and IV only 
Question 1 Explanation:
i) a^{m} b^{n} c^{p} d^{q}  m+p = n+q,
mn = qp
First we will push a’s in the stack then we will pop a’s after watching b’s.
Then some of a’s might left in the stack.
Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s.
And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) a^{m} b^{n} c^{p} d^{q}  m=n, p=q
Push a’s in stack. Pop a’s watching b’s.
Now push c’s in stack.
Pop c’s watching d’s.
So it is context free language.
iii) a^{m} b^{n} c^{p} d^{q}  m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
mn = qp
First we will push a’s in the stack then we will pop a’s after watching b’s.
Then some of a’s might left in the stack.
Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s.
And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) a^{m} b^{n} c^{p} d^{q}  m=n, p=q
Push a’s in stack. Pop a’s watching b’s.
Now push c’s in stack.
Pop c’s watching d’s.
So it is context free language.
iii) a^{m} b^{n} c^{p} d^{q}  m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
Question 2 
Consider the contextfree grammars over the alphabet {a, b, c} given below. S and T are nonterminals.

G_{1}: S → aSbT, T → cTϵ
G_{2}: S → bSaT, T → cTϵ
The language L(G_{1}) ∩ L(G_{2}) is
Finite  
Not finite but regular  
ContextFree but not regular  
Recursive but not contextfree 
Question 2 Explanation:
Strings generated by G_{1}:
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G_{2}:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G_{1}) and L (G_{2}) are:
{ϵ, c, cc, ccc…}
So, L (G_{1}) ∩ L (G_{2}) can be represented by regular expression: c*
Hence the language L (G_{1}) ∩ L (G_{2}) is “Not finite but regular”.
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G_{2}:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G_{1}) and L (G_{2}) are:
{ϵ, c, cc, ccc…}
So, L (G_{1}) ∩ L (G_{2}) can be represented by regular expression: c*
Hence the language L (G_{1}) ∩ L (G_{2}) is “Not finite but regular”.
Question 3 
Consider the following languages over the alphabet Σ = {a, b, c}.
Let L_{1} = {a^{n} b^{n} c^{m}│m,n ≥ 0} and L_{2} = {a^{m} b^{n} c^{n}│m,n ≥ 0}
Which of the following are contextfree languages?

I. L_{1} ∪ L_{2}
II. L_{1} ∩ L_{2}
I only  
II only  
I and II  
Neither I nor II 
Question 3 Explanation:
Strings in L_{1} = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L_{2} = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L_{1} ∪ L_{2} ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L_{1} ∪ L_{2}) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L_{1} ∪ L_{2}) is CFL.
Strings in L_{1} ∩ L_{2} = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L_{1} ∩ L_{2}) will have (number of a’s = number of b’s = number of c’s)
i.e., (L_{1} ∩ L_{2}) = {a^{n}b^{n}c^{n}  n ≥ 0} which is CSL.
Strings in L_{2} = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L_{1} ∪ L_{2} ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L_{1} ∪ L_{2}) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L_{1} ∪ L_{2}) is CFL.
Strings in L_{1} ∩ L_{2} = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L_{1} ∩ L_{2}) will have (number of a’s = number of b’s = number of c’s)
i.e., (L_{1} ∩ L_{2}) = {a^{n}b^{n}c^{n}  n ≥ 0} which is CSL.
Question 4 
Let L_{1}, L_{2} be any two contextfree languages and R be any regular language. Then which of the following is/are CORRECT?
I, II and IV only  
I and III only  
II and IV only  
I only 
Question 4 Explanation:
Since CFL is closed under UNION so L_{1} ∪ L_{2} is CFL, is a true statement.
CFL is not closed under complementation.
So L_{1} compliment may or may not be CFL. Hence is Context free, is a false statement.
L_{1} – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L_{1} ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L_{1}∩R is context free.
CFL is not closed under INTERSECTION, so L_{1} ∩ L_{2} may or may not be CFL and hence IV^{th} is false.
CFL is not closed under complementation.
So L_{1} compliment may or may not be CFL. Hence is Context free, is a false statement.
L_{1} – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L_{1} ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L_{1}∩R is context free.
CFL is not closed under INTERSECTION, so L_{1} ∩ L_{2} may or may not be CFL and hence IV^{th} is false.
Question 5 
Consider the following languages:

L_{1} = {a^{p}│p is a prime number}
L_{2} = {a^{n} b^{m} c^{2m}  n ≥ 0, m ≥ 0}
L_{3} = {a^{n} b^{n} c^{2n} │ n ≥ 0}
L_{4} = {a^{n} b^{n} │ n ≥ 1}
Which of the following are CORRECT?

I. L_{1} is contextfree but not regular.
II. L_{2} is not contextfree.
III. L_{3} is not contextfree but recursive.
IV. L_{4} is deterministic contextfree.
I, II and IV only  
II and III only  
I and IV only  
III and IV only 
Question 5 Explanation:
L_{1} = {a^{p}│p is a prime number} is a context sensitive language. So I is false.
L_{2} = {a^{n} b^{m} c^{2m}│n ≥ 0, m ≥ 0} is a context free as we have to do only one comparison (between b’s and c’s) which can be done by using PDA, so L^{2} is Context free and II is true.
L_{3} = {a^{n} b^{n} c^{2n}│n≥0} is context sensitive.
The reason it has more than one comparison (at a time) as we have to compare number of a’s, b’s and c’s.
So this cannot be done using PDA. Hence III is CSL and every CSL is recursive, so III is True
L_{4} = {a^{n} b^{n}│n ≥ 1} is Context free (as well as Deterministic context free).
We can define the transition of PDA in a deterministic manner.
In beginning push all a’s in stack and when b’s comes pop one “a” for one “b”.
If input and stack both are empty then accept.
L_{2} = {a^{n} b^{m} c^{2m}│n ≥ 0, m ≥ 0} is a context free as we have to do only one comparison (between b’s and c’s) which can be done by using PDA, so L^{2} is Context free and II is true.
L_{3} = {a^{n} b^{n} c^{2n}│n≥0} is context sensitive.
The reason it has more than one comparison (at a time) as we have to compare number of a’s, b’s and c’s.
So this cannot be done using PDA. Hence III is CSL and every CSL is recursive, so III is True
L_{4} = {a^{n} b^{n}│n ≥ 1} is Context free (as well as Deterministic context free).
We can define the transition of PDA in a deterministic manner.
In beginning push all a’s in stack and when b’s comes pop one “a” for one “b”.
If input and stack both are empty then accept.
Question 6 
Consider the following languages:

L_{1} = {a^{n} b^{m} c^{n+m} : m,n ≥ 1}
L_{2} = {a^{n} b^{n} c^{2n} : n ≥ 1}
Which one of the following isTRUE?
Both L_{1} and L_{2} are contextfree.  
L_{1} is contextfree while L_{2} is not contextfree.  
L_{2} is contextfree while L_{1} is not contextfree.  
Neither L_{1} nor L_{2} is contextfree. 
Question 6 Explanation:
L_{1} can be recognized by PDA, we have to push a’s and b’s in stack and when c’s comes then pop every symbol from stack for each c’s.
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L_{2} can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1^{st} comparison:
number of a’s = number of b’s
2^{nd} comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L_{2} can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1^{st} comparison:
number of a’s = number of b’s
2^{nd} comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
Question 7 
L_{1} and L_{2} only  
L_{1} and L_{3} only  
L_{2} and L_{3} only  
L_{3} only 
Question 7 Explanation:
L_{1}: First push all the a's in the stack then push all the b's in the stack. Now pop all the b's from the stack watching next no. of a's. And then pop all the a's from the stack watching next no. of b's. So can be done by PDA, hence CFL.
L_{2}: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.
L_{3}: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
L_{2}: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.
L_{3}: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Question 8 
Only L2 is context free  
Only L2 and L3 are context free  
Only L1 and L2 are context free  
All are context free 
Question 8 Explanation:
All languages viz L1, L2, L3 and L4 has only one comparison and it can be accepted by PDA (single stack), hence all are Context Free Languages.
Question 9 
S → aSabSbab; The language generated by the above grammar over the alphabet {a,b} is the set of
All palindromes.  
All odd length palindromes.  
Strings that begin and end with the same symbol.  
All even length palindromes. 
Question 9 Explanation:
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 10 
L_{1} only  
L_{3} only
 
L_{1} and L_{2}
 
L_{2} and L_{3}

Question 10 Explanation:
L_{1} can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L_{1}.
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
Question 11 
L_{1} is a deterministic CFL
 
L_{2} is a deterministic CFL
 
L_{3} is a CFL, but not a deterministic CFL
 
L_{3} is a deterministic CFL 
Question 11 Explanation:
Given: L_{1} = {ww^{R}  w ∈ {0,1}*}
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
Question 12 
L_{1} ∩ L_{2} is a contextfree language  
L_{1} ∪ L_{2} is a contextfree language
 
L_{1} and L_{2} are contextfree languages
 
L_{1} ∩ L_{2} is a context sensitive language

Question 12 Explanation:
CFL is closed under Union.
CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
Question 13 
Contextfree languages are closed under:
Union, intersection  
Union, Kleene closure  
Intersection, complement  
Complement, Kleene closure

Question 13 Explanation:
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
By checking the options only option B is correct.
Question 14 
the set of all binary strings with unequal number of 0’s and 1’s  
the set of all binary strings including the null string
 
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
 
None of the above 
Question 14 Explanation:
(B) is the answer. Because for any binarystring of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 15 
the sentence if a then if b then c:=d  
the left most and right most derivations of the sentence if a then if b then c:=d give rise top different parse trees  
the sentence if a then if b then c:=d else c:=f has more than two parse trees  
the sentence if a then if then c:=d else c:=f has two parse trees 
Question 15 Explanation:
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
Question 16 
The intersection of two CFL's is also a CFL.
True  
False 
Question 16 Explanation:
Context free language is not closed under intersection.
There are 16 questions to complete.