A Discussion of Finite Automata, Pushdown Automata and Turing Machines

A discussion of Finite Automata, Pushdown Automata and Turing Machines

Summary

Abstract machines can perform certain operations on given input. Language accepting, generating output and performing calculations or computations and producing a result are levels of operations that these machines can perform.

A progression of abstract machines follow from finite automata, pushdown automata and lastly to end with Turing machines that can perform all these levels of operations.

Turing machines are the basis of modern computers.

Introduction

This paper aims to give a concise theoretical background to the concepts of finite automata, pushdown automata and Turing machines. These three theoretical machines can be used to describe certain computational machines and is part of the theory of the working of computers. Some of the other parts, that this paper is not concerned with, is the theory of computer logic and computer architecture. A number of concepts need to be defined, before the three machines can be described, and these are given without a discussion of the proof of the definitions or theorems.

The paper is structured in five sections. As background to the middle three sections, the first section introduces certain concepts and definitions, that will be used in the later sections of the paper. The second section focuses on describing finite automata and their working. The third section extends the concepts of the second section to describe pushdown automata. Thereafter the fourth section introduces Turing machines and the paper ends with a discussion of the three machines with regards to their abilities.

First the background to the topic will be discussed in the following section.

Terminology, concepts and definitions

This section introduces a few of the more unusual concepts that are required to hold a sensible discussion on computational machines. When a concept is obvious from general use and no ambiguity needs to be resolved, it is not introduced here. The discussion is an abridged extract from the first few chapters of Cohen (1991).

An alphabet is a list of letters that can be used as the input to a machine. It is defined by the Greek capital letter ОЈ (sigma). A certain specified set of strings that can be built using letters from the alphabet is called the language. The words are those strings that are allowed in the language. The word without any characters from the alphabet is the null or empty string, written as the Greek capital letter О› (lamda).

ОЈ* (the Kleene star) is the closure of the alphabet, and is defined as the language where every string that can be formed from the alphabet is a word in the language, including the empty string.

A regular expression is an expression made up from letters of the alphabet according to the following 3 rules; (1) any letter from ОЈ written in bold, is a regular expression; (2) if r1 and r2 are regular expressions then so are (r1), r1r2, r1 + r2 , and r*; (3) nothing else is a regular expression. r1r2 means the concatenation of strings and r1 + r2 means choice of string, i.e. either one or the other.

A language is regular if it can be described by a regular expression. Not all languages are regular.

A few characteristics of regular languages are the following:

o If L1 and L2 are regular languages, then so is L1 + L2, L1L2 and L*.

o Regular languages are closed under intersection, meaning if L1 and L2 are regular languages, then so is (L1 в?© L2).

o L’, the complement of the language L, is the language containing all the words made from the alphabet of L that are not words in L.

A language that cannot be defined by a regular expression is then a non-regular language.

A machine can always be considered to be in a state at any given moment. The machine changes between states, based on the input to the machine and the rules of the machine.

A context free grammar (CFG) as defined by Cohen (1991) is a collection of the following three things:

1. An alphabet в?' of letters called terminals from which you are going to make strings that will be the words of a language.

2. A set of symbols called non-terminals, one of which is the symbol S, standing for �start here’.

3. A finite set of productions of the form:

one non-terminal в†' finite string of terminals and/or non-terminals

A language generated by a CFG is called a context-free language.

Not all languages are context free and if not, it is called a non-context free language.

A CFG is in Chomsky Normal Form (CNF) if all its production rules have the form

Nonterminal в†' Nonterminal Nonterminal

or

Nonterminal в†' terminal

All CFGs can be written in CNF. For all CFGs in CNF with p live productions (i.e. productions of the form Nonterminal в†' Nonterminal Nonterminal) and w is any word generated by the CFG with length greater than 2p, the word w can be broken up into 5 substrings

w = u v x y z

such that x is not Λ and v and y are not both Λ and such that all the words uvnxyns for n = 1, 2, 3, … can also be generated by the CFG. If a word w with length greater than 2p cannot be broken up into 5 substrings with the conditions as above, then the language generated by the grammar is a non-context free language.

The last language discussed in this essay is the set of languages generated by phrase-structure grammars. A phrase-structure grammar as defined by Cohen is a collection of three things:

1. An alphabet в?' of letters called terminals.

2. A finite set of symbols called nonterminals that includes the start symbol S.

3. A finite list of productions