## topic

## Context-Free-Language

Question 1 |

L 1 and L 2 are regular. | |

L 1 and L 2 are context-free. | |

L 1 is regular and L 2 is context-free. | |

L 1 and L 2 are context-free but not 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 2 |

L 1 is not context-free but L 2 and L 3 are deterministic context-free. | |

Neither L 1 nor L 2 is context-free. | |

Neither L 1 nor its complement is context-free. |

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 3 |

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

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 4 |

The grammar whose productions are

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

is ambiguous because

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 |

"if a then if b then c:=d else c:=f".

__Parse tree 1__:

__Parse tree 2__:

Question 5 |

Context-free languages are closed under:

Union, intersection | |

Union, Kleene closure | |

Intersection, complement | |

Complement, Kleene closure |

By checking the options only option B is correct.

Question 6 |

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.

Theory Explanation. |

Question 7 |

Consider the languages:

L_{1}= {a^{n}b^{n}c^{m}|n,m > 0} and L_{2}= {a^{n}b^{m}c^{m}|n,m > 0}

Which one of the following statements is FALSE?

L _{1} ∩ L_{2} is a context-free language | |

L _{1} ∪ L_{2} is a context-free language | |

L _{1} and L_{2} are context-free languages | |

L _{1} ∩ L_{2} is a context sensitive language |

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 context-free.

Question 8 |

Consider the languages:

L_{1}= {ww^{R}|w ∈ {0,1}*} L_{2}= {w#w^{R}| w ∈ {0,1}*}, where # is a special symbol L_{3}= {ww | w ∈ (0, 1)*}

Which one of the following is TRUE?

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 |

_{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. (✔️)

Question 9 |

Let L_{1} = {0^{n+m}1^{n}0^{m}|n,m ≥ 0}, L_{2} = {0^{n+m}1^{n+m}0^{m}|n,m ≥ 0}, and L_{3} = {0^{n+m}1^{n+m}0^{n+m}|n,m ≥ 0}. Which of these languages are NOT context free?

L _{1} only | |

L _{3} only | |

L _{1} and L_{2} | |

L _{2} and L_{3} |

_{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.

Question 10 |

^{R}to be the reverse of w. For example, if w = 01101 then w

^{R}= 10110. Which of the following languages is/are context-free?

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

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

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

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

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).

Question 11 |

_{1}be a regular language and L

_{2}be a context-free language. Which of the following languages is/are context free

Question 12 |

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

True | |

False |

Question 13 |

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 is

**TRUE**?

Both L _{1} and L_{2} are context-free. | |

L _{1} is context-free while L_{2} is not context-free. | |

L _{2} is context-free while L_{1} is not context-free. | |

Neither L _{1} nor L_{2} is context-free. |

_{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.

Question 14 |

Let L_{1}, L_{2} be any two context-free 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 |

_{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.