Vor Ort
Merkzettel Warenkorb
Produktbild: Formal Languages and Automata Theory

Formal Languages and Automata Theory

27,99 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

02.08.2012

Verlag

Oxford University Press

Seitenzahl

380

Maße (L/B/H)

23,4/18/1,8 cm

Gewicht

517 g

Sprache

Englisch

ISBN

978-0-19-807106-8

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

02.08.2012

Verlag

Oxford University Press

Seitenzahl

380

Maße (L/B/H)

23,4/18/1,8 cm

Gewicht

517 g

Sprache

Englisch

ISBN

978-0-19-807106-8

Herstelleradresse

Libri GmbH
Europaallee 1
36244 Bad Hersfeld
DE

Email: gpsr@libri.de

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)
  • Produktbild: Formal Languages and Automata Theory


    • AUTOMATA, FORMAL LANGUAGES AND COMPUTABILITY

    • 1.1 Formal Languages

    • 1.1.1 Phrase Structure Grammars

    • 1.2 Chomsky Classification of Grammars

    • 1.3 Computability

    • Supplementary Examples

    • A Quick Review

    • Problems for Practice

    • Objective Type Questions


    • MATHEMATICAL PRELIMINARIES

    • 2.1 Set Theory

    • 2.2 Relations

    • 2.2.1 Types of Relations

    • 2.3 Functions

    • 2.4 Counting Techniques

    • 2.4.1 Permutations

    • 2.4.2 Combinations

    • 2.4.3 Pigeonhole Principle

    • 2.5 Logic

    • 2.5.1 Propositions and Logic

    • 2.6 Methods of Proof

    • 2.6.1 Direct Proof

    • 2.6.2 Indirect Proof

    • Supplementary Examples

    • A Quick Review

    • Problems for Practice

    • Objective Type Questions


    • FINITE AUTOMATA

    • 3.1 Finite Automata

    • 3.1.1 String processing by finite automaton

    • 3.2 Properties of transition function

    • 3.3 Deterministic and Nondeterministic Finite Automaton

    • 3.3.1 Acceptance of a string by NFA

    • 3.4 Equivalence of NFA and DFA

    • 3.4.1 Converting a NFA to equivalent DFA

    • 3.4.2 Equivalence of DFAs

    • 3.5 Level Equivalence and Reduction in Finite Automaton

    • 3.6 Finite automata with outputs

    • 3.6.1 Moore and Mealy Machines

    • 3.6.2 Conversion of a Moore Machine to equivalent Mealy Machine

    • 3.6.3 Conversion of a Mealy Machine to equivalent Moore Machine

    • 3.7 Finite automata with null moves

    • 3.7.1 Removal of null moves

    • Supplementary Examples

    • A Quick Review

    • Problems for Practice

    • Objective Type Questions


    • REGULAR SETS AND REGULAR GRAMMAR

    • 4.1 Regular Expression

    • 4.2 Correspondence between regular expression and regular set

    • 4.3 Identities related to regular expressions

    • 4.4 Relation between Regular Languages and Finite Automata

    • 4.4.1 Finite automaton corresponding to regular expression

    • 4.4.2 Regular expression corresponding to finite automaton

    • 4.5 Closure properties of regular sets

    • 4.6 Automata for union, intersection and difference of languages

    • 4.7 Pumping Lemma for regular Languages

    • 4.7.1 Applications of pumping lemma

    • 4.7.2 Suitability of pumping lemma

    • 4.8 Production System associated with regular grammar

    • 4.9 Myhill Nerode Theorem (Equivalent Classes and Regular Languages)

    • 4.10 Some Decision Problems related to Finite Automata and Regular Langauges

    • 4.11 Regular language and current programming language scenario

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • CONTEXT FREE GRAMMARS AND LANGUAGES

    • 5.1 Some example recursive grammars

    • 5.2 Context Free Grammars

    • 5.2.1 Leftmost and Rightmost Derivation of a string

    • 5.2.2 Some example context free languages and grammars

    • 5.2.3 Ambiguity in Context Free Grammar and Parse Tree

    • 5.2.4 Possible defects in CFG and their removal

    • 5.2.4.1 Failure of non terminal(s) to generate terminal(s)

    • 5.2.4.2 Problem of unit productions

    • 5.2.4.3 Problem of unreachable non terminal

    • 5.2.4.4 Problem of null productions

    • 5.3 Context Free languages as superset of regular languages

    • 5.4 Closure properties of Context Free languages

    • 5.4.1 Intersection of a CFL and a regular language

    • 5.5 Normal Forms for CFGs

    • 5.5.1 Chomsky Normal Form

    • 5.5.2 Greibach Normal Form

    • 5.6 Pumping lemma for Context Free Grammars

    • 5.6.1 Applications of pumping lemma

    • 5.7 More on closure properties

    • 5.7 Applications of Context Free Grammars

    • 5.7.1 Programming language Constructs

    • 5.7.2 Natural Language

    • 5.7.3 Markup Languages

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • PUSHDOWN AUTOMATA

    • 6.1 Basic Structure of Pushdown Automata

    • 6.2 Two types of acceptance by PDA

    • 6.3 Correspondence between PDA and CFL

    • 6.3.1 PDA corresponding to a given CFG

    • 6.3.2 CFG corresponding to a given PDA

    • 6.4 Parsing and PDA

    • 6.4.1 Design of Top Down Parser

    • 6.4.2 Design of a Bottom up Parser

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • TURING MACHINES

    • 7.1 Basic structure and working of a Turing Machine

    • 7.2 Instantaneous Description of a Turing Machine

    • 7.3 Language of a Turing machine

    • 7.4 Turing Machine as computer for positive integers

    • 7.5 Universal Turing machine (UTM)

    • 7.5.1 UTM and Modern Day Computer

    • 7.6 Enhancements in Turing Machine

    • 7.6.1 Multi-track Turing Machine

    • 7.6.2 Multi-tape Turing Machine

    • 7.7 Turing Machine as Enumerator

    • 7.8 Non-Deterministic and Deterministic Turing machine

    • 7.9 lternative representations of Turing Machines

    • 7.9.1 Turing Machine with semi infinite Tape

    • 7.9.2 Two stack machine

    • 7.10 Time and Space Complexity of a Turing Machine

    • 7.11 Some other machines

    • 7.11.1 Linear Bound Automata

    • 7.11.2 Post Machine

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • THE PITFALL OF ALGORITHMIC COMPUTING: UNDECIDABILITY

    • 8.1 Recursive and Non Recursive Languages

    • 8.2 Language of Turing machines

    • 8.3 Some decision problems relating to Turing Machines

    • 8.4 Some Decision Problems relating to CFG

    • 8.5 Post Correspondence Problem

    • 8.5.1 Constructing CFG using PCP

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • COMPUTABLE FUNCTIONS

    • 9.1 Primitive Recursive Functions

    • 9.2 µ Recursive Functions

    • 9.2.1 Computability and µ Recursive Functions

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions


    • COMPUTATIONAL COMPLEXITY: TRACTABLE AND POSSIBLY INTRACTABLE PROBLEMS

    • 10.1 Growth Rates of Functions

    • 10.2 Languages and complexity classes

    • 10.3 Decision Problems and Optimization Problems

    • 10.4 The classes P and NP

    • 10.5 NP Complete Problems

    • 10.6 Significance of discovering NP complete problems

    • 10.7 Some misconceptions about NP-complete problems

    • Supplementary Examples

    • A Quick Overview

    • Problems for Practice

    • Objective Type Questions

    • APPENDIX A

    • Church-Turing hypothesis

    • APPENDIX B

    • Godel Numbering

    • APPENDIX C

    • Homage to key scientists in the field of automata theory and computation

    • APPENDIX D

    • Chronology of Some Important Events