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
distinguish between histogram and historigram

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec

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

The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

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

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

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

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f