Theoretical Computer Science

Name: Theoretical Computer Science
SKU: 1965
Availability: InStock

Book ID: 1965

Author : Dr. Anjali Sardesai

ISBN : 978-93-90646-67-8

This book covers the Sem. V of T.Y. BSc. (Computer Science). Authored by a leading educationist, it is written in easy-to-understand language to help students grasp the essential concepts, as well as intricacies of Theoretical Computer Science. Step-by-step explanations help the students grasp the methodology to solve problems. With solved examples, test questions and previous exams’ questions included, it forms a comprehensive aid to the understanding of the subject and helps the student prepare for the exams.

About Author

Dr. Anjali S. Sardesai is a very well-known lecturer in Department of Computer Science, Modern College of Arts, Science & Commerce, Shivajinagar, Pune – 411005; where she has been teaching for the past 20 years. She has an excellent academic track record during her completion of B.C.S. and M.C.S. from University of Pune. In her total work experience of over 24 years, she has worked in renowned IT company initially for more than 2 years and then she has chosen to work for educational field due to her passion for teaching. As an eligibility criteria for teaching, she has successfully cleared both SET and NET examinations in the same year. She has completed Ph.D. in Computer Science from Savitribai Phule Pune University. She has also completed courses on JAVA, DOTNET & RedHat from different institutes. With this strong academic background and practical IT experience, she has also acquired very good command on subjects such as ‘Theory of Computer Science’, ‘Compiler Construction’, ‘C Programming’, ‘DOTNET’, ‘COM/CORBA’ and ‘UNIX Internals’. She is a member of Board of Studies in Computer Science and worked as a member of Board of Studies in Animation and Board of Studies in Computer Application. She has been worked as a member of Syllabus Reframing Committee and also as a Resource person, for B.Sc.(Computer Science) and M.Sc.(Computer Science), M.C.A.(Science Faculty). Due to her good subject-knowledge and student-friendly teaching style, combined with excellent communication skills, she has become very popular amongst the students.
She had co-authored Practical WorkBooks published by University of Pune for :
F.Y.B.Sc.(Computer Science), T.Y.B.Sc.(Computer Science), F.Y.B.Sc. (Animation), T.Y. B.Sc. (Animation).
She is holding key position as Vice Principal (Academics), IQAC Coordinator and Head, Department of Animation in Modern College of Arts, Science and Commerce, Shivajinagar, Pune-5.

Original price was: ₹420.Current price is: ₹336.

27 in stock

Add to wishlist

Description

Contents

1. Finite Automaton
1. Basic Concept of Language Theory
1.1 Symbol
1.2 Alphabet (?)
1.3 String (or word)
1.4 Formal Language
2. Introduction to Finite Automata
2.1 Deterministic Finite Automata
2.2 Execution Sequence of FA
2.3 Formal Definition of FA
2.4 Different Ways to Represent FA
2.5 Notations Used in FA Representation
2.6 Properties of Transition Functions
2.7 Acceptability of a String by a Finite Automaton
2.8 Language Accepted by a FA – L(M)
2.9 Construction of DFA
3. Non-deterministic Finite Automata
3.1 Formal Definition (NFA)
3.2 Language of an NFA
4. NFA to DFA
4.1 Myhill – Nerode Theorem
4.2 Minimizing FA (MYhill-Nerode Theorem)
4.3 Minimization of DFA
5. Finite Automata with ? – transitions
5.1 Formal Definition (NFA – ? moves)
5.2 String Accepted by ?-NFA
5.3 Language Accepted by ?-NFA
5.4 ?-Closure
5.5 Extended Transitions
6. Conversion of ?-NFA to DFA
7. Finite Automata with Output
7.1 Moore Machine
7.2 Mealy Machine
8. Equivalence of Deterministic and Non-deterministic FA
8.1 Conversion of NFA to Equivalent DFA

2. Regular Expressions and Languages
1. Regular Expression (RE)
1.1 Standard Operations on Languages
1.2 Formal Definition of Regular Expression
2. Regular Expression Identities
3. Regular Language
4. Conversion of RE to FA (Equivalence of Finite Automata and Regular Expression)
6. Pumping Lemma for Regular Languages and Applications
7. Closure Properties of Regular Languages

3. Context Free – Grammars and Languages
1. Fundamental Concepts of Grammar
1.1 What is Grammar?
1.2 Formal Definition of Grammar (Phrase-Structure Grammar)
1.3 Derivation
1.4 Language Generated-by Phrase-Structure Grammar
2. Derivation and Reduction
2.1 Derivation
2.2 Reduction
3. Chomsky Hierarchy
4. Context Free Grammar
4.1 Definition
4.2 Left Most and Right Most Derivation
4.3 Parse Tree/Syntax Tree
5. Ambiguous Grammar
6. Simplification of CFG
6.1 Elimination of Useless Symbols
6.2 Removing UNIT Productions from Grammar
6.3 Removal of ? Productions from a Grammar
6.4 Removal of Nullable Symbols from Grammar
7. Normal Forms
7.1 Chomsky Normal Form (CNF)
7.2 Greibach Normal Form (GNF)
8. Regular Grammar
8.1 Definition: Regular Grammar
8.2 Construction of Regular Grammar equivalent to given DFA
8.3 Construction of Finite Automata from Given Regular Grammar

4. Push Down Automata
1. Introduction
2. Definition of PDA and Examples
2.1 Components of Pushdown Automata
2.2 Model of Pushdown Automaton
2.3 Pictorial Representation of PDA
2.4 Formal Definition of PDA
2.5 Conventions used in PDA
2.6 PDA Moves (Formally defined)
2.7 Instantaneous Description
3. The Languages of PDA (Construction of PDA Using Empty Stack and Final State Method)
3.1 Language Acceptance by Final State
3.2 Language Accepted by Empty Stack
4. DPDA and NPDA
4.1 Deterministic PDA (DPDA)
4.2 Non-Deterministic PDA (NPDA)
4.3 Correction in DPDA and NPDA
5. Equivalence of PDA and CFG
5.1 Conversion of a Context Free Language (in GNF) to Push Down Automata

5. Turing Machine
1. Introduction
2. Turing Machine Model and Definition of TM
3. Definition of Turing Machine
4. Design of a Turing Machine
4.1 Notational Conventions for TM
4.2 Representation of Turing Machine
5. Problems on Language Recognizers
6. Language Accepted by TM
7. Variations of Turing Machines/Types of TM
7.1 Multitrack Turing Machine
7.2 Two-way Turing Machine
7.3 Multitape Turing Machine
7.4 Non-deterministic Turing Machine
8. Introduction to LBA & CSG