Posts

Showing posts from January 3, 2010

Books for Theory of Computation

Image
TOC BOOK
Main Reference Book
Subject Name : Theory of Computation

Subject Code : 620007

introduction to languages and the theory of computation
Suggested Additional Reading
Subject Name : Theory of Computation

Subject Code : 620007



michael sipser sipser theory of computation michael sipser introduction to the theory of computation introduction to the theory of computation sipser introduction to the theory of computation by michael sipser introduction to the theory of computation michael sipser introduction to theory of computation sipser intro to theory of computation sipser theory of computation michael sipser sipser computation theory of computation sipser

 hopcroft automata
theory of automata and computation
introduction to automata theory languages and computation
introduction to automata theory languages and computation 3rd edition
introduction to automata theory languages and computation
introduction to automata theory languages and computation 3rd edition
automata theory languages and computation
hopcro…

Strings

Introduction: Strings - Basic Definitions
• Alphabet: Finite set of symbols or characters
– Denoted 
• String: Finite sequence - possibly empty - of symbols from some alphabet 
– Empty string denoted 
– Set of all possible strings over alphabet  denoted

Introduction of TOC

Introduction: Overview • Automata theory deals with the theory of computation
• Theory of computation
– Provides set of abstract structures that can be used for solving certain
classes of problems
*  These problems are independent of any platform (software or hardware)
* Based on mathematical properties of problems and algorithms
– Defines what is computable
* I.e., Identifies the limitations of computability
• Theory can be used to answer questions like
1. Can a given problem be solved computationally?
– If not, is there a restricted solution that is useful?
2. Can a solution be implemented in a fixed amount of time?
3. How efficient is a solution?
4. Can problems be classified wrt their solutions?
• Theory is the basis on which computer science exists
• Theory has many practical applications beyond the purely theoretical issues
• General topics to be discussed:
1. Languages
2. Finite state machines
3. Regular expressions, grammars, and languages
4. Pushdown automata
5. Context free …