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
State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

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


Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

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