Context free languages are closed under MCQ

Closure Properties of Context Free Languages Question 1:

The class of Context-free grammar is not closed under _______operations.

1. Intersection
2. Homomorphism
3. Substitution
4. Complement

Answer (Detailed Solution Below)

Option :

Answer: Option 1, Option 2

Concept:

Context-free languages are closed under Homomorphism and Substitution

CFLs are NOT closed under intersection and not closed under complementation.

Explanation: 

Example:

L1 = pn qn rm | m, n > 0 → CFL

L2 = pm qn rn  | m, n > 0 → CFL

L = pn qn rm ∩ pm qn rn  | m, n > 0. L = pn qn rn it is not accepted by a pushdown automaton and hence it is not a CFL. and hence it is not closed under intersection.

Closure Properties of Context Free Languages Question 2:

Context free grammar is not closed under:

1. Concatenation
2. Complementation
3. Kleene Star
4. Union

Answer (Detailed Solution Below)

Option 2 : Complementation

Concept:

Context free languages are closed under Union, Concatenation and Kleene Closure (star)

CFLs are NOT closed under intersection and not closed under complementation

Example:

L1 = pn qn rm | m, n > 0 → CFL

L2 = pm qn rn  | m, n > 0 → CFL

L = pn qn rm ∩ pm qn rn  | m, n > 0. L = pn qn rn it is not accepted by pushdown automaton and hence it is not a CFL. and hence it is not closed under intersection.

Important Point:

Closure Properties of Context Free Languages Question 3:

Consider the following statements with respect to the language L = {anbn |n≥ 0}

S1 : L2 is context free language

S2 : Lk is context-free language for any given k ≥ 1

S3 : L̅ and L* are context free languages

Which one of the following is correct?

1. only S1 and S2
2. only S1 and S3
3. only S2 and S3
4. S1, S2 and S3

Answer (Detailed Solution Below)

Option 4 : S1, S2 and S3

Statement S1: L2 is context free language – True

L2 means L.L which will give the language {anbn anbn |n≥ 0} and this is context free language.

Statement S2: Lk is context-free language for any given k ≥ 1 – True

Lk is context-free language because CFLs are closed under kleene closure.

Statement S3: L̅ and L* are context free languages – True

L̅ is a DCFL because L is a DCFL. L̅ is a language that accepts all inputs on a and b except anbn and this is easily determined by a PDA.

L* is a CFL because CFLs are closed under kleene closure.

Important Point:

Deterministic Context free language is closed under complementation

Closure Properties of Context Free Languages Question 4:

Context free languages are closed under

1. union, intersection
2. union, Kleene closure
3. intersection, complement
4. complement, Kleene closure

Answer (Detailed Solution Below)

Option 2 : union, Kleene closure

Concept:

Context free languages are closed under Union and Kleene Closure

CFL is not closed under intersection and not closed under complementation

Hence, only option 2 matches

Important Points:

Closure Properties of Context Free Languages Question 5:

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.

I. L is deterministic context-free.

II. L is context-free but not deterministic context-free.

III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

1. I only
2. II only
3. I and III only
4. III only

Answer (Detailed Solution Below)

Option 3 : I and III only

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.

Top Closure Properties of Context Free Languages MCQ Objective Questions

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.

I. L is deterministic context-free.

II. L is context-free but not deterministic context-free.

III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

1. I only
2. II only
3. I and III only
4. III only

Answer (Detailed Solution Below)

Option 3 : I and III only

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.

Context free languages are closed under

1. union, intersection
2. union, Kleene closure
3. intersection, complement
4. complement, Kleene closure

Answer (Detailed Solution Below)

Option 2 : union, Kleene closure

Concept:

Context free languages are closed under Union and Kleene Closure

CFL is not closed under intersection and not closed under complementation

Hence, only option 2 matches

Important Points:

Consider the following languages:

L1 = {anbmcn + m: m, n ≥ 1}

L2 = {anbnc2n: n ≥ 1}

Which one of the following is TRUE?

1. Both L1 and L2 are context-free
2. L1 is context-free while L2 is not context-free
3. L2 is context-free while L1 is not context-free
4. Neither L1 nor L2 is context-free

Answer (Detailed Solution Below)

Option 2 : L1 is context-free while L2 is not context-free

Statement I: L1 = {an bm cn + m: m, n ≥ 1}

L1 can be accepted easily by single stack. First, push a’s into stack, then push b’s into stack then read c’s and pop b’s, when no b’s left on stack, then keep reading c’s and pop a’s. When no c’s left in input and stack is empty then accepted by only one stack. Hence L1 is a context free language.

Statement II: L2 = {anbnc2n: n ≥ 1}

This language can’t be accepted by a single stack. When we push a’s into stack and pop them with b’s then it satisfies number of a’s = number of b’s but we left with empty stack and c’s in input. We can’t ensure that number of c’s are double than a and b’s. A push down automata can’t remember number of a’s for third set of characters, that is. c.

Hence L2 is a context sensitive language but not context free language.

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L̅1 (complement of L1) is recursive

II. L̅2 (complement of L2) is recursive

III. L̅1 is context-free

IV. L̅1 ∪ L2 is recursively enumerable

1. I only
2. III only
3. III and IV only
4. I and IV only

Answer (Detailed Solution Below)

Option 4 : I and IV only

Properties:

Context free language is not closed under complementation.

Recursively enumerable language is not closed under complementation.

Recursively enumerable language is closed under union.

Recursive languages are closed under complementation.

Explanation:

L1: Context-free

L2: recursively enumerable but not recursive

Statement I:

L̅1 (complement of L1) is recursive → TRUE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursive language.

Statement II:

L̅2 (complement of L2) is recursive → FALSE

Since recursively enumerable language (L2) is not closed under complementation. Therefore, L̅2 is not recursively enumerable language. If a language is not recursively enumerable then it cannot be recursive for sure. Since recursive language is subset of recursively enumerable language.

Statement III:

L̅1 is context-free → FALSE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Statement IV: → TRUE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursively enumerable language.

Also, recursively enumerable language is closed under union. Therefore, L̅1 ∪ L2 is recursively enumerable.

Context free grammar is not closed under:

1. Concatenation
2. Complementation
3. Kleene Star
4. Union

Answer (Detailed Solution Below)

Option 2 : Complementation

Concept:

Context free languages are closed under Union, Concatenation and Kleene Closure (star)

CFLs are NOT closed under intersection and not closed under complementation

Example:

L1 = pn qn rm | m, n > 0 → CFL

L2 = pm qn rn  | m, n > 0 → CFL

L = pn qn rm ∩ pm qn rn  | m, n > 0. L = pn qn rn it is not accepted by pushdown automaton and hence it is not a CFL. and hence it is not closed under intersection.

Important Point:

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

I. L1 ∪ L2 is context-free

II. L̅1 is context-free

III. L1 – R is context-free

IV. L1 ∩ L2 is context-free

1. I, II and IV only
2. I and III only
3. II and IV only
4. I only

Answer (Detailed Solution Below)

Option 2 : I and III only

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct.

Option 2).  L̅1 is context-free

L1 is a context-free language. According to the property, its complement can’t be context-free.

Option 3) L1 – R is context-free

As the difference of a context-free language with regular is context-free. So, it is correct.

Option 4) L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect. 

Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?

I. L̅3 ∪ L4 is recursively enumerable

II. L̅2 ∪ L3 is recursive

III. L1* ∩ L2 is context-free 

IV. L1 ∪ L̅2 is context-free

1. I only
2. I and III only
3. I and IV only
4. I, II and III only

Answer (Detailed Solution Below)

Option 4 : I, II and III only

L1: Regular

L2: Context-free

L3: Recursive

L4: Recursively enumerable

Statement I: TRUE

 L̅3 ∪ L4 is recursively enumerable

As L3 is recursive language and complement of a recursive language is also recursive.

L4 is recursive enumerable. So, L̅3 ∪ L4 is recursive enumerable.

Statement II: TRUE

II. L̅2 ∪ L3 is recursive

L2 is context free language. Context free languages are not closed under complementation. Complement of a context free language is context sensitive also recursive. L3 is recursive.

So, union of two recursive languages is recursive.

Statement III: TRUE

III. L1* ∩ L2 is context-free 

Kleen closure of regular language is regular. Intersection of a regular language and context free language is context free.

Example:

Regular language = \(L^*_1 = (a + b)^*\)

L2 = an bn

The intersection of \(L^*_1 \cap L_2 = a^nb^n\) is a context-free language 

Statement IV: FALSE

L1 ∪ L̅2 is context-free

Complement of L2 is not context free.  L1 ∪ L̅2 may or may not be context free.

Therefore, the statement I, II and III are correct.

The class of Context-free grammar is not closed under _______operations.

1. Union
2. Concatenation
3. Intersection
4. Star

Answer (Detailed Solution Below)

Option 3 : Intersection

Concept:

Context free languages are closed under Union and Kleene Closure

CFLs are NOT closed under intersection and not closed under complementation

Example:

L1 = pn qn rm | m, n > 0 → CFL

L2 = pm qn rn  | m, n > 0 → CFL

L = pn qn rm ∩ pm qn rn  | m, n > 0. L = pn qn rn it is not accepted by pushdown automaton and hence it is not a CFL. and hence it is not closed under intersection.

Important Point:

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

1. I, II and IV only
2. II and III only
3. I and IV only
4. III and IV only

Answer (Detailed Solution Below)

Option 4 : III and IV only

Consider the options one by one:

Option 1:

L1 = {ap | p is a prime number}

Prime numbers do not have fixed pattern. So, it is not possible to solve it using pushdown

automaton. So, L1 is not context free language.

Option 2:

L2 = {anbmc2m | n ≥ 0, m ≥ 0}

It can be solved easily using single stack.  Comparison is done between b and c. We can make a pushdown automaton for this. So, L2 is context free language.

Option 3:

L3 = {anbnc2n | n ≥ 0}

First comparison is between a and b, then between b and c, therefore two stacks are required.

So, it is context sensitive language. L3 is recursive language.

Option 4:

L4 = { anbn | n ≥ 1}

First push a into a stack then pop a for each b from the stack. The given language is accepted by

Deterministic Pushdown Automaton. Therefore, L4  is deterministic context-free.

Closure Properties of Context Free Languages Question 15:

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.

I. L is deterministic context-free.

II. L is context-free but not deterministic context-free.

III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

1. I only
2. II only
3. I and III only
4. III only

Answer (Detailed Solution Below)

Option 3 : I and III only

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.

What are context

Are context

Is context

Are context