[PDF] [PDF] formal-languages-and-their-relation-to-automata - saved paradigms

[PDF] Automata Theory, Languages,and Computation - Department of

book Second, the role of automata and language theory has changed over the past two 2 3 1 An Informal View of Nondeterministic Finite Automata 55

[PDF] Formal Languages and Automata Theory

5 nov 2010 · We end the chapter with an introduction to finite representation of languages via regular expressions 2 1 Strings We formally define an alphabet 

[PDF] Automata Theory and Formal Languages - CORE

Nondeterministic Finite Automata and S-extended Type 3 Grammars 33 notion of grammar (or language) we consider in each sentence throughout the book,

[PDF] Automata Theory and Applications - UT Austin Computer Science

Stochastic Finite Automata: Markov Models and HMMs * Programs and algorithms will appear throughout the book, stated at varying levels of detail We will 

[PDF] DIGITAL NOTES ON FORMAL LANGUAGES AND AUTOMATA

(R15A0506)FORMAL LANGUAGES AND AUTOMATA THEORY Objectives: ❖ To teach the student to identify different formal language classes and their

[PDF] formal-languages-and-their-relation-to-automata - saved paradigms

the techniques and results from language and automata theory This book presents the theory of formal languages as a coherent theory and makes explicit its 

[PDF] Chapter 1 Review of Formal Languages and Automata Theory - LIACS

I 1 Chomsky hierarchy grammar automaton 3 regular right-linear finite state A → aB a 2 context-free review of formal languages and automata theory 1 1 Sets 1 8 Complexity theory based on the book by Jeffrey Shallit of the same title

[PDF] Introduction to automata theory, languages

published this classic book on formal languages, automata theory, and computational complexity With this long-awaited revision, the authors continue to  

pdf Images

Domains of discourse: automata and formal languages Automaton is the box of tricks language recognition is what it can do What is this course about? Examining the power of an abstract machine Domains of discourse: automata and formal languages Formalisms to describe languages and automata Very useful for future courses

[PDF] formal report example for students pdf

[PDF] formal report writing example for students

[PDF] formalin fixation time calculator

[PDF] formalin solution

[PDF] format for project writing pdf

[PDF] format line numbers in word 2016

[PDF] formation developpeur web a distance

[PDF] formatting document in ms word in hindi

[PDF] formatting techniques in tableau

[PDF] forme algébrique d'un nombre complexe exercice

[PDF] forme bilinéaire et quadratique exercices corrigés

[PDF] forme bilinéaire symétrique définie positive

[PDF] forme canonique second degré exercice corrigé

[PDF] forme indéterminée 0/0

[PDF] forme indéterminée math

AND THEIR FORMAL LANGUAGES

RELATION TO AUTOMATA

FORMAL LANGUAGES

AND THEIR RELATION TO AUTOMATA JOHN E. HOPCROFT

Cornell University, Ithaca, New York

JEFFREY D. ULLMAN

Bell Telephone Laboratories, Murray Hill, New Jersey A VV Reading, Massachusetts ADDISON-WESLEY PUBLISHING COMPANY

Menlo Park, California • London • Don Mills, Ontario

This book is in the

ADDISON-WESLEY SERIES

IN COMPUTER SCIENCE AND INFORMATION PROCESSING Consulting Editors

MICHAEL A. HARRISON

RICHARD S. VARGA Copyright © 1969 by Addison-Wesley Publishing Company, Inc. All rights reserved. No

part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Published simultaneously in Canada. Library of Congress Catalog Card No. 69-14297. PREFACE The study of formal languages constitutes an important subarea of computer science. This area sprang to life around 1956 when Noam Chomsky gave a mathematical model of a grammar in connection with his study of natural languages. Shortly afterwards, the concept of a grammar was found to be of great importance to the programmer when the syntax of the programming language ALGOL was defined by a context-free grammar. This development led naturally to syntax-directed compiling and the concept of a compiler compiler. Since then a considerable flurry of activity has taken place, the results of which have related formal languages and automata theory to such an extent that it is impossible to treat the areas separately. By now, no serious study of computer science would be complete without a knowledge of the techniques and results from language and automata theory. This book presents the theory of formal languages as a coherent theory and makes explicit its relationship to automata. The book begins with an explanation of the notion of a finite description of a language. The funda- mental descriptive device--the grammar--is explained, as well as its three major subclasses--regular, context-free, and context-sensitive grammars. The context-free grammars are treated in detail, and such topics as normal forms, derivation trees, and ambiguity are covered. Four types of automata equivalent to the four types of grammars are described. These automata are the finite automaton, the pushdown automaton, the linear bounded autom- aton, and the Turing machine. The Turing machine is covered in detail, and unsolvability of the halting problem shown. The book concludes with certain advanced topics in language theory--closure properties, computational complexity, deterministic pushdown automata, LR(k) grammars, stack automata, and decidability. The emphasis is on ideas and ease of understanding rather than undue formalism. In some cases the details of long and tedious proofs are omitted. However, in all cases sufficient intuitive explanation is given so that the reader may easily provide the rigorous proof if desired. The book is intended primarily as a textbook for a first or second year graduate course in formal languages. It is self-contained and presupposes only the normal level of maturity expected of a beginning graduate student. Although not essential, it has been found that a course in finite state machines or Turing machines is useful preparation. The book is not intended as a research monogram on formal languages, although it covers many of the known results, and much of the material presented previously existed only in journals of mathematics and computer science. The chapters are provided with a guide to references on the material covered and related topics. The problems are an integral part of the text and their difficulty ranges from almost trivial to extremely difficult. The material for this book is based upon class notes for courses in language theory taught by the authors at Princeton, Columbia, and Cornel1. The authors would like to thank the many people who offered their sugges- tions and criticism. In particular, we would like to thank A. V. Aho, S. Amoroso, A. Korenjak, and M. Harrison. Thanks are also due to Bell Telephone Laboratories, and Princeton and Cornell Universities for provid- ing the facilities for the preparation of the work. J. E. H.

J. D. U.

CONTENTS Chapter 1 Languages and Their Representations 1.1 Alphabets and Languages ........... 1

1.2 Procedures and Algorithms .......... 2

1.3 Representations of Languages .......... 5

Problems ................ 7 Chapter 2 Grammars

2.1 Motivation ............... 8

2.2 The Formal Notion of a Grammar ........ 10

2.3 The Types of Grammars ........... 13

2.4 The Empty Sentence ............ 15

2.5 Recursiveness of Context-Sensitive Grammars ..... 16

2.6 Derivation Trees for Context-Free Grammars ..... 18

Problems ................ 24

References ............... 25 Chapter 3 Finite Automata and Regular Grammars 3.1 The Finite Automaton ............ 26

3.2 Equivalence Relations and Finite Automata ..... 28

3.3 Nondeterministic Finite Automata ........ 30

3.4 Finite Automata and Type 3 Languages ....... 33

3.5 Properties of Type 3 Languages ......... 35

3.6 Solvable Problems Concerning Finite Automata .... 39

3.7 Two-way Finite Automata ........... 41

Problems ................ 44

References ............... 45 Chapter 4 Context-Free Grammars

4.1 Simplification of Context-Free Grammars ...... 46

4.2 Chomsky Normal Form ........... 51

4.3 Greibach Normal Form ........... 53

4.4 Solvability of Finiteness and the "uvwxy Theorem" . . . 57

4.5 The Self-Embedding Property .......... 61

vii

4.6 ~-Rules in Context-Free Grammars ........ 62

4.7 Special Types of Context-Free Languages and Grammars. . 63

Problems ................ 65

References ............... 67 Chapter 5 Pushdown Automata 5.1 Informal Description ............ 68

5.2 Definitions ....... ........ 70

5.3 Nondeterministic Pushdown Automata and Context-Free

Languages ............... 74

Problems ................ 79

References ............... 79 Chapter 6 Turing Machines

6.1 Introduction ............... 80

6.2 Definitions and Notation ........... 80

6.3 Techniques for Turing Machine Construction ..... 84

6.4 The Turing Machine as a Procedure ....... 91

6.5 Modifications of Turing Machines ........ 92

6.6 Restricted Turing Machines Equivalent tO the Basic Model . 98

Problems ............... 101

References ............... 101 Chapter 7 Turing Machines: The Halting Problem, Type 0 Languages 7.1 Informal Discussion ............ 102

7.2 A Universal Turing Machine ......... 102

7.3 The Unsolvability of the Halting Problem ...... 108

7.4 The Class of Recursive Sets .......... 109

7.5 Turing Machines and Type 0 Grammars ...... 111

Problems ................ 113

References ............... 114

Chapter 8 Linear Bounded Automata and Context-Sensitive

Languages

8.1 Introduction ............... 115

8.2 Relation of Linear Bounded Automata to Context-Sensitive

Languages ............... 116

8.3 The Context-Sensitive Languages as a Subclass of the Recursive

Sets ................. 117

Problems ................ 118

References ............... 119 Chapter 9 Operations on Languages 9.1 Introduction ............... 120

9.2 Closure Under Elementary Operations ....... 120

9.3 Closure Under Mappings ........... 124

Problems ................ 133

References ............... 134 Chapter 10 Time- and Tape-Bounded Turing Machines 10.1 Introduction ............ , . . 135

10.2 Definitions ............... 135

10.3 "Speed Up" and "Tape Reduction" Theorems ..... 137

10.4 Single-Tape Turing Machines and Crossing Sequences . . 143

10.5 Lower Bounds on Tape Complexity ........ 147

10.6 Tape and Time Hierarchies .......... 149

Problems ................ 154

References ................ 155 Chapter 11 Time and Space Bounds for Recognizing Context-Free

Languages 11.1 Introduction ............... 156

11.2 Time Requirements for Recognition of Context-Free Languages 156

11.3 Space Requirements for Recognition of Context-Free Languages 160

Problems ................ 164

References ............... 165

Chapter 12 Deterministic Pushdown Automata 12.1 Introduction ............... 166

12.2 Complements of Deterministic Languages ...... 167

12.3 Properties of Deterministic Languages ....... 171

12.4 Context-Free Languages That Are Not Deterministic . . . 180

12.5 LR(k) Grammars . ............ 180

Problems ................ 187

References ............... 188 Chapter 13 Stack Automata 13.1 Definitions ............... 189

13.2 Restricted Types of Stack Automata ........ 192

13.3 The Power of Two-Way Stack Automata ...... 192

13.4 The Power of One-Way Stack Automata ...... 201

13.5 Recursiveness of Stack Automata ........ 207

13.6 Closure Properties ............. 209

Problems ................ 209

References ............... 209 Chapter 14 Decidability 14.1 Decidable and Undecidable Questions ....... 211

14.2 Post's Correspondence Problem ......... 212

14.3 A Question Concerning Context-Sensitive Languages . . . 219

14.4 Unsolvable Questions for Context-Free Languages .... 219

14.5 Ambiguity in Context-Free Languages ....... 222

14.6 Unsolvable Questions Concerning Deterministic Context-Free

Languages ............... 229

14.7 Summary of Decision Problems for Regular, LR(k), Context-

Free, Context-Sensitive, and Type 0 Grammars .... 231

Problems ................ 231

References ............... 232 Bibliography .......... .... 233 Index ................. 239

CHAPTER 1 LANGUAGES AND THEIR REPRESENTATIONS 1.1 ALPHABETS AND LANGUAGES What is the theory of languages ? To answer this question we first ask" What

is a language ? Webster defines a language as "the body of words and methods of combining words used and understood by a considerable community." However, this definition is not sufficiently precise for building a mathematical theory of languages. Thus we shall define a formal language abstractly as a mathematical system. This formality will enable us to make rigorous state- ments about formal languages and to develop a body of knowledge which can then be applied to those languages which are suitably modeled. With these ideas in mind, we make the following definitions. An alphabet or vocabulary is any finite set of symbols. Although a non- countably infinite number of symbols exists, we shall consider only a count- ably infinite t subset from which all finite sets will be drawn. This subset will include digits, the Latin and Greek letters both upper and lower case (possibly with combinations of subscripts, superscripts, underscores, etc.), and special symbols such as #, ¢, and so on. Any countable number of additional symbols that the reader finds convenient may be added. Some examples of alphabets are the Latin alphabet, {A, B, C,..., Z}, the Greek ~ alphabet, {a, fl, 7,..., co}, and the binary alphabet, {0, 1}. A sentence over an alphabet is any string of finite length composed of symbols from the alphabet. Synonyms for sentence are string and word. The empty sentence, e, is the sentence consisting of no symbols. If Vis an alphabet, then V* denotes the set of all sentences composed of symbols of V, including the empty sentence. We use V + to denote the set V* - {e}. Thus, if V = {0, 1}, then V* = {e, 0, 1, 00, 01, 10, 11,000,...} and V + = {0, 1, 00,...}. A language is any set of sentences over an alphabet. Most languages of interest will contain an infinite number of sentences. Three important questions are raised. First, how do we represent (i.e., specify the sentences of) a language ?

If the language contains only a finite number of sentences, the answer is easy. I" A set is countably infinite if it is in one-to-one correspondence with the integers

(i.e., if it makes sense to talk about the ith element of the set).

2 LANGUAGES AND THEIR REPRESENTATIONS 1.2 One simply lists the finite set of sentences. On the other hand, if the language

is infinite, we are facedwith the problem of finding a finite representation for the language. This finite representation will itself usually be a string of symbols over some alphabet, together with some understood interpretation which associates a particular representation with a given language. Second, does there exist a finite representation for every language ? One would suspect that the answer is no. We shall see that the set of all sentences over an alphabet is countably infinite. A language is any subset of the set of all such sentences. It is a well-known fact of set theory that the set of all subsets of a countably infinite set is not countably infinite. Although we have not defined what constitutes a finite representation, we intuitively feel that any meaningful definition of a finite representation will result only in a countable number of finite representations, since one should be able to write down any such representation as some string of symbols. Thus, there are many more languages than finite representations. Third, we might ask what can be said about the structure of those classes of languages for which there exist finite representations. Much of this book will be devoted to presenting various systems of representing and charac-

terizing these classes of languages. 1.2 PROCEDURES AND ALGORITHMS Before discussing the idea of a finite representation we informally introduce

the concepts of a procedure and an algorithm. A procedure is a finite sequence of instructions that can be mechanically carried out, such as a computer program. We are somewhat vague in our definition of a procedure. We give a formal definition in Chapter 6 in terms of Turing machines. For the time being, if we cannot determine whether or not a step can be mechanically carried out, then we reduce the step to a sequence of simpler steps which we can determine can be carried out. For example, we might object to the step "Find the smallest integer, x, satisfying such and such a condition," unless it was obvious how to find the smallest x. Even if one knows that such a smallest x must exist, it may not be possible to find the x by mechanical means. An example of a procedure which determines if an integer i, greater than one, is prime is given in Fig. 1.1. A second example of a procedure is given in Fig. 1.2; this procedure determines, for an integer i, whether there exists

a perfect numbert greater than i. "I" A perfect number is an integer which is equal to the sum of all its divisors except

itself. Thus 6 is a perfect number since 1 + 2 + 3 = 6. 12 is not perfect since its divisors are 1, 2, 3, 4, and 6, which sum to 16.

1.2 PROCEDURES AND ALGORITHMS 3 Note that the first procedure will terminate for all values of i, since either

a value ofj will be reached which divides i, or j will eventually become equal to or greater than i. In either case the procedure terminates and tells us whether i is prime. A procedure which always terminates is called an algor- ithm. Thus we refer to the procedure of Fig. 1.1 as an algorithm for deter- mining if an integer greater than one is prime.

Instructions"

1. Set j = 2.

2. If j __> i, then halt. i is prime.

3. If i/j is an integer, then halt. i is not prime.

4. Setj=j+ 1.

5. Go back to Instruction 2. I Start I =I '1 yes= "1 "i ~ i? I " 0

Isi,# an integer? no

' 1 I i=i+1 yes = v Halt. i is prime. Halt. i is not prime. Fig. 1.1. A procedure for determining whether an integer greater than one is prime. The second procedure need not always terminate. If there are only a

finite number of perfect numbers,t then the procedure will not stop for any integer larger than the largest perfect number. Rather the procedure will keep testing larger and larger k, looking for another perfect number. In other words, if i is such that there is a perfect number greater than i, the procedure will find it. However, if no such perfect number exists, the pro-

cedure will run forever. As long as the procedure continues to run, we have t The question of whether or not there are an infinity of perfect numbers is an

unsolved problem of number theory.

4 LANGUAGES AND THEIR REPRESENTATIONS Instructions" l,

2. 3. 4. 5. 6. 7. 8. 9. 10.

11. Set k = i.

Set k = k + 1.

Set sum = 0.

Setj = 1.

If j < k, then go to Instruction 8.

If sum ¢ k, then go to Instruction 2.

Halt. k is a perfect number greater than i.

If k/j is not an integer, then go to Instruction 10.

Set sum = sum + j.

Setj = j + 1.

Go to Instruction 5. 1.2 j = j + 1 L no a"

t l stao l ! k=k+.l~L, ,p 1 j., j=l IsjIs k,,~" an integer? yes L no

I no "1 Does sum = k? lyes ,

• a perfect number greater than i. Fig. 1.2. A procedure for determining if there is a perfect number greater than i.

1.3 REPRESENTATIONS OF LANGUAGES 5 no way of knowing if it will eventually halt. Thus we may say that the

procedure determines if there exists a perfect number greater than a given integer in the sense that, if such a perfect number exists, the procedure will eventually supply an affirmative answer. If no such perfect number exists, the procedure will supply no answer at all, since at no time do we know ifquotesdbs_dbs4.pdfusesText_7