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

Reducibility among problems, A common approach in solving problems is to tr... A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

Suffix substitution closure, Our primary concern is to obtain a clear chara... Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

Prism algorithm, what exactly is this and how is it implemented and how to ... what exactly is this and how is it implemented and how to prove its correctness, completeness...

Nfas with e-transitions, We now add an additional degree of non-determinism... We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

Myhill-nerode theorem, The Myhill-Nerode Theorem provided us with an algori... The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

Strictly k-local automata, Strictly 2-local automata are based on lookup ta... Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

Boolean operations - class of recognizable languages, Theorem The class of ... Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

A composable-reset DFA (CR-DFA) is a five-tuple, Question 2 (10 pt): In thi... Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

Deterministic finite automata, conversion from nfa to dfa 0 | 1 ____... conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}

Pumping lemma, For every regular language there is a constant n depending o... For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u