Theory of computation by klp mishra pdf

International Edition Textbooks may bear a mishea Not for sale in the U. Advanced Book Search Browse by Subject. The book is designed to meet computtion needs of the undergraduate and postgraduate students of computer science and engineering as well as those of the students offering courses in computer applications. My library Help Advanced Book Search. Turing Machines and Linear Bounded Automata.

Sign In Register Help Cart. This Third Edition, in response to the enthusiastic reception given by academia and students to the previous edition, offers a cohesive presentation of all aspects of theoretical computer science, namely automata, formal languages, computability, and complexity. Solutions or Hints to Chapter-end Exercises. 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. The table giving the truth values of such a proposition obtained by replacing the propositional variables by arbitrary propositions is called the truth table of ex. If ex involves n propositional constants, then we have 2" possible combinations of truth values of propositions replacing the variables.

Solution The truth values of the given formula are shown in Table 1. P v --, P has the truth value T irrespective of the truth value of P. Such formulas are called tautologies. Note: When it is not clear whether a given formula is a tautology. Solution We give the truth values of ex in Table 1. Note: ex is a contradiction if and only jf --, ex is a tautology. We construct the truth values of [f.

As the truth value of a tautology is T, irrespective of the truth values of the propositional variables. Similarly, we denote any contradiction by F. We call them Identities and give a list of such identities in Table 1. The identities 12 can be used to simplify fOTI11ulas.

Solution L. Oil 11 1. We also know that two such fonnulas are equivalent if and only if they have the same truth table. The number of distinct truth tables for fonnulas in P and Q is So the number of distinct truth tables is Thus there are only 16 distinct nonequivalent fonnulas, and any fonnula in P and Q is equivalent to one of these 16 fonnulas. In this section we give a method of reducing a given fonnula to an equivalent fonn called the 'nonnal fonn'.

We also use 'sum' for disjunction, 'product' for conjunction, and 'literal' either for P or for -, P, where P is any propositional variable. DefInition 1. An elementary sum is a sum of literals. And P v -, Q, P v -, R are elementary sums. We can use I 1e, l. The resulting fonnula has -, only before the propositional variables, i. The resulting fonnula will be a sum of products of literals, i. For the same formula, we may get different disjunctive normal forms.

The advantages of constructing the principal disjunctive normal form are: i For a given formula, its principal disjunctive normal form is unique. Use the idempotent laws to avoid repetition of minterms. There are no contradictions. So we have to introduce the missing variables step 3. For L;. The minterms in the two variables P and Q are 00, 01, 10, and 11, Each wff is equivalent to its principal disjunctive normal form.

As the number of subsets is 24 , the number of distinct formulas is Refer to the remarks made at the beginning of this section. The truth table and the principal disjunctive normal form of a are closely related. Each minterm corresponds to a particular assignment of truth values to the variables yielding the truth value T to a.

So, if the truth table of a is given. Find the principal disjunctive normal form. If a is in disjunctive normal form, then --, a is in conjunctive normal form. This can be seen by applying the DeMorgan's laws. So to obtain the conjunctive normal form of a, we construct the disjunctive normal form of --, a and use negation. Deimition 1. For obtaining the principal conjunctive normal form of ex, we can construct the principal disjunctive normal form of -, ex and apply negation.

T and F act as bounds i. In this section we give some important rules of logical reasoning or rules of inference. The propositions that are assumed to be true are called h potheses or premises.

The proposition derived by using the rules of inference is called a conclusion. The process of deriving conclusions based on the assumption of premises is called a valid argument.

The rules of inference are simply tautologies in the form of implication i. We write this in the form Q. Here P denotes a premise. Pv The proposition below the line. P v Q is the conclusion. Of course, we can derive more rules of inference and use them in valid arguments. For valid arguments, we can use the rules of inference given in Table 1. As the logical identities given in Table 1. On the left. On the right, we indicate whether the proposition is a premise hypothesis or a conclusion.

If it is a conclusion. S v P Premise iv 9. S Lines 7, 8 and disjunctive syllogism Rh Thus, we can conclude 5 from the given premises.

R Premise iv 5. Computer Science or MBA, then he is assured of a good job. If Ram is assured of a good job, he is happy. Ram is not happy. So Ram has not completed MBA. Solution We can name the propositions in the following way: P denotes 'Ram has completed B.

Computer Science '. Q denotes 'Ram has completed MBA'. R denotes 'Ram is assured of a good job'. S denotes 'Ram is happy'. If every cow is white then it has four legs. If every cow has four legs then every buffalo is white and brisk. The milk is black. Therefore, the buffalo is white. Solution We name the propositions in the following way: P denotes 'The milk is black'.

Q denotes 'Every cow is white'. R denotes 'Every cow has four legs'. S denotes 'Every buffalo is white'. T denotes 'Every buffalo is brisk'.

P Premise i v 2. Q Modus ponens RIJ, 4. R Modus ponens RIJ, 6. As propositions, there is no relation between them, but we know they have something in common.

Both Ram and Sam share the property of being a student. By replacing x by Ram or Sam or any other name , we get many propositions. The common feature expressed by 'is a student' is called a predicate. In predicate calculus we deal with sentences involving predicates. Statements involving predicates occur in mathematics and programming languages.

Some logical deductions are possible only by 'separating' the predicates. For example, 'is a student' is a predicate. P x can denote 'x is a student'. In this sentence, x is a variable and P denotes the predicate 'is a student'.

The sentence 'x is the father of y' also involves a predicate 'is the father of. Here the predicate describes the relation between two persons. As P x involves a variable x, we cannot assign a truth value to P x. However, if we replace x by an individual object, we get a proposition. For example, if we replace x by Ram in P x , we get the proposition 'Ram is a student'. We can denote this proposition by P Ram. If we replace x by 'A cat', then also we get a proposition whose truth value is F.

Similarly, S 2, 0, 1 is the proposition 2. Also, S l, 1, 1 is the proposition 2. The following definition is regarding the possible 'values' which can be assigned to variables. Note: In most examples. Remark We have seen that by giving values to variables, we can get propositions from declarative sentences involving predicates. Some sentences involving variables can also be assigned truth values. For example, consider 'There exists x such that.

Both these sentences can be assigned truth values T in both cases. Universal and Existential Quantifiers The phrase 'for all' denoted by V is called the universal quantifier. The phrase 'there exists' denoted by 3 is called the existential quantifier. P x in Vx P x or in 3x P x is called the scope of the quantifier V or 3.

Note: The symbol V can be read as 'for every', 'for any', 'for each', 'for arbitrary'. The symbol 3 can be read as 'for some', for 'at least one'. When we use quantifiers, we should specify the universe of discourse. If we change the universe of discourse, the truth value may change. If the universe of discourse is the set of all integers. If the universe of discourse is the set of all real numbers. The following example illustrates the use of connectives.

All students are clever. Some students are not successful. Every clever student is successful. There are some successful students who are not clever. Some students are clever and successful. Solution As quantifiers are involved.

We can take the universe of discourse as the set of all students. Let C x denote 'x is clever'. Let Sex denote 'x is successful'. Then the sentence 1 can be written as 'IIx C x. Note: A proposition can be viewed as a sentence involving a predicate with 0 Variables. So the propositions are wffs of predicate calculus by rule i. We call wffs of predicate calculus as predicate formulas for convenience.

The well-formed formulas introduced in Section 1. Then ex and f3 are equivalent to each other over U if for every possible assignment of values to each variable in ex and [3 the resulting statements have the same truth values.

Remark In predicate formulas the predicate val;ables mayor may not be quantified. We can classify the predicate variables in a predicate formula, depending on whether they are quantified or not.

This leads to the following definitions. An occurrence of x is free if it is not a bound occurrence. A predicate variable in a is free if its occurrence is free in any part of a. The occurrence of X3 in ex is free. Note: The quantified parts of a predicate formula such as "Ix P x or 3x P x are propositions. We can assign values from the universe of discourse only to the free variables in a predicate f01lliula a. Defmition 1. We note that valid predicate formulas correspond to tautologies among proposition formulas and the un satisfiable predicate formulas correspond to contradictions.

Therefore, all the rules of inference for the proposition formulas are also applicable to predicate calculus wherever necessary. For predicate formulas not involving connectives such as A x , P x, y. For Example, corresponding to 16 in Table 1. Corresponding to RI3 in Table 1. Thus we can replace propositional variables by predicate variables in Tables 1. Some necessary equivalences involving the two quantifiers and valid implications are given in Table 1.

Also, when the conclusion involves quantifiers, we may have to introduce quantifiers. The necessary rules of inference for addition and deletion of quantifiers are given in Table 1.

RI ,4 : Existential instantiation? P c c is some element for which P c is true. Rl 1s : Universal generalization P x 'ix P x x should not be free in any of the given premises.

Ram is a graduate. Ram is educated. Solution Let G x denote 'x is a graduate'. Let E x denote 'x is educated'.

Let R denote 'Ram'. So the premises are i 'If. The conclusion is E R. Ram can read and write. Therefore, Ram is a graduate. Let L x denote 'x can read and write'. The conclusion is G R. G R is not a tautology.

So we cannot derive G R. For example, a school boy can read and write and he is not a graduate. No well-behaved person is quarrelsome. Ram is not quarrelsome. Solution Let the universe of discourse be the set of all educated persons.

Let PCx denote 'x is well-behaved'. Let Q x denote 'x is quarrelsome'. So the premises are: i 'II. Y PCx. To obtain the conclusion. Thus the argument is valid. Solution Let P denote 'This book is interesting'. Let Q denote 'The exercises are difficult'. Let R denote 'The subject is difficult'. From the truth table, we conclude that ex is a tautology. Contrapositive-If two of the sides of a triangle are not equal, then. Opposite-If there is unemployment in India. I didn't get first class.

So either I didn't get the notes or I didn't study well. Solution Let P denote '1 get the notes'. This book is useful in GATE as well as for academics to score decent marks. We are providing this PDF for free, you can download it for free here.

If you found this blog helpful to you then please feel free to tell us, and If you want any pdf which is not available here, unfortunately. If you have any rare pdf you can support us by sending it to collectallpdf gmail. Social Plugin. Most Recent. Mishra is the author of Theory Of Computer Science avg rating, 67 ratings, 7 reviews , Theory of Computer Science avg rating, 58 ratin.

Automata, Languages and Computation. Formerly Professor. Department of Electrical. Regular Sets and Regular Grammars.