Automata Theory - Finite State Automata and Regular Languages

Automata are abstract models of automatic machines which tend to have a very limited number of states they can be in. We use Automata without even knowing it, the most common example I can think of is the use of compilers with programming languages. In this post I'm going to be looking at Deterministic and Non-Deterministic Finite State Automata, and Regular Languages.

Firstly, I believe it would be best to give an introduction to the concept of Formal Languages which are processed by these abstract models of computation which represent real life computers in our modern age.

All the Formal Languages are defined within the Chomsky Hierarchy, which defines which languages can be computed by which machines. It takes the following format.

The hierarchy gives the types of languages classes, and what machines they can be computed by. For example, Finite Automata can only recognise Regular Languages and not Context-Free Languages. So what is the formal definition of a Formal Language?

Regular Languages and Regular Grammar: 

A formal language is a set of strings over a given alphabet with some form of rules applied to this strings. I'll introduce the terms of strings and alphabets shortly. These rules may be regular grammar which forms the basis of regular languages, which are recongised by finite automata machines. In mathematical terms, the formal language can be defined as follows:

$$L = \Sigma \subset \Sigma^*$$

A language is a set of all the possible words or strings which can be generated from that finite alphabet. Since I will be mostly looking Finite Automata, then a I mention briefly what a Regular Language is.

A Regular Language is a language which is constrained by the rules of regular grammar; all finite languages are regular, and all languages which can be accepted by a finite automation are regular, since finite automata only has a finite amount of memory, it isn't able to recognise a set of strings which has a arbitrary number of 0's or 1's.

A classic example of a regular language which can't be accepted by finite automata is:

$$\{0^n1^n | n \ge 0\}$$

Regular Languages are defined by regular expressions, regular expressions are said to be a sequence of characters which forms some kind of search pattern, for example a character can have literal meaning and a special meaning (forming a metacharacter). The pattern is a method of giving a set of strings some form of meaning and purpose. A good example from Wikipedia is, a literal character a can be used to denote the a set only containing the letter a, which would mean this: $$\Sigma = \{a\}$$

Let's give a formal definition for the rules of a regular grammar which is used to define a regular language.

A grammar tends to form a four tuple of:

$$G = (N, T, R, s)$$

The N represents a set of non-terminal symbols and the T represents a set of terminal symbols, these symbols are used to produce the production rules, which in turn are used to produce the strings accepted by the machines. Remember these are abstract representations of how computers work and how compilers can be designed. R is the production rules, and s is the start symbol.

The sets of both Non-Terminal and Terminal symbols is disjoint, and their intersection is the empty set. The Terminal Symbols can't be converted into a different character, and thus the reason why they're called Terminal Symbols. The Non-Terminal Symbols can be converted into different characters. For example, let's say that the N = {x} and T = {a}, this is a very small set but the production rules will easier to understand with less symbols.

The production rules would be defined in the following format:

$$x \rightarrow xa$$
$$x \rightarrow a$$

The production rules could be chosen a k number of times, which would produce:

$$xa^ka$$  

Deterministic and Non-Deterministic Finite State Automata:

A Deterministic Finite State Machine (DFSM) is said to be deterministic if for a given state and input, the next state can be determined. This is what most of our computers are, and hence the reason why the P=NP problem hasn't been solved, NP algorithms require a non-deterministic Turing Machine. A FSM is typically defined as a tuple:

 $$(X, Q, q, F, \sigma)$$

X = Alphabet (Inputs)
Q = Finite Set of States
q = Initial State (member of Q)
F = Final Accepting State (Proper Subset of Q)


DFSMs have a finite number of states, and their transition function is defined below:

$$\sigma: Q \centerdot X \rightarrow Q$$

The transition function shows that for a given state and a given input, which state the finite machine will move to. All FSMs have a starting state and a accepting final state. The only difference between a DFSM and a NDFSM (Non-Deterministic Finite State Machine) is the transition function used. The transition function for a NDFSM is defined below:

$$\sigma: Q \centerdot X \rightarrow P(Q)$$

With a Non-Deterministic Finite State Machine, then two states can be reached with the same input, this doesn't necessarily mean that two accepting states could be reached. With the case of one accepting state, then the machine will need process both of transition functions, and then accept the transition function which leads to a final accepting state. There is also no difference in terms of computing power between a DFSM and a NDFSM, since both machines can accept all regular languages.

The circle with a inner circle is the final accepting state, and is used with all FSM diagrams. Note that the labels on the edges represent the characters with the string being read by the machine.