1. Knowledge of grammars and automata models for processing regular, context-free and phrase structure languages (e.g. finite automata, pushdown automata, and Turing machines).
2. Knowledge of undecidable problems, e.g. ambiguity problems.
3. Knowledge of the origin of P vs. NP.
4. Knowledge of formal language application to other domains.