Context-Free-Language

Question 1

Which one of the following languages over Σ = {a,b} is NOT context-free?

A
{wwR |w ∈ {a,b}*}
B
{wanwRbn |w ∈ {a,b}*, n ≥ 0}
C
{anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
D
{wanbnwR |w ∈ {a,b}*, n ≥ 0}
Question 1 Explanation: 
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
Question 2

Consider the languages

    L1 = {0i1j | i != j}.
    L2 = {0i1j | i = j}.
    L3 = {0i1j | i = 2j+1}.
    L4 = {0i1j | i != 2j}.

Which one of the following statements is true?

A
Only L2 is context free
B
Only L2 and L3 are context free
C
Only L1 and L2 are context free
D
All are context free
Question 2 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 3
Consider the following languages:
I. {am bn cp dq ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {am bn cp dq ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {am bn cp dq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {am bn cp dq ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are context-free?
A
I and IV only
B
I and II only
C
II and III only
D
II and IV only
Question 3 Explanation: 
i) am bn cp dq | 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) am bn cp dq | 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) am bn cp dq | 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 4
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G1: S → aSb|T, T → cT|ϵ
G2: S → bSa|T, T → cT|ϵ
The language L(G1) ∩ L(G2) is
A
Finite
B
Not finite but regular
C
Context-Free but not regular
D
Recursive but not context-free
Question 4 Explanation: 
Strings generated by G1:
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G2:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G1) and L (G2) are:
{ϵ, c, cc, ccc…}
So, L (G1) ∩ L (G2) can be represented by regular expression: c*
Hence the language L (G1) ∩ L (G2) is “Not finite but regular”.
Question 5
S→aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of

A
all palindromes.
B
all odd length palindromes.
C
strings that begin and end with the same symbol.
D
all even length palindromes.
Question 5 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 6

Consider the languages:

L1 = {anbncm |n,m > 0} and L2 = {anbmcm |n,m > 0}

Which one of the following statements is FALSE?

A
L1 ∩ L2 is a context-free language
B
L1 ∪ L2 is a context-free language
C
L1 and L2 are context-free languages
D
L1 ∩ L2 is a context sensitive language
Question 6 Explanation: 
CFL is closed under Union.
CFL is not closed under Intersection.
L1 = {anbncm | n>0 & m>0}
L2 = {ambncn | n>0 & m>0}
L3 = L1 ∩ L2
={anbncn | n>0} It is not context-free.
Question 7

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
Question 7 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 8

Show that the language L = {xcx| x ∈ {0,1}* and c is a terminal symbol} is not context free, c is not 0 or 1.

A
Theory Explanation.
Question 9

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
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
D
None of the above
Question 9 Explanation: 
(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.
Question 10
Consider the following languages over the alphabet Σ = {a, b, c}.
Let L1 = {an bn cm│m,n ≥ 0} and L2 = {am bn cn│m,n ≥ 0}
Which of the following are context-free languages?
I. L1 ∪ L2
II. L1 ∩ L2
A
I only
B
II only
C
I and II
D
Neither I nor II
Question 10 Explanation: 
Strings in L1 = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L2 = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L1 ∪ L2 ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L1 ∪ L2) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L1 ∪ L2) is CFL.
Strings in L1 ∩ L2 = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L1 ∩ L2) will have (number of a’s = number of b’s = number of c’s)
i.e., (L1 ∩ L2) = {anbncn | n ≥ 0} which is CSL.
Question 11

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

A
I, II and IV only
B
I and III only
C
II and IV only
D
I only
Question 11 Explanation: 
Since CFL is closed under UNION so L1 ∪ L2 is CFL, is a true statement.
CFL is not closed under complementation.
So L1 compliment may or may not be CFL. Hence is Context free, is a false statement.
L1 – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L1 ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L1∩R is context free.
CFL is not closed under INTERSECTION, so L1 ∩ L2 may or may not be CFL and hence IVth is false.
Question 12
Consider the following languages:
L1= {ap│p is a prime number}
L2= {anbmc2m| n ≥ 0, m ≥ 0}
L3= {anbnc2n│ n ≥ 0}
L4= {anbn│ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.
A
I, II and IV only
B
II and III only
C
I and IV only
D
III and IV only
Question 12 Explanation: 
L1 = {ap│p is a prime number} is a context sensitive language. So I is false.
L2 = {an bm c2m│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 L2 is Context free and II is true.
L3 = {an bn c2n│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
L4 = {an bn│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 13
Consider the following languages:
L1 = {an bm cn+m: m,n ≥ 1}
L2= {an bn c2n: n ≥ 1}
Which one of the following is TRUE?
A
Both L1 and L2 are context-free.
B
L1 is context-free while L2 is not context-free.
C
L2 is context-free while L1 is not context-free.
D
Neither L1 nor L2 is context-free.
Question 13 Explanation: 
L1 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 L2 can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1st comparison:
number of a’s = number of b’s
2nd comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
Question 14

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
Question 14 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 15

The intersection of two CFL's is also a CFL.

A
True
B
False
Question 15 Explanation: 
Context free language is not closed under intersection.
There are 15 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access