Automata, Theory of Computation

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of languages on abstract automata. These are "checking machines" in which the input is a string over some speci?c alphabet. We say such a machine accepts a string if the computation on that input results in a TRUE output. We say that it recognizes a language if it accepts all and only the strings in that language.

Generally, in exploring a class of languages, we will de?ne a class of automata that recognize all and only the languages in the class-a particular sort of automaton, the peculiarities of which exactly capture the characteristics of the class of languages. We say the class of automata characterizes the class of languages. We will actually go about this both ways. Sometimes we will de?ne the class of languages ?rst, as we have in the case of the Finite Languages, and then look for a class of automata that characterize it. Other times we will specify the automata ?rst (by, for instance, modifying a previously de?ned class) and will then look for the class of languages it characterizes. We will use the same general methods no matter which way we are working.

The de?nition of the class of automata will specify the resources the machine provides along with a general algorithm for employing those resources to recognize languages in the class. The details that specialize that algorithm for a particular language are left as parameters. The only restriction on the nature of these parameters is that there must be ?nitely many of them and they must range over ?nite objects.

Posted Date: 3/21/2013 5:35:23 AM | Location : United States







Related Discussions:- Automata, Assignment Help, Ask Question on Automata, Get Answer, Expert's Help, Automata Discussions

Write discussion on Automata
Your posts are moderated
Related Questions
Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh


De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

What are the benefits of using work breakdown structure, Project Management

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations


c program to convert dfa to re

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan