## Introduction to Automata Theory, Formal Languages and ComputationFormal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simple and exhaustive approach to topics like automata theory, formal languages and theory of computation. These descriptions are followed by numerous relevant examples related to the topic. A brief introductory chapter on compilers explaining its relation to theory of computation is also given. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Language and Grammar | 21 |

Finite Automata | 47 |

Finite State Machine | 133 |

Regular Expression | 223 |

Contextfree Grammar | 297 |

Pushdown Automata | 377 |

Turing Machine | 429 |

Computability and Undecidability | 486 |

Recursive Function | 526 |

Computational Complexity | 543 |

Basics of Compiler Design | 584 |

Advance Topics Related to Automata | 615 |

625 | |

627 | |

Variations of the Turing Machine | 464 |

### Common terms and phrases

accepted algorithm binary called circuit combination compatible graph Construct contains context-free grammar Convert the following denoted derivation Design deterministic e-closure empty stack Example ﬁnal finite automata FIRST(e following grammar given in Fig halting problem information lossless input string input symbol input tape integer label language set left recursion leftmost matrix Mealy machine merger graph minimized machine modified Moore machine node non-deterministic non-terminal NP complete null production null string output palindrome parse tree parser parsing table polynomial Present production rules proved pumping lemma q 0 q q 1 q Q ql recursively enumerable recursively enumerable language regular expression removed replaced sequence Solution stack top Step subset terminal testing graph testing table theorem transitional diagram transitional function Turing machine undecidable unit production vertex