Handbook of Mathematical Models for Languages and Computation
2: BioVendor Instruments a.s., Brno, Czech Republic
3: Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic
The theory of computation is used to address challenges arising in many computer science areas such as artificial intelligence, language processors, compiler writing, information and coding systems, programming language design, computer architecture and more. To grasp topics concerning this theory readers need to familiarize themselves with its computational and language models, based on concepts of discrete mathematics including sets, relations, functions, graphs and logic. This handbook introduces with rigor the important concepts of this kind and uses them to cover the most important mathematical models for languages and computation, such as various classical as well as modern automata and grammars. It explains their use in such crucially significant topics of computation theory as computability, decidability, and computational complexity. The authors pay special attention to the implementation of all these mathematical concepts and models and explains clearly how to encode them in computational practice. All computer programs are written in C#.
Inspec keywords: computability; grammars; computational linguistics; decidability; natural languages; automata theory; programming languages
Other keywords: syntax analysis; computation; sequences; decidability; deep pushdown automata; context-free grammars; parallel grammatical models; computability; graphs; programming languages; mathematical models; jumping models; relations; context-dependent grammars; finite automata; regulated models; biology; natural languages; sets; functions; Turing machines; classical models; pushdown automata
Subjects: General and management topics; Automata theory; Natural language interfaces; Formal languages and computational linguistics; Programming languages
- Book DOI: 10.1049/PBPC026E
- Chapter DOI: 10.1049/PBPC026E
- ISBN: 9781785616594
- e-ISBN: 9781785616600
- Page count: 761
- Format: PDF
-
Front Matter
- + Show details - Hide details
-
p.
(1)
-
Part I. Basic mathematical concepts
Basic mathematical concepts
- + Show details - Hide details
-
p.
1
(1)
1 Sets, sequences, and languages
- + Show details - Hide details
-
p.
3
–20
(18)
This chapter reviews the most basic concepts concerning sets and sequences. Special attention is paid to languages defined as sets whose elements are finite sequences of symbols because languages play an important role later in this book.
2 Relations and functions
- + Show details - Hide details
-
p.
21
–28
(8)
This chapter reviews rudimentary concepts concerning relations and their special cases called functions. These concepts underlie most formal models introduced in Part II of this book.
3 Graphs
- + Show details - Hide details
-
p.
29
–33
(5)
This chapter reviews the principal ideas and notions underlying graph theory. It restricts its attention to directed graphs, which are central to the theory of computation.
-
Part II. Classical models for languages and computation
Classical models for languages and computation
- + Show details - Hide details
-
p.
35
–36
(2)
4 Relations and language models
- + Show details - Hide details
-
p.
37
–46
(10)
We all use a variety of languages, ranging from high-level programming languages up to machine codes, to express our ideas representing procedures, which prescribe computers how to execute computational processes we have in mind. Just like finite sets, finite languages might be specified by listing all the strings. Apart from listing some trivial few -word languages, however, most specifications of this kind would be unbearably extensive and clumsy. More importantly, infinite languages, including almost all programing and natural languages, obviously cannot be specified by an exhaustive enumeration of their strings at all. Consequently, mathematical finite -size models for languages are central to this book as a whole. We base these models, customarily referred to as rewriting systems, upon relations (see Section 2.1). As a matter of fact, these systems underlie almost all language models covered in this book. The section defines rewriting systems in general, and concentrates its attention on using these systems as language -defining devices.
5 Finite automata
- + Show details - Hide details
-
p.
47
–86
(40)
In this five-section chapter, we cover finite automata that represents perhaps the simplest language-accepting rewriting systems. In Section 5.1, we define their basic versions. Then, in Section 5.2, we introduce finite automata that read a symbol during every single computational step. In Section 5.3, we study deterministic finite automata. In Section 5.4, we cover several reduced and minimal versions of finite automata. Finally, in Section 5.5, we define regular expressions and demonstrate the equivalence between them and finite automata.
6 Context-free grammars
- + Show details - Hide details
-
p.
87
–138
(52)
Context-free grammars represent language-generating rewriting systems. Each of their rewriting rules has a single symbol on its left-hand sides. By repeatedly applying these rules, these grammars generate sentences of their languages. This chapter gives a mathematical introduction into context-free grammars. First, Section 6.1 defines their basic versions. Then, Section 6.2 presents several mathematical methods that transform the basic versions so that the transformed versions are as powerful as the original versions but are much easier to handle in theory as well as in practice.
7 Pushdown automata
- + Show details - Hide details
-
p.
139
–158
(20)
Pushdown automata represent, in essence, finite automata extended by potentially infinite stacks, commonly referred to as pushdown lists or, more briefly, pushdowns. In this chapter, we demonstrate that these automata are as powerful as context-free grammars, discussed in the previous chapter. This chapter is divided into four sections. First, Section 7.1 defines pushdown automata. Then, Section 7.2 stablishes the equivalence between them and context-free grammars. Section 7.3 introduces three ways of accepting languages by these automata. Finally, Section 7.4 narrows its attention to the deterministic versions of pushdown automata and demonstrates that they are less powerful than their nondeterministic versions.
8 Turing machines
- + Show details - Hide details
-
p.
159
–177
(19)
In the article, there exists a crucially important hypothesis, referred to as the Church -Turing thesis, saying that every effective computation is mechanically performable by a procedure if and only if it is carried out by a Turing machine. Consequently, any computation beyond the power of Turing machines is also beyond the power of any computer. Therefore, these machines are central to the study of computation from a practical, mathematical, logical, as well as philosophical standpoint.
9 Computability
- + Show details - Hide details
-
p.
179
–190
(12)
This theory makes use of Turing machines to demonstrate the mathematical limits of computation. Indeed, any computation beyond the power of Turing machines is also beyond the computer power. The Turing machine represents a relatively simple language -defining model. Consider Turing machines as computers of functions over nonnegative integers and demonstrates the existence of functions whose computation cannot be specified by any procedure.
10 Decidability
- + Show details - Hide details
-
p.
191
–212
(22)
Recall that algorithms represent procedures that stop on all inputs, so they are formalized by Turing machines (TMs) that also halt on any input strings. In terms of these machines, we investigate the power of problem -deciding algorithms in this chapter. In fact, we restrict our attention only to the algorithmic decidability concerning problems related to the mathematical models discussed earlier in this book.
-
Part III. Alternative models for languages and computation
Alternative models for languages and computation
- + Show details - Hide details
-
p.
213
–214
(2)
11 Context-dependent grammars
- + Show details - Hide details
-
p.
215
–292
(78)
This chapter gives an extensive and thorough coverage of grammars that generate languages under various context -related restrictions. First, it covers classical grammars based upon tight context restrictions. Then, it studies context conditional grammars and their variants, including random context grammars, generalized forbidding grammars, semi-conditional grammars, and simple semi-conditional grammars. They all are based upon loose context restrictions. More precisely, they have their rules enriched by permitting and forbidding strings, referred to as permitting and forbidding conditions, respectively. These grammars perform their language-generation process in such a way that they require the presence of permitting conditions and, simultaneously, the absence of forbidding conditions in the rewritten sentential forms.
12 Regulated models
- + Show details - Hide details
-
p.
293
–365
(73)
This chapter covers regulated language models, which are extended by additional mathematical mechanisms that prescribe the use of rules during the generation of their languages. An important advantage of these models lies in controlling their language-defining process and, therefore, operating in a more deterministic way than general models, which perform their derivations in a completely unregulated way. More significantly, the regulated versions of language models are stronger than their unregulated versions. The chapter covers grammars regulated by states, grammars regulated by control languages, matrix grammars, programmed grammars, and regulated automata.
13 Parallel grammatical models
- + Show details - Hide details
-
p.
367
–477
(111)
Many modern information technologies work in parallel, so they make use of mutually cooperating multiprocessor computers. It thus comes as no surprise that the investigation of parallel computation fulfills a central role within computer science as a whole. In order to build up a systematized body of knowledge about computation in parallel, we need its proper formalization in the first place. The present chapter describes several types of parallel grammars, which can act as a grammatical formalization like this very well. To give an insight into parallel grammars, recall that up until now, in all grammars under consideration, a single rule was applied during every derivation step. To obtain parallel grammars, this one -rule application is generalized to the application of several rules during a single step. Parallel grammars represent the subject of this chapter. First, it studies partially parallel generation of languages, after which it investigates the totally parallel generation of language.
14 Jumping models
- + Show details - Hide details
-
p.
479
–543
(65)
Take a typical program p that processes information i within the framework of today's information technologies. During a computational step, p usually reads a piece of information x in i, erases it, generates a new piece of information y, and inserts y into somewhere into i, whereas the position of this insertion may occur far away from the original position of x, which was erased. Therefore, to put it simply, during its computation, p keeps jumping across i as a whole. To investigate this kind of modern computation mathematically, the language theory should provide computer science with appropriate mathematical models. The classical versions of automata and grammars work on words strictly continuously, however. Consequently, they can hardly serve as appropriate models for this purpose. A proper formalization of processors that work in the way sketched above necessitates an adaptation of classical grammars, so they work on words discontinuously. At the same time, any adaptation of this kind should conceptually maintain the original structure of these models as much as possible, so computer science can quite naturally base its investigation upon these newly adapted grammatical models by analogy with the standard approach based upon their classical versions. That is, these new models should work on words in a discontinuous way while keeping their structural conceptualization unchanged. This chapter discusses models that work in this discontinuous way. Indeed, automata and grammars discussed in this section are conceptualized just like their classical versions except that during the applications of their rules, they can jump over symbols in either direction within the rewritten strings, and in this jumping way, they define their languages
15 Deep pushdown automata
- + Show details - Hide details
-
p.
545
–562
(18)
While the ordinary pushdown lists can be modified only on their tops, deep pushdown lists, as their name suggests, can be modified under them. Accordingly, while the ordinary versions of pushdown automata can expand only the topmost pushdown symbols, deep pushdown automata (DPDAs) can make expansions deeper in their pushdown lists; otherwise, they both work identically. This chapter proves that the power of DPDAs is similar to the generative power of regulated context-free grammars without erasing rules. Indeed, just like these grammars, DPDAs are stronger than ordinary pushdown automata but less powerful than context-sensitive grammars. More precisely, they give rise to an infinite hierarchy of language families coinciding with the hierarchy resulting from n-limited state grammars. The chapter is divided into two sections. The former introduces the basic versions of DPDAs. The latter places some natural restrictions on them.
-
Part IV. Applications
Applications
- + Show details - Hide details
-
p.
563
(1)
16 Applications in general
- + Show details - Hide details
-
p.
565
–568
(4)
This chapter makes several general remarks about computational applications of modern language models covered earlier in this book. It also discusses their application perspectives in computer science in the near future. As we know by now, however, all these models represent an enormously large variety of grammars and automata. Therefore, we narrow our attention only to some of them. Specifically, we choose regulated grammars (see Chapter 12), scattered context grammars (see Section 13.1), grammar systems (see Section 13.3), and regulated pushdown automata (see Chapter 12) for this purpose. Regarding the computer-science-application areas, we focus our principle attention on two areas-computational linguistics and computational biology.
17 Applications in syntax analysis: programming languages
- + Show details - Hide details
-
p.
569
–659
(91)
This chapter consists of four sections. Section 17.1 conceptualizes two fundamental approaches to syntax analysis -top-down parsing and bottom-up parsing. Then, Section 17.2 describes the former approach, while Section 17.3 explores the latter. Section 17.4 explains how to implement a syntax-directed translation, which is completely driven by a parser when producing target machine language programs.
18 Applications in syntax analysis: natural languages
- + Show details - Hide details
-
p.
661
–677
(17)
Syntactic analysis of natural languages is a subfield of natural language processing (NLP) that is often claimed to be a “corner stone” of the area, a necessary base for any advanced language processing and real understanding. we describe the syntax analysis of programming languages by using classical language models context -free grammars and pushdown automata. In the present chapter, however, we sketch the syntax analysis of natural languages based upon alternative grammatical models namely scattered context grammars.we have illustrated how to transform and generate grammatical sentences in English by using transformational scattered context grammars, which represent a very natural linguistic apparatus straightforwardly based on scattered context grammars. However, from a more general perspective, we can apply these grammars basically in any area of science that formalizes its results by strings containing some scattered context dependencies.
19 Applications in biology
- + Show details - Hide details
-
p.
679
–691
(13)
In this two-section chapter, we sketch applications of totally parallel grammars with context conditions. That is, we apply their special versions to microbiological organisms. We give three case studies that make use of these grammars. Two case studies are presented of biological organisms whose development is affected by some abnormal conditions, such as a virus infection. From an even more practical point of view, by using these grammars, a powerful and elegant implementation tool is presented in the area of biological simulation and modeling. Specifically, it implements models of growing plants.
-
Part V. Conclusion
Conclusion
- + Show details - Hide details
-
p.
693
(1)
20 Concluding remarks
- + Show details - Hide details
-
p.
695
–720
(26)
This book gives a survey of crucially important mathematical models for languages and computation. Most of these models were introduced and studied within the framework of formal language theory. In essence, this theory represents a mathematically systematized body of knowledge concerning languages and their models, which allow us to formalize and investigate computation strictly scientifically. The book defines languages as sets of finite sequences consisting of symbols. As a result, this general definition encompasses almost all languages, including natural as well as artificial languages, such as programming languages. The strictly mathematical approach to languages necessitates an introduction of mathematical models that define them. The first section of the conclusion summarizes all the material covered in the text. The second section points out modern investigation trends, including open-problem areas, and makes many bibliographical comments.
-
Back Matter
- + Show details - Hide details
-
p.
(1)