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
We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

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

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

I want a proof for any NP complete problem

Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(