Abstract

This chapter discusses the use of formal language theory in the investigation of diverse phenomena such as natural languages, computer code, and animal cognition. Formal language theory deals with mathematically defined languages as well as the formal systems, such as grammars and automata, that are used to define them. In this context, a language is a set of strings, a grammar specifies a set of rules for forming the string-set from an alphabet, and an automaton is an abstract machine that can be programmed to generate or recognize a formal language. Formal language theory can thus be understood as the study of string-sets and their associated formal systems. As a result of being used as a model template across linguistics, computer science, and experimental cognitive science, formal systems in formal language theory, as well as a classification scheme called the Chomsky hierarchy, are given different interpretations.