title: Deciding if a given Language is Regular/Context-Free/Non Context-Free
body: <p>I need some help with deciding if a given language is regular, context-free or not context-free. A brief, informal explanation is sufficient in the answer, hence no need to use pumping lemma.</p>
  
  <p>Lets say I have the following lanugages:</p>
  
  <pre><code>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) &lt; #c(w) }
  
  L3 = { w  ∈ {a, b, c, d}* | #a(w) &lt; #b(w) &lt; #c(w) }
  </code></pre>
  
  <p>This is my solution:</p>
  
  <pre><code>L1 = L2 ∩ L3 ∩ L4 where
  
  L2 = #a(w) is even
  L3 = #b(w) = 1 mod 3
  L4 = w does not have a substring abc 
  </code></pre>
  
  <p>A DFA can be constructed for L2, becuse L2 does not need infinite memory, so L2 is regular. For L3 the same reasoning as above. And for L4 we can construct a DFA that simply does not accept "abc", hence regular.</p>
  
  <p>L1 is regular because regular languages are closed under ∩ .</p>
  
  <p>For L2 we can divide the language into:</p>
  
  <pre><code>L2 = L3 ∩ L4 where
  
  L3 = #a(w) is even
  L4 = #b(w) &lt; #c(w)
  </code></pre>
  
  <p>We know that a DFA can be constructed for L3, hence L3 is regular. L4 is context-free because we can construct a PDA where a stack is used to count the number of a:s and b:s.</p>
  
  <p>L2 is hence context-free because the ∩ of a regular language and a context-free language result in a context-free language.</p>
  
  <p>For L3 we can see that it's non context-free because we are limitied to 1 stack, and to do more than 1 comparison we need more stacks.</p>
  
  <p>Is my reasonings rights ? I have a exam soon and need to know if I have got the idea behind this.</p>
  
  <p>Thanks in advance</p>