Automaton for finite languages, Theory of Computation

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







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
Related Questions
proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

build a TM that enumerate even set of even length string over a

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

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

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

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

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p