I'm having trouble seeing what makes "any number of a's followed by the same number of b's and c's" a context-free language, while "any number of a's followed by any number of b's followed by any number of c's" is a regular language, as I saw expressed without explanation by an instructor. (Note in the latter example, the number of b's and c's may be unique, while in the former, the number of b's and c's are equal).
Any insight appreciated; apologies for a possibly crude question (format).
If the number of "a"'s must be equal to the sum of the number of "b"'s and "c"s, you cannot freely add a "b" or "c" to a string. What you can do is keep a stack where you push each "a", popping one off the stack every time you see a "b" or a "c". If the end of the sentence coincides with an empty stack, then the sentence is acceptable. Parsers with a single stack like that correspond to context-free grammars.
The stack is part of the parser state, and there is nothing which limits the size of the stack. So you need potentially unlimited state. A regular language can be parsed by a parser which has bounded state (usually represented as a single state in a state machine or some other election from a finite set of possibilities). That's good enough to recognise a*b*c*
, since it never matters how many "a"'s have been seen or how many "c"'s are still to come.
As you probably know, if the number of "a"'s, the number of "b"s and the number of "c"s must be equal, then a single stack is no longer sufficient to do the recognition, and the language is no longer context-free. That language is context-sensitive.