We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the class. In this way, we can regard a specification of those parameters as a definition of a language in the class. Given our assumption of finiteness for the parameters, the definition will be finite.

The specification itself will be a mathematical object-a tuple of values, one for each parameter. We can illustrate this process by applying it to the class of Finite Languages. The obvious algorithm for recognizing such a language is to use a lookup table containing all and only the strings in the language. We then simply read the entire input and check to see if it is in the table. A schematic representation of an automaton implementing this algorithm is shown in Figure 1. The input is shown across the top, written on a tape one symbol per cell of the tape. (The structure of the input is irrelevant here, but will matter when we work with automata that scan the input sequentially.) The ∈ element, here, outputs TRUE iff its first input is a member of the set presented to its second input, so it represents some sort of search mechanism.

Posted Date: 3/21/2013 5:36:48 AM | Location : United States

Ask an Expert

Related Discussions:- Automaton for finite languages, Assignment Help, Ask Question on Automaton for finite languages, Get Answer, Expert's Help, Automaton for finite languages Discussions

Write discussion on Automaton for finite languages
Your posts are moderated

Write your message here..

Related Questions

Arden''s theorem,

Possibility of recognizing the palindrome language, Computer has a single F... Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Equivalence of nfas and dfas, In general non-determinism, by introducing a ... In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Create a general algorithm from a checking algorithm, Claim Under the assum... Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

Local myhill graphs, Myhill graphs also generalize to the SLk case. The k-f... Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

Non - sl languages, Application of the general suffix substitution closure ... Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Gastric juice, what are composition and its function of gastric juice what are composition and its function of gastric juice

Third model of computation, Computer has a single LIFO stack containing ?xe... Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

Algorithm for the universal recognition problem, Sketch an algorithm for th... 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

Xx, Ask queyystion #Minimum 100 words accepted# Ask queyystion #Minimum 100 words accepted#