Computer Theory: Finite Automato - Essay Example

FINITE AUTOMATO An FA is a 5-tuple  , where Q: Finite set of states  : Finite input alphabet  : Transition function Start state F: Set of final states Finite state automaton is also known as a finite state machine (FSM). In its basic meaning, the finite number of states and the transitions between them in nature of their actions make up the model on which the state machine is defined. Automaton is a singular form of automata. Kohavi (1986) in computer science, 'Automata' refers to the study of Abstract computing devices. It is use to get help to solve problems which be done by a computing machine. Concepts which came up and have been used in different fields, like compiler design, software design etc. So a finite automaton is that which has a finite number of distinguishable internal configurations. Kohavi (1986) A finite automaton is a collection of three things: 1. A finite set of states, out of the whom one is concieved as the initial state, called start state, and some (maybe none) of which are designated as final states. 2. An alphabet of possible input letters, from which are formed strings that are to be read one letter at a time. 3. A finite set of transitions that narrate in relation to each state and for each letter of the input alphabet that reflects upon the nature of the to go to next..."1 A state stores information about the past, i.e. it reproduces the changes in the input from the start of the system to the present instance. Furthermore, a transition points towards a state change and can be understood by a condition that would need to be fulfilled to enable the transition. An action is the detailed information of an activity that is to be performed at a given moment. There are several action types: Entry action - which is performed when entering the state Exit action - which is performed when exiting the state Input action - which is performed depending on present state and input conditions Transition action - which is performed when performing a certain transition When talking about finite automata three things are important: Alphabet - generally represented as Sigma, is the set of symbols that are accepted by the FSM. As an example, the alphabets {0,1} would state to be accepting simple binary numbers. String - a sequence of symbols. Language - the set of strings that are "accepted" by the FSM. In order to define the state of finite automata we specify one or more accept states. If the system is in one of the accept states while the FSm is being done, the string is made to be accepted in the process. Pin (1989) gave example that if we Construct a Deterministic Finite Automata accepting the following Set: {w belongs to {a,b}* : w has an even number of a's and odd number of b's } Then, there will be four states, for no particular reason let us name them: a even, b even a even, b odd a odd, b even a odd, b odd Make "a even, b even" be the start state, and make "a even, b odd" be the only accepting state. Now for the transitions: on input "a", go from "a even, b even" to "a odd, b even" "a even, b odd" to "a odd, b odd" "a odd, b even" to "a even, b even" "a odd, b odd" to "a even, b odd" on input b, go from "a even, b even" to "a even, b odd" "a even, b odd" to "a even, b even" "a odd, b even" to "a odd, b odd" "a odd, b odd" to "a odd, b even" If there were any other letters in the input alphabet besides a and b, -- for example if you had said w belonged to {a,b,c}* instead of {a,b}* -- then you would just remain in the current state when such a letter was input; only an a or a b in the input string can trigger a state change2. CONTEXT FREE GRAMMAR Nijholt(1980) state in his book that a context-free grammar G is a 4-tuple:  where 1.  is a finite set of non-terminal characters or variables. These characters represent different and variable types of phrase or clause in the sentence. 2.  is a finite set of terminals, disjoint with , which make up the actual content of the sentence. 3.  is the start variable, used to represent the whole sentence (or program). It must be an element of . 4.  is a relation from  to  such that 3. Lew (1985) In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form V → w Where V is a single nonterminal symbol and w is a string of terminals and/or non-terminals (possibly empty). The term "context-free" expresses the fact that no-terminals can be rewritten without regard to the context in which they occur. A formal language is context-free if some context-free grammar generates it. The central role is played by context-free grammar in the design description of programming languages and compilers. They are also used for analyzing the syntax of natural languages.4. Jurafsky and Martin (2008) describe the most common way of modeling constituency CFG = Context-Free Grammar = Phrase Structure Grammar = BNF = Backus-Naur Form Context-free grammar is explained below: G = hT,N, S,Ri • T is set of terminals (lexicon) • N is set of non-terminals For NLP, we usually distinguish out a set P _ N of preterminals which always rewrite as terminals. • S is start symbol (one of the nonterminals) • R is rules/productions of the form X ! , where X is a nonterminal and is a sequence of terminals and nonterminals (may be empty). • A grammar G generates a language L. An example context-free grammar G = hT,N, S,Ri T = {that, this, a, the, man, book, flight, meal, include, read, does} N = {S, NP, NOM, VP, Det, Noun, Verb, Aux} S = S R = { S ! NP VP Det ! that | this | a | the S ! Aux NP VP Noun ! book | flight | meal | man S ! VP Verb ! book | include | read NP ! Det NOM Aux ! does NOM ! Noun NOM ! Noun NOM VP ! Verb VP ! Verb NP A CFG defines a formal language = the set of all sentences (strings of words) that can be derived by the grammar5. TURING MACHINE Turing machines, first described by Alan Turing in (Turing 1937), are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed. Brookshear (1985) in his book describe Turing, writing before the invention of the modern digital computer, was interested in the question of what it means to be computable. Through intuition, a task is stated to be computable if a particular sequence of instructions which when followed will eventually lead to the completion of the task. These cumulative pieces of instructions are called an effective procedure, or algorithm, for the task. This intuition must be made precise by defining the capabilities of the device that is to carry out the instructions. Devices with different capabilities may be able to complete different instruction sets, and therefore may result in different classes of computable tasks (see the entry on computability and complexity)6. Turing proposed a class of devices that came to be known as Turing machines. These devices lead to a formal notion of computation that we will call Turing-computability. Hromkovič (2004) said that a Turing machine is a purely logical construct and consists on a tape divided on cells (the medium) and a processing head. The medium is supposed to be both the input and output; the input is entered before starting the machine and the result is the reading on the same tape. The head’s pointer can do two things: it can move either left or right, or it can change its internal state to one of a given set of states. There’s where set theory comes handy for computer science. Processing ends when reaching a value from a subset of the States set called End States. The examples used in class for: a) a complement function (01011 becomes 10100, etc); b) a “marbles” addition function (1+11 becomes 111); c) a “match pattern” decision function. The notation used will be the following: ‘0X 1YR’ means “when the head is on state 0 and reads a symbol “X”, change to state 1, write a symbol “Y” and move to the right”.7 Example 1: Complement function Symbols = {0, 1} and {B} States = {0, 1} End States = {1} 00 01R; When reading a "0" write a "1", move ahead 01 00R; When reading a "1" write a "0", move ahead 0B 1BS; When reading a blank (end of the string) change state to an End State. That’s all, the head travels through the tape turning each “0″ it finds to “1″ and each “1″ to “0″, Once it reads a blank the state changes to “finalize”. Another example of a Turing machine In this picture the ovals again represent control states of the machine and the arrows represent transitions between control states. However, since the Turing Machine may move R, L, or Write to the tape, the action is represented explicitly in the diagram. On each arrow is the tape element followed by the '/' and then the action. For example, the transition from da to srb represents the tuple "da a # srb"; that is if you are in control state "da" and you are reading an "a" on the tape, then overwrite a with # (i.e. erase it) and make srb the current control state8. Read More