Finite State Machines: Part II

Standard

In the last post i tried to explain what a finite state machine is (see here). In this post, we’ll talk about regular languages and the equivalence between deterministic finite state machines, often called deterministic finite automata (DFA), and nondeterministic finite state machines, often called nondeterministic finite automata (NDFA).

Equivalences

One might think that NDFAs can solve problems that DFAs cannot, but NDFAs are just as powerful as DFAs. However, a DFA will require many more states and transitions than a NDFA would take to solve the same problem.

To convert a DFA into an NDFA, just define a NDFA that has all the same states, accept states, transitions, and alphabet symbols as the DFA. Essentially, the NDFA “ignores” its nondeterminism because it does not use null transitions and has exactly one transition per symbol in each state.

If an NDFA uses n states, a DFA would require up to 2n states in order to solve the same problem. To translate an NDFA into a DFA, use power set construction. For example, if an NDFA has 3 states, the corresponding DFA would have the following state set: {0,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}. Each element in the state set represents a state in the DFA. We can determine the transition functions between these states for each element of the set.

Regular Languages

By definition, a language is regular if and only if there is a DFA that recognizes it. Since DFAs are equivalent to NDFAs, it follows that a language is regular if and only if there is an NDFA that recognizes it. Therefore, DFAs and NDFAs recognize all regular languages. A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings.

There are different types of languages, shown in the figure below. However, we will focus on regular languages as an introduction to languages.

alan

Finite automata generate or model regular languages. This means that regular languages can be described by a simple state machine diagram. A finite state machine M, describes a given language L. 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. We say that the machine M recognizes the language L if M accepts all strings w that are in L.

For example, the machine in the image below 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.

aut

Leave a Reply

Your email address will not be published. Required fields are marked *