## Introduction to Automata Theory, Languages, and ComputationPreliminaries. Finite automata and regular expressions. Properties of regular sets. Context-free grammars. Pushdown automata; Properties of context-free languages. Turing machines. Undecidability. The Cohmsky hierarchy. Heterministic context-free languages. Closure properties of families of languages. Computational complexity theory. Intractable problems. Highlights of other important language classes. |

### What people are saying - Write a review

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

### Contents

Preliminaries | 1 |

Finite Automata and Regular Expressions | 13 |

Properties of Regular Sets | 55 |

Copyright | |

13 other sections not shown

### Other editions - View all

### Common terms and phrases

2DFA algorithm alphabet automata binary cells CFL's class of languages closure properties computation construct contains context-free grammars context-free languages crossing sequences CSL's DCFL DCFL's defined denote deterministic DPDA DSPACE(log empty encoding equivalent Example Exercise finite automaton finite control finite number follows full trio Ginsburg given graph Greibach halts Hamilton circuit homomorphism ID's inductive hypothesis infinite input symbol integers labeled language accepted leftmost length Let G linear log-space log-space reduction Moore machine moves nondeterministic Note NP-complete oracle output pair path polynomial problem productions Proof Let prove PSPACE pumping lemma pushdown automaton r.e. sets recursive function recursive language reduce regular expression regular set rightmost derivation scanned sentential form shown in Fig simulate stack symbol storage tape string subset Suppose tape head tape symbol terminal Theorem TM's transition Turing machine undecidable variables vertex vertices viable prefix word