scientific article; zbMATH DE number 1517989
The first edition of this book appeared in (1979; Zbl 0426.68001). Now-a-days the subject is a course for undergraduate students in Engineering and Technology Courses. Taking this aspect into account, the authors have formulated the chapters. The following is the table of contents of the present edition: 1. Automata: The Method and the Madness; 2. Finite Automata; 3. Regular Expressions and Languages; 4. Properties of regular Languages; 5. Context-Free Grammars and Languages; 6. Pushdown Automata; 7. Properties of Context-Free Languages; 8. Introduction to Turing Machines; 9. Undecidability; 10. Intractable Problems; 11. Additional Classes of Problems. Each chapter comprises exercises, summary and references. Figures are given to make the understanding clear. The coverage includes Chomsky and Greibach normal forms, Kruskal's algorithm, Ogden's lemma, Post's correspondence problem, pumping lemma, Rice's theorem, Savitch's theorem and the travelizer salesman problem. The following exercises typifies the standard of the problems: 1. Suppose that \(p\) and \(q\) are distinguishable states of a given DFA \(A\) with \(n\) states. As a function of \(n\), what is the tighest upper bound on how. Long the shortest strint that distinguishes \(p\) and \(q\) can be? 2. Design a contxt-free grammar for the language \(\{0^n 1^n:n\geq 1\}\), that is, the set of all strings of one or more \(0\)'s followed by an equal number of \(1\)'s. 3. Design a Turing machine for the language: the set of strings with an equal number of \(0\)'s and \(1\)'s. Before taking a course on Automata, Formal language and Computation, students should have studied Discrete Mathematics, common data structures and compilers. The get-up and printings are attractive.
- Powers of rationals modulo 1 and rational base number systems
- A Rice-style theorem for parallel automata
- Abstract models for dialogue protocols
- Processes with local and global liveness requirements
- On \(\tau\)-adic representations of integers
- On the closure of pattern expressions languages under intersection with regular languages
- An application of quantum finite automata to interactive proof systems
- Statistical mechanics of complex systems for pattern identification
- On the Hopcroft's minimization technique for DFA and DFCA
- Compositionally progressive solutions of synchronous FSM equations
- Deciding equivalence of top-down XML transformations in polynomial time
- A characterization of regular circular languages generated by marked splicing systems
- Computational bounds on polynomial differential equations
- On regular tree languages and deterministic pushdown automata
- Extracting symbolic knowledge from recurrent neural networks -- a fuzzy logic approach
- Automata theory based on complete residuated lattice-valued logic: Pushdown automata
- Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic
- Closure and decidability properties of some language classes with respect to ciliate bio-operations.
- A language measure for supervisory control
- Algorithmic complexity of recursive and inductive algorithms
- Experience, generations, and limits in machine learning
- Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets
- Combining Benders decomposition and column generation for multi-activity tour scheduling
- Passive testing with asynchronous communications and timestamps
- Regular language representations in the constructive type theory of Coq
- Growth in higher Baumslag-Solitar groups
- Regular patterns, regular languages and context-free languages
- Weak call-by-value lambda calculus as a model of computation in Coq
- Inductive synthesis of cover-grammars with the help of ant colony optimization
- Semiautomatic structures
- Disturbance decoupling in nonlinear hybrid systems
- On the gap between separating words and separating their reversals
- Coding tree languages based on lattice-valued logic
- Model approach to grammatical evolution: deep-structured analyzing of model and representation
- Separating codes and traffic monitoring
- Deriving generic bounds for time-series constraints based on regular expressions characteristics
- On the adoption of abductive reasoning for time series interpretation
- An adaptive subdivision method for root finding of univariate polynomials
- Quantifying matrix product state
- Efficient determinization of visibly and height-deterministic pushdown automata
- Multiple context-free tree grammars: lexicalization and characterization
- On the decidability of subtyping with bounded existential types and implementation constraints
- Complementing unary nondeterministic automata
- Patterns in words and languages
- Finite automata and pattern avoidance in words
- A language measure for performance evaluation of discrete-event supervisory control systems
- The structure of reflexive regular splicing languages via Schützenberger constants
- On membrane hierarchy in P systems
- On properties of bond-free DNA languages
- Visibly linear dynamic logic
- Limit cycle analysis in a class of hybrid systems
- A non-ambiguous decomposition of regular languages and factorizing codes
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Path resolution for nested recursive modules
- Isomorphism between two BL-general fuzzy automata
- Implementation relations and test generation for systems with distributed interfaces
- Partition refinement of component interaction automata
- A note on automatic semigroups.
- Finite transducers and nondeterministic state complexity of regular languages
- Some studies in hemirings by the falling fuzzy \(k\)-ideals
- Theory of reaction automata: a survey
- ptype: probabilistic type inference
- A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem
- Spiking neural P systems with target indications
- Design and implementation of bounded-length sequence variables
- Semigroups arising from asynchronous automata.
- Computational complexity of synchronization under regular commutative constraints
- Dynamic preference logic meets iterated belief change: representation results and postulates characterization
- Extending greedy feature selection algorithms to multiple solutions
- Online premeans and their computation complexity
- The descriptional power of queue automata of constant length
- On decidability of theories of regular languages
- General decidability results for asynchronous shared-memory programs: higher-order and beyond
- Communicating reaction systems with direct communication
- Comparison of path-complete Lyapunov functions via template-dependent lifts
- Gardens of Eden in the game of life
- Active matter as a path planning interpreter
- Formalization of the computational theory of a Turing complete functional language model
- State complexity of binary coded regular languages
- Approximate NFA universality motivated by information theory
- Interval type-2 fuzzy automata and interval type-2 fuzzy grammar
- Spiking neural P systems with a flat maximally parallel use of rules
- On typical hesitant fuzzy automata
- Second-order finite automata
- Operational complexity and pumping lemmas
- Stochastic analysis of minimal automata growth for generalized strings
- A closeness- and priority-based logical study of social network creation
- On the computation of counterexamples in compositional nonblocking verification
- Zombie number of the Cartesian product of graphs
- Equidecomposable magmas
- Introducing synchrony in fuzzy automata
- Some complete -powers of a one-counter language, for any Borel class of finite rank
- Multi-matching nested relations
- Team bisimilarity, and its associated modal logic, for BPP nets
- Constrained synchronization and commutativity
- Removing nondeterminism in constant height pushdown automata
- Concrete digital computation: what does it take for a physical system to compute?
- On expressive power of regular realizability problems
- Unique decipherability in formal languages
- Moments of the count of a regular expression in a heterogeneous random sequence
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4506483)