Logic and Language Models for Computer Science

Dana Richards, Henry Hamburger;;;

• Éditeur: WSPC
• Année: 2017
• ISBN:
  9789813229228
• Édition: 3
• Sujet: Informatica
• Sous-sujet: Elaborazione del linguaggio naturale

-->

This text presents the formal concepts underlying Computer Science.

It starts with a wide introduction to Logic with an emphasis on reasoning and proof, with chapters on Program Verification and Prolog.

The treatment of computability with Automata and Formal Languages stands out in several ways:

-->

• it emphasizes the algorithmic nature of the proofs and the reliance on simulations;
• it stresses the centrality of nondeterminism in generative models and the relationship to deterministic recognition models

-->

The style is appropriate for both undergraduate and graduate classes.

--> Contents:

• • Mathematical Preliminaries
• Logic for Computer Science:
  • Propositional Logic
  • Proofs by Deduction
  • Predicate Logic
  • Proving with Predicates
  • Program Verification
• Language Models for Computer Science:
  • Language and Models
  • Generative Models of Regular Languages
  • Finite Automata and Regular Languages
  • Context-Free Grammars
  • Pushdown Automata and Parsing
  • Turing Machines
• Appendices:
  • Logic Programming
  • The awk Language
  • Answers to Selected Problems

-->
--> Readership: Students and professionals interested in theoretical computation and language models for computer science. -->
Keywords:Theory of Computation;Logic Automata Theory;Formal LanguagesReview: Key Features:

• The emphasis is on Logic. Logic is described in the context of reasoning (not circuits) with a concentration on proof techniques. The discussion entails a chapter on Program Verification and a chapter on Prolog programming
• There is a forthright treatment of non-determinism. Non-determinism is fundamental to generative techniques, like grammatical models and recursively defined constructs such as regular expressions, and are integral to machine models of context-free languages
• The treatment of constructive proofs (in particular, simulation-based proofs of computability) are cast in explicit algorithmic notation, which is familiar to the Computer Science student

Chapter 1

Mathematical Preliminaries

This text is concerned with formal models that are important to the field of computer science. Because the models are formal, we will make substantial use of mathematical ideas. In many ways the topics in this book — logic, languages and automata — are a natural extension of a Discrete Mathematics course, which is generally required for Computer Science majors. This text steers clear of excessive mathematical notation, focusing instead on fundamental ideas and their application. However it is impossible to appreciate the power that comes from the rigorous methods and models in this book without a background in Discrete Mathematics. This chapter is a brief overview of the needed mathematical background and may be useful for self-evaluation, review and reference.

1.1Sets and Sequences

A set is a unordered collection of distinct elements. The elements are typically thought of as objects such as integers, people, books, or classrooms, and are written within braces, like this: {Friday, Saturday, Sunday}. When working with sets, it can be important to specify U, the universe of elements (e.g., the set of days of the week) from which the elements of particular sets are drawn. Note that the universe itself is a set: the set of all elements of a given type.

Sometimes the universe is only implicitly specified, when the reader can easily figure out what it is. The elements are said to be in the set and are called its members.

Sets can be presented in two forms. The extensional form enumerates the elements of the set, while the intensional form specifies the properties of the elements. For example:

are extensional and intensional forms of the same set. The second of these is read “those x such that x is an integer and … ” Note that the universe, the set of integers, is implicit in the first example and only informally specified in the second. The empty set is a set with no element and is denoted

.

Because the elements of a set are distinct, you should write sets with no repetition. For example, suppose a student database includes countries of origin and that it shows the participants in a seminar as being from China, France, China, Egypt and France. Then the set of countries represented in this class is {China, France, Egypt}. There is no concept of ordering within a set; there is no “first” element, etc. For example, the sets {4, 2, 3} and {2, 3, 4} are the same set.

If ordering is important then one speaks of a sequence of elements. In the extensional form of a sequence the elements appear in order, within parentheses, not braces. For example, the sequence (4, 2, 3) is different from (2, 3, 4). Further, sequences need not have distinct elements, so the sequence (2, 3, 3, 4) is different from (2, 3, 4). A sequence of length 2 is called an ordered pair. A sequence of length 3, 4 or 5 is called a triple, quadruple or quintuple respectively; in the general case of length n, the word is n-tuple. Sequences are often implemented as one-dimensional arrays or as linked lists. This leads to an intensional form for sequences, where we use subscripts, so that the extensional notation, like (x₁, x₂, x₃), can replaced with a direct definition of x_i, for each i.

The cross-product of S₁ and S₂, denoted S₁ × S₂, is the set of ordered pairs of elements in which the first is in S₁ and the second is in S₂.

Formally,

For example, {a, b} × {c, d, e} = {(a, c), (a, d), (a, e), (b, c), (b, d), (b, e)}. Just as the elements of S₁ × S₂ are ordered pairs, the elements of S₁ × S₂ × S₃ are triples, and so on.

Set operators are discussed later, but we start with two basic ideas, the notions of membership and comparison. The notation x

S means that x is an element of the set S, while x

S means that x is not in S. When S = {11, 12, 13, 14}, 12

S and 16

S. We say that S₁ is a subset of S₂, written S₁

S₂, if each element of S₁ is also an element of S₂. For example, {12, 14}

{11, 12, 13, 14}. Note that S

S. Now consider subset T, that is not equal to S, because it is missing one or more elements of S. While it is correct to write T

S we may choose to write T

S, which states that T is a proper subset of S. The empty set is a subset of any set, so we can write

S, for any set S.

1.2Relations and Functions

A binary relation is a set of ordered pairs. More formally, a relation R from the set S₁ to the set S₂ is a subset of the cross-product of those sets, R

S₁ × S₂. For example, if E is a set of employees and P is a set of projects, we can specify a relation R between...