GATE Computer Science Engineering(CSE) 2027 Test: Identify Class Language

A suitable way to see that LLL is regular is to observe that “avoiding a fixed forbidden substring” (here, “0011”) can be recognized by a finite automaton that remembers at most the last three symbols seen. Concretely, you build a DFA whose states record how much of the prefix “001” has just been seen; whenever “0011” would be completed, the DFA rejects. Hence LLL is accepted by a finite automaton, so it is regular. In other words, the correct choice is:

(b) LLL is regular.

Option A is correct.

L1 - L2 = L1 ∩ ~L2, so the difference can be written as an intersection of a context-free language with the complement of a regular language.

Regular languages are closed under complement; therefore ~L2 is regular.

Context-free languages are closed under intersection with regular languages; hence L1 ∩ ~L2 is context-free. Thus the statement "L1 - L2 is not context free" is false.

Context-free languages are not closed under complement in general; therefore ~L1 need not be context-free, so the statement "~L1 is context free" is also false.

Consequently, statements a and c are the false ones, while b and d are true; this corresponds to Option A.

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]

Answer: A

L1 is context-free. Observe that L1 = {aⁿb^{n · {cm}, where {anbn is a standard CFL and {cm} is regular; concatenation of a CFL with a regular language is a CFL.}

L2 is context-free. Similarly L2 = {a^{n · {bmcm, where {bmcm is a CFL and {an} is regular; their concatenation is a CFL.}

The intersection L1 ∩ L2 equals {aⁿbⁿcⁿ | n > 0}, because membership requires the number of a's, b's and c's to be equal.

It is a standard result that {aⁿbⁿcⁿ | n > 0} is not context-free (for example, by the pumping lemma for context-free languages). Therefore L1 ∩ L2 is not a CFL, so any statement asserting that this intersection is context-free is false.

Other statements (that each of L1 and L2 is CFL, and that union gives a CFL) are true. Hence Option A is the false statement.

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)

• For any finite n, the language is simply a finite set of strings (here, 106 strings).

• Any finite language is regular (since you can construct a finite automaton with a separate path for each string)

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.