1.3.1. Introduction¶

In this module, we present the three major 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 / 37 Settings

<<<>>>

A language is simply a collection (that is, a set) of strings. More precisely, a language is a subset of the strings that can be generated from some alphabet. A fundamental thing to be able to do with a string is to determine whether or not it is part of a given language. We will talk later about ways to formally define a particular language. But first we need some notation to help express ourselves.

Saving...
Server Error
Resubmit

1.3.3. Grammars¶

The following frameset will provide an introduction to the concept of a grammar, as used in Formal Languages.

1 / 35 Settings

<<<>>>

One way to describe a language is in the form of a grammar. We'll start with a grammar you can maybe relate to. Below is a grammar that describes a really small subset of the English language.

$\begin{eqnarray*}\lt sentence\gt&\rightarrow&\lt subject\gt\lt verb\gt\lt d.o.\gt\\\lt subject\gt&\rightarrow&\lt noun\gt | \lt article\gt\lt noun\gt\\\lt verb\gt&\rightarrow&\ \mbox{hit}\ |\ \mbox{ran}\ |\ \mbox{ate}\\\lt d.o. \gt&\rightarrow&\lt article \gt\lt noun\gt | \lt noun\gt\\\lt noun \gt&\rightarrow&\ \mbox{Fritz}\ |\ \mbox{ball}\\\lt article\gt&\rightarrow&\ \mbox{the}\ |\ \mbox{an}\ |\ \mbox{a}\end{eqnarray*}$

Saving...
Server Error
Resubmit

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, where “recognize” means to reliably determine if a string is in the langauge or not.

While this picture 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. In some machine types, the tape head then automatically moves to the right at each steps. Some machines are able to also alter the symbol in the current square, and maybe have a choice of whether to move right or left.