ABSTRACT

A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.

1. Introduction

Task 1 (The Task of the Hanoi Towers [1]). The Hanoi Towers are made up of three vertical pins. A series of N discs is hung on the first pin. The discs are all different, but ordered by size with the largest being on the bottom and the smallest on top. The task is to move the discs from the first to the third pin, using the second pin as an assistant. There are several conditions to completing this exercise: only one disc may be moved at one time and while one disc is being moved, all other discs must be on one of the pins and also, during this time, it is prohibited for a larger disc to be placed on a smaller one.

The task of the Hanoi Towers is a classic example used to teach recursion in programming [1-4]. In this paper, we will look at this Task from the standpoint of mathematical linguistics, i.e. as a part of the discipline of “discrete mathematics” and “mathematical linguistics” studies by students in Informatics and Computer courses at university [2,5-9].

There are three interesting approaches associated with the task of Hanoi towers in terms of mathematical linguistics:

1) To generate the Hanoi moves using a finite automaton;

2) To generate the Hanoi moves using a context-free grammar;

3) To generate the Hanoi moves using a pushdown automation.

The first approach is described in [10] and an equivalent version (with morphisms) in [11]. In this paper we will consider the second and third tasks. These tasks have been formulated in a Bulgarian in the textbook [12].

The algebraic properties of context-free grammars and languages are discussed in [5,8,13,14]. Several applications of formal grammars and languages and pushdown automata are considered in [8,15].

2. Context-Free Grammars and Languages

Let V be a finite and non-empty set. The elements of this set are called letters, and the whole set V—alphabet.

We will call a word over the alphabet V each finite string of letters from V. A word that does not contain any letter is called an empty word, which we will mark with. denotes the set of all words over V, including empty set. The term length of a word refers to the number of letters in it. The length of the word will be expressed by.

Let and be two words over the Alphabet V. By concatenation (multiplication) of both words we will mean the word obtained by successive completion of the letters of after the last letter of.

Let V be an alphabet. Each subset L of is called formal language (or only language) over alphabet V.

By generative grammar (or only grammar), we will understand the four ordered tuples, where V is a finite set (Alphabet) of terminal symbols, W—a set of nonterminal symbols, S—a start symbol of the grammar, which is an element of W, and P is a set of ordered pairs, where, with at least there one non-terminal symbol in. In a number of sources (see references at the end), an additional condition is placed for sets W and P to be finite. For our needs this condition is not necessary. It is enough that these sets are countable. The elements of P are called productions. If, then it means, as the symbol “” does not belong to.

Let and be two words from. We will say that is derived directly from in the grammar and will write (or only, if is understandable), if there exists words and a production in so that and.

If is a word over, for which, we will say that the number of words is the derivation of from in, which we denote by or only, if is default. The count n of the immediate derivations will be called the length of derivation.

The Set is called formal language over V, generated by the grammar. The Grammars and are equivalent if.

A grammar is context-free, if all the productions are of the type

where V and W are alphabets, respectively with terminal and nonterminal symbols.

Task 2. For a given positive integer N a context-free grammar should be built with a terminal alphabet encoding possible displacements and if, then describes the algorithm that solves the Task 1. Prove that for each positive integer N language is not empty, i.e. for each positive integer N there is an algorithm that solves the task of the Hanoi towers¹.

Solution. Let’s consider context-free grammar where. The meaning of is “Move top disk from the i-th pin of the j-th pin”. In this way, if, where , then describes the algorithm for the consecutive moving of discs in the three pins.

the start symbol, consists of productionsand for, where . Apparently, the grammar constructed in this manner is context-free.

Let, i.e. we assume that the derivationexists and let the length of the derivation is equal to. If, then obviously this is possible if and only if the number of discs and there is a direct derivation and in the presence of a single disc, describes an algorithm for solving Task 1. Similarly is a derivation with length 1 with start symbol and describes the algorithm for moving a single disc from pin to pin, where and. Let. We assume that if a derivation exists with length less than of type, where, then describes the moving of n discs from pin to pin, using pin k as assistant according to the constraints in Task 1, where,. When s < 1 obviously derivation with length s (if existing) will be of the type then the next derivations andexist with lengths less then s, whereand. According to the induction assumption, describes the algorithm for moving of discs from the first to the second pin, using the third one as assistant, and describes the algorithm for moving discs from the second to the third pin, using thr first one as assistant. Then describes the following algorithm: first under the constraints of Task 1 we move the top number of discs from the first pin to the second, then we move the largest bottom disk from the first pin of the empty third and finally, we move number of discs from the second pin to the third one. Therefore (if existing) describes the solution of the task of the Hanoi towers.

Let’s prove for each positive integer N that language is not empty. When, the only production of which can be applied is and therefore, i.e. is not an empty language. Let’s assume that for each positive integer the languages are not empty and put. Let’s consider the context-free grammarsand. Apparently and work by analogy of and according to the above proven if, then describes the algorithm for moving discs from the first tos the second pin, using third one as assistant under the constraints described in Task 1, and if, then describes the algorithm for moving t discs from the second pin to the third one using the first one as assistant. According to the induction assumption and there exists. Then in derivation exist, whereand. Therefore, i.e. is a non empty language.

When the following word is produced . We can verify the correctness of the algorithm using the example of the five consecutive playing cards.

The following is easy to prove (e.g. using induction):

Proposition 1. Let N be a positive integer, and be defined as the solution of Task 2 context-free grammar, then

and if, then

In other words, for each positive integer N, grammar generates exactly one word that describes an algorithm for solving the task of the Hanoi towers with exactly displacements of the disks from one pin to another.

3. Pushdown Automata

By nondeterministic pushdown automation one will understand each ordered septuple

where:

- K is a finite set of states of automaton;

- V is a finite set of entry letters (entry alphabet);

- W is a finite, non empty set of stack symbols (stack alphabet);

- is a transition function;²

- is a start state of automaton;

- is a start stack symbol;

- is a set of accepting states.

The ordered triple will be called configuration of nondeterministic pushdown automaton M.

Let . Then the transition function defines a transition configuration to the next configuration in the following way:

1) For each pair the configuration passes in the configuration, where , which we denote by.

2) For each pair the configuration passes in the configuration, which we denote by.

If the nondeterministic pushdown automation is initially given the word then, according to the start configuration, the following possible configurations are obtained by using a function of transitions. For each new configuration using all possible next configurations are obtained and so on.

The nondeterministic pushdown automation recognizes the word by accepting state, if its work at the beginning of given word, it reaches a configuration of type, for each, when.

The nondeterministic pushdown automation M recognizes the word by empty stack, if its work at the beginning of a given word reaches a configuration of type.

The pushdown automation is called deterministic, if for each and exactly one of the following two conditions is valid:

1) contains no more than one element for each and.

2) for each and contains no more than one element.

A language which is recognized by some deterministic pushdown automation is called a deterministic language. As it is known the relationship between context-free languages and pushdown automation is given by the following statements:

For each context-free language L a nondeterministic pushdown automation M exists, such that L is recognized by M through an accepting state.

Language L is recognized of a nondeterministic pushdown automation through an empty stack if and only if L is recognized of a nondeterministic pushdown automation through an accepting state.

If L is a language which is recognized by a nondeterministic pushdown automation, then L is a context-free language.

Task 3. For each positive integer a deterministic pushdown automation M_N should be built, which in its work should imitate the work of monks in solving the task of the Hanoi towers (see Task 1).

Solution. The requested pushdown automation is the following:, where

and is the empty set. Let,. Then the transition function is defined in following way:

(1)

(2)

(3)

(4)

Immediately after the inclusion of M_N, before being submitted as any input signal, the automation replaces the start stack symbol z₀ with word according to (1) and after a number of actions depending on the current stack symbol (2), (3), or (4). Moreover, we assume that automation M_N is designed so that after the reading of the stack symbol of the type , , simultaneously with the action according to (4) another action is carried out, namely the removal of top disk i-th pin on j-th. Transient function is defined so that after a finite number of beats the stack is empty and stops. This occurs because if the current stack symbol of the kind, then M_N deletes it, and if the current stack symbol is of the type, then at the next beat of the parameter decreases by one unit, if, or passes into the symbol at, then that symbol is deleted.

We will prove that the stack M_N of configuration where, , as a result of their work reaches a configuration and in the process it transfers, according to the restrictions of Task 1, s discs from pin i to pin j. When s = 1 we have, i.e. the assertion is met. Let’s assume that the assertion is fulfilled for any t, such that and let. Then in, , , we have. According to the induction assumption, M_N reaches the configuration moving t – 1 discs from i-th pin of k-th pin after which it passes in a configuration moving the next disc from pin to pin and again according to the induction, it moves discs (as all are obviously smaller size) on this disk on pin which are taken from pin. Therefore the assertion is true for any.

According to the assertion that has just been just proved, we have:

while the stack moves to the upper discs from the first to the second pin, then it moves the biggest at the bottom from the first to the third pin and finally it moves discs (numbers from the second to the third pin observing the restrictions described in Task 1). Therefore the pushdown automation M_N solves the task of the Hanoi towers.

REFERENCES

NOTES

¹It is not necessary L(Γ_N) to describe all solutions of Task 1. Some of them may be ineffective, for instance if they involve the useless relocation of disk as soon as moving the same disk to another pin.

²As usual with P(A) is denoted the set of all subsets of the set A, including the empty.