Question: Are there non-regular languages? 3Īny regular language can also be represented by some regular expression. 2Īdding some more jargon, a language is a regular language if it can be recognized by some finite automaton. Any NFA can be converted to a DFA that recognizes the same language. Notice that it transitions to the accept state when it encounters the sequence 101, but the 0 in the middle is optional since the same transition also has as a symbol, meaning it is automatically taken.Īn important conclusion is that NFA’s and DFA’s are equivalent.

Here is an NFA that accepts all strings containing 101 or 11 as a substring. A transition with input is followed regardless of the actual input. If any one computation terminates on an accept state, the NFA accepts the string. Think of an NFA as creating copies of itself and the computation going on independently on each of them if there are multiple possible transitions. An NFA (non-deterministic) can have arbitrarily many transitions for a single input from each state. In a DFA (d stands for deterministic), there can only be one transition per input per state. The examples above show deterministic FA’s. Can you figure out what language the one on the right recognizes? 1 Another method is to draw a table with a row per state, column per symbol, and each cell containing the next state.Įxercise: The FA on the left recognizes all strings ending with a 1. The most intuitive way is to draw a directed graph similar to the following examples, called a state diagram. There are different ways to represent an FA. If an FA is in one of its accept states when it reaches the end of the string, it is said to accept or recognize that string. It starts at a designated start state, reads individual characters from the input string, and moves from state to state as specified by the transitions. A finite automaton (FA) simply reads an input string, accepts it if the string is part of the language the FA is programmed to recognize, and rejects otherwise.Īn FA (finite automaton) has a set of states, and transitions between those states depending on the symbol being read. Finally, a set of strings form a language. A symbol can be any character ( 0, 1, a, b, $, …). We first have to cover some basic terminology. That question leads us to automata theory, and the simplest model of computation: the finite automaton. To base those questions on solid foundations though, a more fundamental question should be answered first: What is computation? The first question concerns computability theory, and the second question computational complexity theory. There are two main questions to be asked regarding computation:

Finite state automata stack what is