L1: regular language
L2: context free language
L3: context sensitive language

The strings in L₁ are { c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L₂ are { ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L₁ ∩ L₂ is {a^xb^x | x ≥0}, which is CFL but not regular.

Finding prime number cannot be done by FA or PDA , so it cannot be regular or CFL. This language can be recognized by LBA , hence it can be accepted by Turing Machine.

→ Both L₁ and L₂ are CFL. So option A is false.
→ L₁ ∩ L₂ = ∅, True and also L1 is non-regular. Option B is true.
→ L₁ ∪ L₂ is not a CFL but L₂ is CFL is closed under union. So option C is false.
→ Both L₁ and L₂ accepted by DPDA.

L₁ and L₃ are regular.
L₁ is limited to fixed range and L₃ contains even number of 0's which is regular. No need to use more memory to implement L₃.

We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.

Regular grammar is either right linear or left linear. A left linear grammar is one in which there is atmost 1 non-termial on the right side of any production, and it appears at the left most position.
Similarly, in right linear grammar, non-terminal appears at the right most position.
Here we can write a right linear grammar for G₁ as
S → w(E
E → id)S
S → o
(w-while, o-other)
So, L(G₁) is regular.
Now for G₂ also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G₁ and G₂ have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.

Let L₁ = {s ∈ (0 + 1)* | d(s) mod5 = 2}, we can construct the DFA for this which will have 5 states (remainders 0,1,2,3,4)
L₂ = {s ∈ (0 + 1)* | d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L₁ and L₂ have DFAs, hence they are regular. So the resulting Language.
L = L₁ ∩ L₂ (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).

Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L₁ ∩ L₂ is a deterministic CFL.
Option B is false, as L₃ is recursive enumerable but not recursive, so intersection with L₁ must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L₁ ∪ L₂ is deterministic context free, hence it is also context free.
Option D is true, as L₁ ∩ L₂ is DCFL and DCFL ∩ L₃ is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.

CFL is closed under regular intersection.

Let us construct a PDA for the language
PUSH z₀ into stack
PUSH K to stack of occurance of a
PUSH L to stack of occurance of b
POP K and L for the occurance of c
→ After POPno elements in the stack. So, this is context free language.
Note:
Regular:
R = {aⁿ | n ≥ 1}, Example.
CFL:
R = {aⁿb^m | n,m ≥ 1}, Example.

The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicograhic order which is not accepted by TM.
The give 'L' is recursive but not necessarily context free.

Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.

C and C++ are context sensitive languages.

The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0⁺.

(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL.
So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.

L = {a^mbⁿ|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.

Context free languages are not closed under intersection.

Due to presence of some features FORTRAN cannot be handled by PDA.
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.