语言与机器

刘建文略译（http://www.semi-translate.com/blog | http://blog.csdn.net/keminlau ）

Introduction

Languages And Machines - Notes for Math237

Author : Dr. Christopher D. H. Cooper, Division of Information and Communication Sciences, Macquarie University Publication Date : July 2005
Book Excerpts:

The unifying theme in this book is the concept of a language as a system of strings of characters strings obeying certain rules. Strings are fundamental to computing science. Although we tend to think of computers as devices for manipulating numbers, words and pictures, it is more accurate to think of them as machines for manipulating strings of symbols which in turn represent numbers, words or pictures.

This book begins by discussing a special-purpose language - the language of logic. Then it develops a language for talking about languages in general. Since languages are just sets of strings, this book will talk about sets and the associated concepts of relations and functions, using yet another special-purpose language.

本书的主题内容是讲述“语言”是按照一定的规则生成字串的系统。字串是计算科学的基石。虽然我们一般都认为计算机是处理数字、文字和图片的设备，但更准确的说，计算机是在处理表达这些数字、文字和图片的符号串。

本书首先探讨一种专用语言--逻辑的语言。从而开发一种新语言来辅助讲述语言的原理。由于语言只不过是字串集合，所以本书使用另一种专用语言来讲述集合和与集合有关的概念，如关系和函数。

At this stage this book will also discuss proofs. It investigates the nature of proof from the syntactic point of view, that is, thinking of proofs as sequences of strings of symbols related to each other in a mechanical way. As well as helping readers to write sound mathematical proofs this book will give them some insight into automated proofs of program correctness.

接着还讨论“证明”。讨论将从句法的角度来研究“证明”的实质；也就是将“证明”看成是按数学方式组成的相关的符号串序列。读者学会作一些完美的数学证明也就对程序的正确性的自动证明过程有深入的理解。

This book will also teach the connection between languages and machines that manipulate them. Finite-state machines and Turing Machines are important mathematical models of the computing process and they are used to answer a number of important theoretical questions. such as:

• How does one give a finite description of a language if it contains infinitely many possible strings?
• Are there any calculations which are theoretically impossible for a computer to perform?

本书还会讲述语言和（操纵该语言的）机器之间的桥梁。有限状态机和图灵机是计算过程的重要的数学模型，它们将用来解答一系列的重大的理论问题。比如：

• 如何给一个语言一个有限的描述，如果该语言包含了无限多可能的字串？
• 是否存在一种计算，它在理论上是（计算机）不可计算的？

Finally this book will looks briefly at encryption and coding. Both of these involve transforming strings of symbols and are important applications to the computing and communications industries. At the same time, both make real use of interesting parts of mathematics - the mathematics of numbers and of polynomials.

最后本书将讲述加密和编码。二者均涉及了符号串的转换，而且都是计算理论和通信理论的重要应用。同时，二者也都数学的有趣的方面--数字和多项式的真实应用。

2.1The languages of mathematics数学的语言（数学作为一种语言）

Somebody once said that mathematics is a language. This is very true at many levels. Just as a language is a vehicle媒介工具 for expressing facts rather than being a body of facts in itself, so is mathematics. Moreover many linguists believe that without human language, thought would have remained at a very primitive level. Language is not just a means of expressing thoughts. It is a tool for creating and developing thought. And so it is with mathematics.

有人说数学是一种语言。在很多层面上讲，这是非常正确的。就像语言是表达事实facts的媒介或工具却不是事实本身，数学也是这样的。此外，很多语言学家认为，如果没有语言，我们的思想很可能现在还处于一个很原始的水平。“语言”不仅仅是表达思想的手段，更是一种创造和开发新思想的工具。数学是异曲同工的。

In one sense the language of mathematics can be thought of as an extension of our everyday language. The fact that mathematicians have found the need to use specialised symbols often conceals this fact. If you were to pick up a research paper in many fields of advanced mathematics you might find many more words than symbols. Mathematicians use words, symbols or diagrams - whatever works best.

从某种意思上看，数学（语言）可以被看作自然语言的扩展。但是数学作为一种语言常常被它使用的特殊符号而被认为它不是一种语言。很多领域所作的研究报告，里面的高级数学部分都充满了这些特殊的符号。数学使用单词，也使用符号甚至图表，只要有利于表达的方式都会使用。

Having said that mathematics is a language, or is an extension of natural language, let us take a different tack补丁. Mathematics contains many miniature小规模 languages for specific purposes. Elementary algebra consists of sentences of the form “expression = expression”, “expression < expression”, etc. The variables and numbers in the expressions are the nouns, and the symbols such as “=” and “<” represent verbs. Another very important language is the language of symbolic logic.

我们说数学是一种语言，一种对自然语言的扩充，但是数学也它特殊的一面。数学包括一小部分特殊用途的语言。初等代数有一些语句，像“expression = expression”, “expression < expression”，表达式中的变量或数字是名词，而等号、小于号是动词。另一种重要的语言就是符号逻辑语言。

2.2语言与计算机科学

Trained computing scientists are familiar with at least one computer language. These are specialised systems for expressing commands, instead of facts. Since compilers must be able to convert such commands reliably and precisely into machine code, these languages need to be defined in a very tight way.

计算机科学家都至少熟悉一种计算机语言。他们都得通过命令来使用一些专用的系统，而不直接用口说。由于编译器必须能够精确地将命令转换成机器码，这种命令语言必须有严格的定义。

It is therefore considered to be an important part of the training of any computing scientist to study the theory of languages - how they can be defined and how they are built up. Many of the great names in this area of computing science, names such as Chomsky and Kleene, were actually experts in linguistics who recognised the relevance of their work to computing science and transferred their research into that environment.

由上可以知，语言理论的研习对每一个计算机科学家是非常重要的。语言理论包括了语言是如何被定义和构建的。

2.4语言

Normally we think of languages as special systems where certain strings are given meaning. There are the natural languages with which we communicate with one other in our daily lives such as English, French or Swahili. Then there are the specialised programming languages with which we communicate with computers such as BASIC, PASCAL and C++.

我们一般认为语言是一个特殊的系统，系统中包含了符号串和这些符号的意思。像我们日常使用的自然语言；像我们与计算机打交道的专用的程序语言basic,c,c++等。

But there are many other specialised systems that we don’t usually think of as languages. Morse Code is a language that is built on top of a natural language. Chess enthusiasts and knitters have developed specialised languages in which they describe their activities.

有很多专用符号系统我们并不认为它们是语言。像莫尔斯电码。像国际象棋爱好者和编造者为描述他们的活动而开发的特殊语言也不能叫语言。

There are two aspects to any language - syntax and semantics. Syntax is concerned with determining whether a given string has a valid form while semantics is concerned with the meanings that are given to acceptable strings. Semantics can only be discussed in the context of a particular language but syntax is more formal and can be discussed abstractly.

语言有两个共通点：语法和语义。语法关注的是一条字串是否是合法的语句，而语义则关注一条合法的语句的具体含义。语义只能在特定的语境中探讨，而语法则更普遍，所以可以抽出来形式般的研究它。

The sentence “The silver prejudice accelerated within the complicated sausage.” is a syntactically correct English sentence. The verbs, nouns and adjectives are all in correct positions relative to one another. But semantically it is nonsense. It lacks meaning. On the other hand the syntax of the sentence “Is near post-office where?” is incorrectly structured for English, but if a foreign tourist stopped you in the street with this question you might be able to guess that he wanted to be directed to the nearest post-office. So correct syntax is not always necessary for communication. But it certainly makes communication much easier!

语法正确的语句不一定有语义；语法欠佳不定义有碍于交流，但语法正确当然便于交流。

Decimal notation for real numbers is a mini-language that uses the ten digits, the minus sign and the decimal point. The semantics of this language involves concepts such as powers of 10 and limits of sequences, but the syntax can be expressed by a few simple rules:

十进制数符号系统语言的一个微型例子。它包含的符号有十个数字、负号和小数点。这种语言的语义包括诸如十的位权和有限的序列，不过它的语法却只下面几种：
(1) If a minus sign is included it must be at the front.
如果有负号，那负号必放在前面；
(2) At most one decimal point may be included and if included it must have a digit on either side.
最多只能有一个小数点，若有的话它有两边都要有一个数字；
(3) The first digit cannot be 0 unless it is the only symbol or a decimal point follows.
第一个数字不能是0，除非它是唯一的符号或后跟有小数点。

In order to make our discussion as general as possible we use the term language to refer to any (finite or infinite) set of strings.

为了让我们的讨论更具有普遍性，我们把“语言”指代任何一个（有限的或无限的）符号串集合。

1.1 The Role of Logic in Mathematics ............................................................… 7
1.2 The Role of Logic in Computing Science .................................................… 7
1.3 Propositions and Truth Functions .............................................................… 8
1.4 Compound Propositions ................................................................................ 9
1.5 Tautologies ..............................................................................................….. 11
1.6 Translating From English .........................................................................…. 12
1.7 Laws of Logic 12
..........................................................................................…..
1.8 Quantifiers ...............................................................................................….. 14
1.9 The Order of Quantifiers ..........................................................................…. 15
1.10 Quantifiers in Mathematics .....................................................................… 15
1.11 Negation Rules .......................................................................................…. 16
1.12 Writing Proofs ……………………………………………………………. 17
1.13 Patterns of Proof ………………………………………………………….. 17
1.14 The Importance of Definitions …………………………………………… 20
Exercises for Chapter 1 ..................................................................................…. 23
Solutions for Chapter 1 ………………………………………………………... 26

2.1 The Languages of Mathematics ................................................................… 35
2.2 Languages and Computing Science ..........................................................… 36
2.3 Strings .....................................................................................................….. 36
2.4 Languages 37
................................................................................................…..
2.5 String Substitution ...................................................................................….. 40
2.6 Formal Grammars ....................................................................................…. 40
2.7 Regular Expressions .................................................................................…. 42
Exercises for Chapter 2 ..................................................................................…. 44
Solutions for Chapter 2 ……………………………………………………… 45

3.1 Sets in Mathematics and Computing Science ............................................... 49
3.2 Defining a Set ....................................................................................……… 49
3.3 Basic Set Functions ..................................................................................…. 51
3.4 Venn Diagrams ........................................................................................….. 51
3.5 Extended Set Functions ............................................................................…. 52
3.6 Relations ................................................................................................…… 53
3.7 The Sum and Product of Relations ……………………………………… 53
3.8 Equivalence Relations ............................................................................…... 54
3.9 Equivalence Classes ...............................................................................…... 55
3.10 Functions .................................................................................................… 56
3.11 One-to-one and Onto Functions .................................................................. 57
3.12 Counting Finite Sets .................................................................................... 58
3.13 Counting Infinite Sets ……………………………………………………. 60
Exercises for Chapter 3 ..................................................................................…. 63


4.1 Cyclops, The Simplest Possible Computer ................................................... 69
4.2 Finite State Machines ...............................................................................…. 71
4.3 Mealy Machines .....................................................................................…... 72
4.4 Moore Machines ......................................................................................….. 73
4.5 Finite State Acceptors ..............................................................................…. 74
4.6 State Diagrams .........................................................................................…. 75
4.7 Black Holes .............................................................................................….. 76
Exercises for Chapter 4 ..................................................................................…. 77
Solutions for Chapter 4 ………………………………………………………... 81


5.1 Equivalent Machines ................................................................................…. 89
5.2 The Reduction Process — Removing Inaccessible States............................. 90
5.3 Equivalent States......................................................................................….. 92
5.4 k-equivalence of States..............................................................................… 94
5.5 The Reduction Algorithm — Locating Equivalent States............................. 95
5.6 The Reduction Process — Identifying States.............................................… 97
5.7 Standard Form .........................................................................................….. 98
5.8 Reduction of Mealey and Moore Machines .................................................. 99
Exercises for Chapter 5 ..................................................................................…. 101
Solutions for Chapter 5 ………………………………………………………... 104

6.1 Multiple Transitions ......................................……………………………… 115
6.2 Null Transitions ............................................………………………………. 116
6.3 Multiple Initial States ....................................……………………………… 117
6.4 Completing the Nulls ……………………………………………………… 117
6.5 Removing the Nulls ....................................................................... ………... 119
6.6 Combining Multiple Transitions ................................................................... 121
6.7 A Worked Example ..................................................................................…. 124
Exercises for Chapter 6 ..................................................................................…. 126
Solutions for Chapter 6 ………………………………………………………... 128


7.1 Regular Languages ........................................................................................ 133
7.2 The Languages 0, 1, λ and ? ...................................................................…. 133
7.3 The Product of Two Languages ...............................................................…. 134
7.4 The Sum of Two Languages ....................................................................…. 135
7.5 The Kleene Star of a Language ................................................................…. 136
7.6 Additional Examples ................................................................................…. 136
7.7 Example of a Non-Regular Language .......................................................… 137
7.8 Set Operations and Regular Languages 138
…………………………………….
Exercises for Chapter 7 ..................................................................................…. 143
Solutions for Chapter 7 ………………………………………………………... 145

8.1 The Limits of Computing .........................................................................…. 149
8.2 The Halting Problem ................................................................................…. 149
8.3 Definition of a Turing Machine .................................................................... 150
8.4 Example of a Turing Machine ................................................................... 152
8.5 Unary Representation of Numbers ............................................................… 152
8.6 Adding Turing Machines ..........................................................................… 153
8.7 Sample Turing Machines ..........................................................................… 154
Exercises for Chapter 8 ..................................................................................…. 157
Solutions for Chapter 8 ………………………………………………………... 160

!
9.1 The Basic Turing Machine and Its Extensions ............................................. 167
9.2 Multiple Tracks ...............................................................................……….. 168
9.3 Multiple Heads ..............................................................................………… 171
9.4 Multiple Characters ……………………………………..…………………. 172
9.5 A Universal Turing Machine ………………………………………………. 174
Exercises for Chapter 9 ................................................................................…... 178
Solutions for Chapter 9 ………………………………………………………... 179

"#$#%#
10.1 The Problem ...........................................................................…................. 183
10.2 Why it is Unsolvable ..................................................................…............. 185
10.3 The Halting Problem ..............................................................................…. 187
10.4 Deciding Whether a Given Turing machine Will Halt …………………... 189
10.5 The Flying Dutchman Problem …………………………………………... 192
Exercises for Chapter 10 ................................................................................…. 193
Solutions for Chapter 10 ………………………………………………………. 197

&$$
11.1 Days of the Week ...................................................................................…. 203
11.2 The System Z7 .......................................................................................….. 204
11.3 The System Zm ......................................................................................….. 206
11.4 Inverses in Zm …………………………………………………………….. 208
11.5 Powers in Zm .........................................................................................….. 210
11.6 Euler's ?-Function........................................................................................ 211
11.7 The RSA Code: How it Works ...............................................................…. 213
11.8 The RSA Code: Why it Works ...............................................................…. 215
11.9 Why it is Secure .....................................................................................…. 215
11.10 Cracking the RSA Code ………………………………………………… 216
11.11 Signature Verification …………………………………………………... 217
Exercises for Chapter 11 ................................................................................…. 218
Solutions for Chapter 12 ………………………………………………………. 220

$
12.1 Error Detection and Error Correction ......................................................... 225
12.2 Polynomials ..................................................................................………... 225
12.3 Complete Polynomials ................................................................................ 228
12.4 Polynomial Codes: How they Work 228
.......................................................…
12.5 Polynomial Codes: Why they Work 230
........................................................…
12.6 Analysis of Probabilities ............................................................................. 231
Exercises for Chapter 12 ................................................................................…. 231
Solutions for Chapter 12 ………………………………………………………. 233

!'$...............................……………. 237 !#'....................................…………… 241

LANGUAGES AND MACHINES

NOTES FOR MATH237



Introduction and Table of Contents (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap00.pdf



Chapter 1: Logic (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap01.pdf


Chapter 2: Languages (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap02.pdf


Chapter 3: Sets, Functions and Relations (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap03.pdf



Chapter 4: Introduction to Finite-State Machines (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap04.pdf


Chapter 5: Equivalence and Reduction of Finite-State Machines (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap05.pdf


Chapter 6: Non-Deterministic Finite-State Machines (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap06.pdf


Chapter 7: Finite State Acceptors and Regular Languages (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap07.pdf


Chapter 8: Turing Machines (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap08.pdf


Chapter 9: Extended Turing Machines (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap09.pdf


Chapter 10: The Busy Beaver Problem (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap10.pdf


Chapter 11: Integers mod m and Public Key Cryptography (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap11.pdf


Chapter 12: Polynomial Codes (updated 15th July 2005)

http://www.ics.mq.edu.au/~chris/math237/chap12.pdf



Appendices (updated 8th July 2005)

http://www.ics.mq.edu.au/~chris/math237/appendix.pdf