Decide whether a given language is regular / context-free / without context

Question

I need help deciding whether a given language is regular, contextual, or non-contextual. The answer is a fairly brief, informal explanation, so there is no need to use the pumping lemma.

Suppose I have the following lanugages:

L1 = { w ∈ {a, b, c, d}* | #a(w) is even, #b(w) = 1 mod 3, w does not have a substring abc } L2 = { w ∈ {a, b, c, d}* | #a(w) is even, #b(w) < #c(w) } L3 = { w ∈ {a, b, c, d}* | #a(w) < #b(w) < #c(w) } 

This is my decision:

 L1 = L2 ∩ L3 ∩ L4 where L2 = #a(w) is even L3 = #b(w) = 1 mod 3 L4 = w does not have a substring abc 

For L2, you can build DFA, because L2 does not need infinite memory, so L2 is regular. For L3, the same reasoning as above. And for L4, we can build a DFA that simply does not accept "abc", therefore, regular.

L1 is regular since regular languages ​​are closed with respect to ∩.

For L2, we can divide the language into:

 L2 = L3 ∩ L4 where L3 = #a(w) is even L4 = #b(w) < #c(w) 

We know that DFA can be built for L3, so L3 is regular. L4 has no context, because we can build a PDA where the stack is used to count the numbers a: s and b: s.

L2, therefore, has no context, because ∩ ordinary language and context-free language lead to context-free language.

For L3, we see that it is not contextual, because we are limited to 1 stack and to perform more than one comparison we need more stacks.

Are my reasoning rights? I have an exam soon and need to know if I have an idea.

Thank you in advance

Answer 1

Yes, you are right on all three points. L1 is regular, L2 has no context, and L3 is not context-free. You correctly apply the closing properties for L1 and L2, and your reasoning is more or less correct for the latter. For the latter, I would caution you against using this rule ... since there can be more than one way to think about how a language can be recognized, some of which require more than a stack, and some of them are not. Take, for example, non-context-free language L = {a ^ nb ^ nc ^ n}. The addition to this language has no context, although inaccurate application of the rule that you use may lead to the fact that you will believe differently (until you have considered the issue).