Consider the following language:

L= {w ∈ { a, b, c }* : na(ω) + nb(ω) = nc(ω)}

L is 

The correct answer is Context free but not linear

Key PointsThe given language L={w ∈ { a, b, c }* : na(ω) + nb(ω) = nc(ω)} consists of strings over the alphabet {a, b, c} with the property that the total number of a's and b's in any string must be equal to the total number of c's.

• This language is context-free.
  • A context-free language (CFL) is typically one that can be generated by a context-free grammar (CFG) or recognized by a pushdown automaton (PDA). In this case, a PDA would have to simultaneously keep count of the number of 'a's and 'b's and compare this cumulative sum with the number of 'c's.  Here the PDA can deterministically guess when to switch from pushing for 'a's/'b's to popping for 'c's. However, this is deterministic, and it can be done deterministically.

  • On the other hand, a linear language is a proper subset of context-free languages where the grammar generating the language never has more than one non-terminal in the right-hand side of any of its productions (can also be processed with a deterministic pushdown automaton).