Context-Free-Language

Question 1

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 1 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 2

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 2 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 3

Context-free languages are closed under:

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

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 5
 For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR= 10110. Which of the following languages is/are context-free?
A
L={w x wR xR | w, x ∈ {0,1}* }
B
L={w wR x xR | w, x ∈ {0,1}* }
C
L={w x xR wR | w, x ∈ {0,1}* }
D
L={w x wR | w, x ∈ {0,1}* }
Question 5 Explanation: 

Option A: L={w x wR  xR  | 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 wR x xR  | 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  xR wR   | 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  wR   | 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).



Question 6
Let L1be a regular language and L2be a context-free language. Which of the following languages is/are context free
A
B
C
D
Question 6 Explanation: 
Question 7

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

A
True
B
False
Question 7 Explanation: 
Context free language is not closed under intersection.
Question 8
A
L 1 and L 2 are regular.
B
L 1 and L 2 are context-free.
C
L 1 is regular and L 2 is context-free.
D
L 1 and L 2 are context-free but not regular.
Question 8 Explanation: 
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.
Question 9
Consider the following languages:
A
L 1 is not context-free but L 2 and L 3 are deterministic context-free.
B
Neither L 1 nor L 2 is context-free.
C
D
Neither L 1 nor its complement is context-free.
Question 9 Explanation: 
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.
Question 10

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 10 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 11

Consider the languages:

L1 = {wwR |w ∈ {0,1}*}
L2 = {w#wR | w ∈ {0,1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1)*}

Which one of the following is TRUE?

A
L1 is a deterministic CFL
B
L2 is a deterministic CFL
C
L3 is a CFL, but not a deterministic CFL
D
L3 is a deterministic CFL
Question 11 Explanation: 
Given: L1 = {wwR | w ∈ {0,1}*}
→ Given L1 is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L2 = {w#wR | w ∈ (0,1)*}
→ Given L2 is CFL and also DCFL.
→ The string w and wR are separated by special symbol '#'.
→ L3 = {ww | w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L2 is DCFL. (✔️)
Question 12

Which of the following languages are context-free?

    L1 = {ambnanbm ⎪ m, n ≥ 1}
    L2 = {ambnambn ⎪ m, n ≥ 1}
    L3 = {ambn ⎪ m = 2n + 1}
A
L1 and L2 only
B
L1 and L3 only
C
L2 and L3 only
D
L3 only
Question 12 Explanation: 
L1: 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.
L2: 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 comparison with the next b's. So not CFL.
L3: 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 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

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 14 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.
There are 14 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