What are some quick things to look for to see if a language is regular or context-free Without using proofs or pumping lemma, but just by looking at the given language by eye, what are some quick tips and techniques that can be used to see that a language is regular, or that a language is context-free?
 A: Any language presentable by a regular expression is regular, as pointed out in a comment. This intuition can help you to see that certain languages are not regular, without a formal proof. For example, if arbitrarily long different parts of a string in the language are related somehow, e.g. your language is $a^nb^n$ for all natural numbers $n$, then it cannot be regular because there is no way to track "dependence" between different arbitrarily long parts of the string either using a regular expression or DFA. Similarly, for a context-free language, there is no way to track dependencies between 3 or more arbitrarily long parts of the string, because although a variable through one of the rules in the presentation can yield both characters and variables on both sides of the variable, these new variables in the expression cannot "track" each other anymore and follow non-trivial relationships in the substrings they produce. This is why e.g. $a^nb^nc^n$ for all natural numbers $n$ is not context free.
A: Thorough answers to your questions can be found here:


*

*How to prove a language is regular?

*How to prove that a language is not regular?

*How to prove that a language is context-free?

*How to prove that a language is not context-free?
