go to previous page   go to home page   go to next page


Yes... although the written description is hard to follow. The automaton is easier to understand.

Formal Languages

Venn Diagram

A formal language is a set of strings. The symbols in the strings are selected from a finite list of symbols called an alphabet. Most of our example strings will be composed of symbols selected from ASCII characters (ordinary keyboard characters). A finite-state automaton precisely describes a set of strings. Often an automaton is clearer than an equivalent description in English. A language (a set of strings) that can be described by a finite automaton is called a regular language.

Formal languages are important to computer science (and to many other fields). All programming languages, like Java, C, and Python, are formal languages. The patterns of ones and zeros that make up the machine code of a processor also is a formal language. Compilers translate from one formal language (like C) into another (the machine language of the processor). However, a programming language is not a regular language. Most formal languages are not regular languages. The diagram shows this.

However, many useful formal languages are regular languages. For example, the set of legal Java identifiers is a regular language. The set of floating point literals (strings like 8.63 or -12.8E3) is a regular language.


Do you suppose that the set of legal file names is a regular language?