Test: Identify Class Language - Computer Science Engineering (CSE) MCQ

L is regular.

• Given L1 is a context free language and L2 as a regular language then L1-L2 is context free language and
• ~L1(complement of context free) is not context free because context free is not closed under complement.
• Complement of regular language i.e. ~L2 is also regular ( so d is correct ) since statements a and c are false.

Hence,Option (C) is correct.

Language generated by this grammar is L = (00)^+ that is regular but not 0^+

With only finite positions in stack, we can have only finite configurations and these can also be modeled as states in a finite
automata.

Language is not regular bcoz we need to match count of c's is equal to count of b's + count of a's

and that can implement by PDA

∂(q0,a,^)= (q0,a) [ push a in stack, as per language a comes first]

∂(q0,a,a)= (q0,aa) [push all a's into stack]
∂(q0,b,a) = (q1,ba) [push b in stack, state change to q1 that sure b comes after a]
∂(q1,b,b)=(q1,bb) [push all b's in stack]
∂(q1,c,b) = (q2,^) [ pop one b for one c]

∂(q2,c,b) = (q2,c) [ pop one b's for each c and continue same ]
∂(q2,c,a) = (q3,^) [ pop one a for one c , when there is no more b in stack]
∂(q3,c,a) = (q3,^) [pop one a for each c and continue same]
∂(q3,^,^) = (qf,^) [ if sum of c's is sum of a's and b's then stack will be empty when there is no c in input]

Note :1. state changes make sure b's comes after a and c's comes after b's]

L1 is CFL [ put a's in stack, and pop a with each b]]
L2 is CFL [put b's in stack and pop b with each c ]
c) is True.

b) is True CFL is closed under Union [ S-> S1 | S2 where S1 is grammar for L1 and S2 for L2]
CFL is not closed under Intersection, so intersection of two CFLs may or may not be CFL.

Let's examine:
L1 ∩ L2 = { aⁱbⁱcⁱ , i>0 } which is Context sensitive but not context free [can't match a's,b's and c's with one stack]
So a) is False

d) is True

Take L = Σ* then Lc = ∅ and Mc ∪ ∅ = M^c.

We know that complement of CFL need not be a CFL as CFL is not closed under complement

So, (A) and (B) are false.

If we take L = ∅ then L^c = Σ* and M^c ∪ Σ* = Σ* which is regular - (C) is also false.

So, answer (D)

The language $L = \{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ is a set of strings where:

• The string consists of exactly $n$ zeros, followed by $n$ ones, followed by $n$ twos,
• $n$ is a positive integer such that $1 \leq n \leq 10^6$.

This type of language is not regular, because it cannot be recognized by a finite automaton. The key reason for this is that the strings have the form $0^n 1^n 2^n$, where the number of zeros, ones, and twos must be the same, and this kind of structure requires the ability to "count" and compare different parts of the string (the number of zeros, ones, and twos), which finite automata cannot do.

Why is it not regular?

We can prove that the language is not regular using the pumping lemma for regular languages. The pumping lemma states that for a regular language, there exists a "pumping length" $p$ such that any string in the language longer than $p$ can be split into three parts $xyz$ with the following properties:

1. $|xy| \leq p$,
2. $|y| > 0$,
3. For all $i \geq 0$, the string $xy^i z$ must also be in the language.

Consider a string $w = 0^p 1^p 2^p$ in the language $L$, where $p$ is the pumping length. The pumping lemma tells us that we can split $w$ into parts $xyz$, where $y$ is non-empty. However, no matter how we split the string, pumping the $y$-section (repeating it) will disrupt the balance between the numbers of 0's, 1's, and 2's, and the resulting string will no longer be in the language. Hence, this language does not satisfy the pumping lemma, so it is not regular.

Is the language context-free?

The language is also not context-free. A context-free grammar can generate languages with balanced structures, but this language requires counting and matching three different symbols in a very specific order, which cannot be done by a context-free grammar. We can prove this using the pumping lemma for context-free languages, which would similarly show that this language does not meet the required conditions for context-freeness.

Conclusion:

The language $L = \{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ is not regular and not context-free.

L1 = { s∈(0+1)* ∣ d(s) mod 5=2 } is regular having 2 as final state out of {0,1,2,3,4} states as given in example in posted link [in same DFA , final state will be 2 instead of 0 ]

Similarly L2 = { s∈(0+1)* ∣ d(s) mod 7≠4 } is also regular having states {0,1,2,3,4,5,6} and all are final state except 4
L1 ∩ L2 is L (given problem ) is also regular
As regular languages are closed under intersection.

Hence, D is the correct option.

A. True: DCFL are closed under Intersection with Regular Languages
C. True: L1 is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
D. True: L1 is regular hence also RE; L2 is DCFL hence also RE; RE languages are closed under Intersection
B. False: L1 is recursive hence also decidable, L3 is RE but not Recursive hence it is undecidable. Intersection of Recursive
language and Recursive Enumerable language is Recursive Enumerable language.