There are two main ways to write a concatenation. A language is a regular language if there is a finite automaton that recognizes it.įor example, this machine recognizes the language of strings that have an even number of zeroes since any string that has an even number of zeroes will go from the start state to an accepting state.Ī regular language can be represented by a string of symbols and operations.Ĭoncatenation is an operation that combines two symbols, sets, or languages. We say that the machine \(M\) recognizes the language \(L\) if \(M\) accepts all strings \(w\) that are in \(L\). \(M\) is said to accept a string \(w\) if the machine starts in a start state, undergoes some series of state transitions, and ends up in an accepting state. A finite state machine, \(M,\) describes a given language, \(L\). This means that regular languages can be described by a simple state machine diagram. it doesn't know how many times the switch has been flipped on or off).įinite automata generate or model regular languages. The machine above can know what state it is currently in, on or off, but it doesn't know what the history of flips was to get it to where it is (i.e. For example, a finite automaton can generate a regular language to describe if a light switch is on or off, but it cannot keep track of how many times the light was switched on or off. Regular languages and finite automata can model computational problems that require a very small amount of memory.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |