0
$\begingroup$

Consider L1 = Any language generated by a machine M1

L2 = Any language generated by a machine M2

Machine can be – FA, PDA, LBA, or TM

Assuming Machine M2 is more powerful than M1

Let L3 = L1 $\cap$ L2

Now can we always say that L3 can be generated by Machine M2 ?

For eg:

L1 = Any Context Free Language (i.e Generated by NPDA)

L2 = Any Recursively enumerable language (i.e Generated by TM)

Now can we always say that L1 $\cap$ L2 is Recursively Enumerable Language i.e it can be generated by a TM?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

Nope. For several examples, see https://en.wikipedia.org/wiki/Context-free_language#Nonclosure_under_intersection,_complement,_and_difference, Which closure properties are always valid between regular, context-free and non context-free languages?, Intersection of Deterministic Context-Free Languages.

$\endgroup$
5
  • $\begingroup$ I did refer your article but in the article it is mentioned that CFL are not closed under intersection and various other clousure properties about CFL. But what can we say about CFL $\cap$ REL. <br/> CFL - Any context free language <br/> REL - Any Recursively enumerable language $\endgroup$ Commented Nov 19, 2022 at 12:04
  • $\begingroup$ @ChaitanyaKale, that's a separate question than what you asked here. We request that you ask only one question per post. If you have multiple questions, it's better to post them separately. I suspect that if you spend some time thinking about it you can figure out the answer to that question. $\endgroup$
    – D.W.
    Commented Nov 20, 2022 at 2:49
  • $\begingroup$ I have actually asked the same question in comment with specifically considering CFL and REL but the original question in general speaks considering any language $\endgroup$ Commented Nov 22, 2022 at 12:00
  • $\begingroup$ @ChaitanyaKale, I already answered that. Your question was "Can we always say...?" and I answered "Nope". $\endgroup$
    – D.W.
    Commented Nov 22, 2022 at 18:41
  • $\begingroup$ Thank you D.W I got it now 👍 $\endgroup$ Commented Nov 24, 2022 at 12:07
1
$\begingroup$

A general principle that may help:

  • Deterministically-defined language classes (e.g., Regular, Turing-decidable), are typically closed under union, intersection, and complement.
  • Nondeterministically-defined language classes (e.g., Context Free, Turing-recognizable) are typically closed under union, but not intersection and complement.

By "deterministically-defined", I mean that the computational model is deterministic, it processes the input in some way, always terminates, and deterministically produces an output. By "nondeterministically-defined", I mean that the computational model involves either nondeterminism in the way the rules are applied or nontermination.

Of course, this rule is only a starting point. Sometimes, the computational model admits determinization (e.g., NFAs can be determinized to DFAs) in which case the nondeterminism is not actually inherent to the model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.