This book has been written for B.E. (IT & CS), MCA, BSc, BCA, MSc and other computer programmes students keeping in view the following special points : • Conceptual clarity and practical orientation. • To learn the basic concept used in the design and analysis of Theory of Computation. • Introduces the principles of Theory of Computation. • Provides various methods and techniques suitable for a variety of applications. • Covers all aspects of automata. • Covers abundance of examples and their solutions.
Additional Info
  • Publisher: Laxmi Publications
  • Language: English
  • ISBN : 978-93-83828-25-8
  • Chapter 1

    Introduction to Automata Theory Price 2.99  |  2.99 Rewards Points

    A formal language is an abstraction of the general characteristics of programming languages. A formal language consists of a set of symbols and some rules of formation by which these symbols can be combined into entities called sentences. A formal language is the set of all strings permitted by the rules of formation.
  • Chapter 2

    Automata Price 2.99  |  2.99 Rewards Points

    An automation is defined as a system where energy, material and information is transformed, transmitted and used for performing some functions without direct participation of man. Examples are automatic machine tools, automatic packing machines and automatic photo printing machines.
  • Chapter 3

    Formal Language Price 2.99  |  2.99 Rewards Points

    A formal language is an abstraction of the general characteristics of programming languages. A formal language consists a set of symbols and some rules of formation by which these symbols can be combined into entities called sentences. A formal language is a set of all strings permitted by the rules of formation.
  • Chapter 4

    Regular Expression Price 2.99  |  2.99 Rewards Points

    A finite automata is having number of finite states and have a set of transitions from one state to another on input symbols with as alphabet Σ (Set of finite input alphabets). In this one state is denoted as initial state (q0) and the final state is said to be as accepting state.
  • Chapter 5

    Context Free Grammar Price 2.99  |  2.99 Rewards Points

    Grammar is a set of formal rules that checks the correctness of the sentences. We can construct correct sentences using these rules. These sentences are known as grammatic sentences and the rules as “syntax”. A grammar which deals with the constituent structure in the sentence is called as phrase “structure grammar”.
  • Chapter 6

    Pushdown Automata Price 2.99  |  2.99 Rewards Points

    As regular expression has equivalent automaton i.e., the finite automaton, similarly all context free grammars have an equivalent machine i.e., pushdown automaton. The pushdown automation is essentially a finite automaton with control of both an input take and a stack or “first-in-last-out” list. A symbol may be entered or removed only at the top of the list. When a symbol is entered at the top, the symbol previously at the top becomes second from the top, the symbol previously second from the top becomes third and so on. Similarly, when a symbol is removed from the top of the list, the symbol previously second from the top becomes the top symbol the symbol previously third from the top becomes the second and so on.
  • Chapter 7

    Turing Machine Price 2.99  |  2.99 Rewards Points

    Turing machines are basic abstract symbol manipulating devices which, despite their simplicity, can simulate the logic of any computer algorithm described by Alen Turing in 1936. A simple Turing machine consists of a tape of a theoretically infinite size consisting of cells or sections on the tape. Each cell can hold on it a symbol, which is written by the head and which can modify the current state of the machine.
  • Chapter 8

    Types of Turing Machine Price 2.99  |  2.99 Rewards Points

    Multiple Track Turing Machine This turing machine has K tracks (K > 0) and one read and write head that reads and write all of them one by one. Its instruction set is appropriately modified so that each transition is labelled by a K-tuple that defines the symbol to be read from and the symbols to be written to each of K track as compared to single track turing machine.
  • Chapter 9

    Computability Price 2.99  |  2.99 Rewards Points

    Computational complexity theory is a branch of the theory of computation in computer science that investigates the problems related to the resources required to design algorithms and the inherent difficulties in providing algorithm that are efficient for both general and specific computational problems.
  • Chapter 10

    Context Sensitive Language Price 2.99  |  2.99 Rewards Points

    A context sensitive grammar (CSG) is a formal grammar in which the left-hand sides and the right-hand sides of any production rule is surrounded by a context of terminal and non-terminal symbols. The concept of context sensitive grammar was introduced by Noam Chomsky in the 1950s. A formal language that can be described by a context sensitive grammar is called a context sensitive language.

About the Author