Goodreads helps you keep track of books you want to read. Want to Read saving…. Want to Read Currently Reading Read. Theory Of Computer Sci
|Published (Last):||24 May 2009|
|PDF File Size:||4.11 Mb|
|ePub File Size:||5.31 Mb|
|Price:||Free* [*Free Regsitration Required]|
Each construction is immediately followed by an example and only then the formal proof is given so that the student can master the technique involved in the construction before taking up the formal proof. The key feature of the book that sets it apart from other books is the provision of detailed solutions at the end of the book to chapter-end exercises. The chapter on Propositions and Predicates Chapter 10 of the second edition is now the first chapter in the new edition.
The changes in other chapters have been made without affecting the structure of the second edition. The chapter on Turing machines Chapter 7 of the second edition has undergone major changes. A novel feature of the third edition is the addition of objective type questions in each chapter under the heading Self-Test. This provides an opportunity to the student to test whether he has fully grasped the fundamental concepts. Besides, a total number of 83 additional solved examples have been added as Supplementary Examples which enhance the variety of problems dealt with in the book.
Preface The sections on pigeonhole principle and the principle of induction both in Chapter 2 have been expanded. In Chapter 5, a rigorous proof of Kleene's theorem has been included. The chapter on LR k grammars remains the same Chapter 8 as in the second edition. Chapter 9 focuses on the treatment of Turing machines TMs. A new section on high-level description of TM has been added and this is used in later examples and proofs.
Some techniques for the construction of TMs have been added in Section 9. The multitape Turing machine and the nondeterministic Turing machine are discussed in Section 9. A new chapter Chapter 10 on decidability and recursively enumerable languages is included in this third edition. In the previous edition only a sketchy introduction to these concepts was given. Some examples of recursively enumerable languages are given in Section The halting problem of TM is discussed in Section Chapter 11 on computability is Chapter 9 of the previous edition without changes.
Chapter 12 is a new chapter on complexity theory and NP-complete problems. Cook's theorem is proved in detail. A section on Quantum Computation is added as the last section in this chapter.
Although this topic does not fall under the purview of theoretical computer science, this section is added with a view to indicating how the success of Quantum Computers will lead to dramatic changes in complexity theory in the future.
The book fulfils the curriculum needs of undergraduate and postgraduate students of computer science and engineering as well as those of MCA courses. Though designed for a one-year course, the book can be used as a one- semester text by a judicious choice of the topics presented.
Special thanks go to all the teachers and students who patronized this book over the years and offered helpful suggestions that have led to this new edition. In particular, the critical comments of Prof. Umaparvathi, Professor of Mathematics, Seethalakshmi College, Tiruchirapalli are gratefully acknowledged.
Mishra N. THEN 1. Qo, F A transition system 3. Propositions are statements used in mathematical logic, which are either true or false but not both and we can definitely say whether a proposition is true or false. In this chapter we introduce propositions and logical connectives.
Normal forms for well-formed formulas are given. Predicates are introduced. When a proposition is true, we say that its truth value is T. When it is false, we say that its truth value is F. New Delhi is the capital of India. The square of 5 is Every college will have a computer by A. Mathematical logic is a difficult subject. Chennai is a beautiful city. Bring me coffee. This statement is false. The sentences are propositions. The sentences 1 and 2 have the truth value T. The sentence 3 has the truth value F.
Although we cannot know the truth value of 4 at present. For the same reason, the sentences 5 and 6 are propositions. To sentences 7 and 8, we cannot assign truth values as they are not declarative sentences. The sentence 9 looks like a proposition. However, if we assign the truth value T to sentence 9, then the sentence asserts that it is false.
If we assign the truth value F to sentence 9, then the sentence asserts that it is true. Thus the sentence 9 has either both the truth values or none of the two truth values , Therefore, the sentence 9 is not a proposition, We use capital letters to denote propositions, 1. But a new sentence obtained from the given propositions using connectives will be a proposition only when the new sentence has a truth value either T or F but not both. The truth value of the new sentence depends on the logical connectives used and the truth value of the given propositions.
We now define the following connectives. There are five basic connectives. Usually, the truth values of a proposition defined using a connective are listed in a table called the truth table for that connective Table 1. TABLE 1. This OR is known as inclusive OR, i. Here we have defined OR in the inclusive sense. We will define another connective called exclusive OR either P is true or Q is true, but not both, i.
But in natural languages this need not happen. For example. Obviously, we cannot write the second sentence in place of the first sentence.
Implication IF Then the proposition a is true as P is false and Q is false and the proposition b is false as P is true and Q is false. The above example illustrates the following: 'We can prove anything if we start with a false assumption. Q provided P'. Solution Let P be the proposition 'It is raining'. Let Q be the proposition 'I have the time'. Let R be the proposition '1 will go to a movie'. The truth tables of these two propositions are identical irrespective of any proposition in place of P and any proposition in place of Q.
SO we can develop the concept of a propositional variable corresponding to propositions and well-formed formulas corresponding to propositions involving connectives. Definition 1. We note that usually a real variable is represented by the symbol x.
This means that x is not a real number but can take a real value. Similarly, a propositional variable is not a proposition but can be replaced by a proposition. Another way of defining a mathematical object is by recursion. Initially some objects are declared to follow the definition. The process by which more objects can be constructed is specified. This way of defining a mathematical object is called a recursive definition.
This corresponds to a function calling itself in a programming language. The factorial n! The recursive definition of n! For example, in propositions we can remove the outermost parentheses.
We can also specify the hierarchy of connectives and avoid parentheses. For the sake of convenience, we can refer to a wff as a formula.
Theory Of Computer Science: Automata, Languages And Computation