Test: Context-Free Language - Computer Science Engineering (CSE) MCQ

L1 = {0ⁱ1^j | i ≠ j} → Context free
A regular expression for this is (0*1*)
A language that generates a regular expression is called regular language that is accepted by deterministic finite automata(DFA) can also be accepted by PDA
So, this language is also a context-free language
L2 = {0ⁱ1^j | i = j} → Context free
First, push 0 into a stack then pop 0 for each 1 from the stack. The given language is accepted by
Deterministic Pushdown Automaton. Therefore, L2  is deterministic context-free.
L3 = {0ⁱ1^j | i = 2j + 1} → Context free
If first 0 came then do nothing and for others 0's, for each zero push two 0's on the stack, and when 1 comes then pop two 0's for each 1 from the stack.
here pushing two 0's sounds non-deterministic but we push one symbol on the stack so it is deterministic
So, the given language is accepted by
Deterministic Pushdown Automaton. Therefore, L₂  is deterministic context-free.
L4 = {0ⁱ1^j | i ≠ 2j} → Context-free
let's take i = 2j +1
so it becomes as language L3
So, the given language is accepted by
Deterministic Pushdown Automaton. Therefore, L2  is deterministic context-free.
So, all the language are context-free

L₁ = {aⁱb^j c^k | i < j < k} is not context free
We can prove this using the pumping lemma also let pumping constant = n
String S = aⁿ bⁿ⁺¹ cⁿ⁺²∈L
Let S = uvwxy where |vx| ≥1 and |vwx| ≤n

Cases :

• vwx is in aⁿ : for i = 2, S¹ = uvⁱwxⁱy has more or equal a’s than b’s ⇒ S¹∉L
• vwx is in bⁿ : for i = 0, S¹ = uvⁱwxⁱy has more or equal a’s than b’s ⇒ S¹∉ L
• vwx is in cⁿ : for i = 0, S¹ = uvⁱwxⁱy has more or equal b’s than c’s ⇒ S¹∉ L
• vwx contains both a and b i.e. aⁿ bⁿ⁺¹ :
• Since x has atleast one b, for i = 2, S¹ = uviwxiy has more b’s than c’s ⇒ S¹∉ L
• vwx contains both b and c i.e. bⁿ⁺¹ cⁿ⁺² since v has atleast one b, for i = 0,

S¹ = uviwxi y has more or equal a’s than b’s ⇒ S¹∉ L                              
So we can say that by pumping lemma, given language is not CFL.
L₂ = {am bn | m ≠n and m ≠2n} is CFL
L₂ can be define as  L₂₁ = {am bn | m < n}
L₂₂ = {am bn | n < m < 2n}
L₂₃ = {am bn | m > 2n}
So, L₂ = L₂₁∪L₂2∪L₂₃
As there exists CFGs for L₂₁, L₂₂ and L₂₃ and since union of CFL’s is a CFL. Thus L₂ is CFL.

Concepts:
Operation under which context-free language is not closed: Intersection, complementation, set difference
Operation under which context-free language is closed: Union, Kleene Closure, and Concatenation.
Context-free language is closed under Intersection with regular language.

L₁ is a regular and L₂ is a context-free language.
Every regular language is context-free language.

Option 1: context-free language
L₁.L₂ it is the context-free language because it is closed under Concatenation.

Option 2: context-free language
L₁ ∪ L₂ it is the context-free language because it is closed under Union.

Option 3: context-free language
L₁∩L₂ it is the context-free language because context-free language is closed under Intersection with regular language.

Option 4: may not be context-free language
L₁ - L₂  it may not be context-free language because it is not closed under complementation.

Statement I: L₁ = {aⁿ b^m c^{n + m}: m, n ≥ 1}
L₁ 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: L₂ = {aⁿbⁿc²ⁿ: 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 L₂ is a context sensitive language but not context free language.

• {waⁿbⁿw^R |w ∈ {a, b}*, n ≥ 0} is accepted by a non-deterministic pushdown automaton and hence it is a context-free language
• {ww^R |w ϵ {a, b}*} is accepted by a non-deterministic pushdown automaton and hence it is context-free language.
• {waⁿw^Rbⁿ|w ∈ {a, b}*, n ≥ 0} is not accepted by a pushdown automaton and hence it is not a context-free language.
• i = n, 2n, 3n, 4n, etc. forms and arithmetic series. aⁿbⁿ, aⁿb²ⁿ and aⁿb³ⁿ is accepted by a deterministic pushdown automaton and context-free language are closed under union and hence aⁿbⁿ ∪ aⁿb²ⁿ ∪ aⁿb³ⁿ is a context-free language. Hence {aⁿbⁱ |i ∈ {n, 3n, 5n}, n ≥ 0} is a context-free language.

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.

• If the NP-Hard problem is reducible to another problem in polynomial time, then that problem is also NP-hard which means every NP problem can be reduced to this problem in polynomial time.
• If Q is reducible to S in polynomial time, Q could be NP because all NP problems can be reduced to S. Since Q could be Np therefore Q could be P also as P is a subset of NP. Also, Q could be NPC because every NPC problem can be reduced to another NPC problem in polynomial time. 

Concept:
The given grammar is,
L1 = {aⁿ|n ≥ 1} 
It regular grammar, 


L2 = {bⁿaⁿ|n ≥ 1}
It is not regular but DCFL because we need to compare a number of b's with the number of a's so we need one stack for comparisons.
L3 = {0ⁿ1^m |n = 2m, n,m ≥ 0}
It is not regular but DCFL because we need to compare a number of b's with the number of a's so we need one stack for comparisons.
L4 = {a^p|p is odd number}
It regular grammar,

(i) Complement of L1 is also regular.
True, L1 is regular so complement is also regular and every regular is context-free so it is true.
(ii) Union of L2 and L3 is also CFL
True, the Union of two CFLs is also CFL by closure property.
(iii) Intersect of L1 and L4 is also CFL
True, L1 and L4 both are regular and the intersection of regular is also regular and every regular is CFL.
(iv) Concatenation of L1 and L2 is also CFL.
True, the Concatenation of two CFLs is always CFL.

Option 1: L₁ is not context-free but L₂ and L₃ are deterministic context-free. 
True, L₁ is not context-free and L₂ and L₃ are clearly DCFLs since they have only one comparison and DPDA can accept both.

Option 2: Neither L₁ nor L₂ is context-free.
False, L₂ is DCFL and every DCFL is a CFL.
L₂ - Context-free.
L₃ - Context-free.
L₂ ∩ L₃ = {anbncn or ambmcm , m, n > = 0}
This language is context sensitive language.

Option 3: L₂, L₃ and  L₂ ∩ L₃ all are context-free.
False, 
L₂ - Context-free.
L₃ - Context-free.
L₂ ∩ L₃ = {anbncn, n > = 0} We can not compare the anbncn  with one single stack. Hence it is not context-free.

Option 4: Neither L₁ nor its complement is context-free.
False, L₁ - Not context-free.
L1' Complement of L₁ is accepted by a context-free grammar is CFL.
Hence the correct answer is option 2, option 3 and option 4.

Statement I: TRUE.
L = {aⁿ |n ≥ 0} ∪ {aⁿbⁿ| n ≥ 0}
{aⁿ |n ≥ 0} is a regular language and {aⁿbⁿ| 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 aⁿbⁿ. Both have a common prefix.