(B) is the answer. Because for any binary string 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.

We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:

Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.

Option A: L={w x w^R  x^R  | w, x ∈ {0,1}* }

This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.

 

Option B: L={w w^R x x^R  | w, x ∈ {0,1}* }

This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR  and again push x and match with xR  

 

Option C: L={w x  x^R w^R   | w, x ∈ {0,1}* } 

This is also CFL. We non deterministically guess the middle of the string. So we push “w” then push x and then  match with xR  and again match with wR 

 

Option D: L={w x  w^R   | w, x ∈ {0,1}* }

This is a regular language (hence CFL). In this language every string start and end with same symbol (as x can expand).

L1=ww is a well-known CSL (non-CFL) and its complement is CFL.
L2={an bn cm | m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn | m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn | n >=0} so this is CSL (non-CFL).
So A is a true statement and rest all are false statements.

Both L1 and L2 are regular.
Since no condition on the value of “n” is mentioned so for a particular case we can assume n=0, now when n=0 the language L1= w =(a+b)*
So if one case is (a+b)* then now even we assume any value of “n” the generated string will already present in (a+b)* thus L1=(a+b)*.
L2: In L2 the middle X can expand and consume all symbols of w except the first symbol and symbols of wr except the last symbol so L2 will be equivalent to language all strings start and end with the same symbol, hence L2 is regular.

Context free language is not closed under intersection.

L₁ 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₂ 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.

L₁ = {a^p│p is a prime number} is a context sensitive language. So I is false.
L₂ = {aⁿ 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² is Context free and II is true.
L₃ = {aⁿ bⁿ c²ⁿ│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₄ = {aⁿ bⁿ│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.

Since CFL is closed under UNION so L₁ ∪ L₂ is CFL, is a true statement.
CFL is not closed under complementation.
So L₁ compliment may or may not be CFL. Hence is Context free, is a false statement.
L₁ – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L₁ ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L₁∩R is context free.
CFL is not closed under INTERSECTION, so L₁ ∩ L₂ may or may not be CFL and hence IV^th is false.

Strings in L₁ = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L₂ = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L₁ ∪ L₂ ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L₁ ∪ L₂) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L₁ ∪ L₂) is CFL.
Strings in L₁ ∩ L₂ = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L₁ ∩ L₂) will have (number of a’s = number of b’s = number of c’s)
i.e., (L₁ ∩ L₂) = {aⁿbⁿcⁿ | n ≥ 0} which is CSL.

Strings generated by G₁:
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G₂:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G₁) and L (G₂) are:
{ϵ, c, cc, ccc…}
So, L (G₁) ∩ L (G₂) can be represented by regular expression: c*
Hence the language L (G₁) ∩ L (G₂) is “Not finite but regular”.

i) a^m bⁿ c^p d^q | m+p = n+q,
m-n = q-p
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ⁿ 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ⁿ 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.