1.3. Introduction to Formal Languages¶
1.3.1. Introduction¶
In this module, we present the three foundational concepts for the semester: Languages, Grammars, and Automata.
1.3.2. Languages¶
First we’ll present the basic ideas related to a Language, as this word is used in Formal Languages.
1.3.3. Grammars¶
The following frameset provides an introduction to the concept of a grammar, as used in Formal Languages.
1.3.4. Practicing Grammars¶
1.3.5. Automata¶
Now we understand what a language is (some subset of strings over an alphabet), and what a grammar is (a way of defining a language using production rules). Our third major concept is a family of computation models called Automata. Automata should be thought of as simple computers. The advantage to “simple” is that we can hope to completely understand how “powerful” the various types of machines are. Here “powerful” means what languages they can be programmed to recognize, which means to reliably determine if a string is in the langauge or not.
Figure 1.3.1: This diagram shows an abstract model of a digital computer. It has a tape (to store information), a tape head (to read the current square on the tape), a control unit, and possibly some optional storage in the form of a stack. Within the control unit, the numbers represent states, which are the specific positions on the dial that the arrow may point to.
While the picture above shows the physical components of the “computer”, it is not showing the control behavior (what to do when we are in a given state with a given symbol on the current square of the tape, and a given value is at the current position in the storage unit). This control behavior is like the “software” of the computer. The “program” used to control this machine will be a set of rules that check the current letter on the tape and the current state of the machine, and then decide what state to move to. Some machine types automatically move the tape head to the right at each step. Some machines are able to alter the symbol in the current square, and maybe have a choice of whether to move right or left.
Figure 1.3.2: This diagram shows an example of an automata in a form that shows its control behavior. This one accepts any string made of 1’s and 0’s that ends in 0 (in other words, any even binary number). Can you figure out how it does that?
