Theory of Computation Simplified: Simulate Real-world Computing Machines and Problems with Strong Principles of Computation (English Edition)

By Dr. Varsha H. Patil, Dr. Vaishali S. Pawar, Dr. Swati A. Bhavsar and Dr. Aboli H. Patil

The book is geared toward those who thirst for computation theory knowledge. To cater to the demands of a wide range of people, the principles in this book are explained in a way that is easy to understand, digest and apply in the upcoming career.

The 'Theory of Computation' is the foundational and mathematical topic in computer science, computer applications, computer Engineering, and software engineering. This book provides a clear introduction to the fundamental principles, followed by an in-depth mathematical study and a wealth of solved problems. Before reading this book, learners must understand basic sets, functions, trees, graphs and strings. The book as a whole acquaints the reader with automata theory fundamentals. The book provides simplified theoretical coverage of the essential principles, solve instances, and solve multiple-choice problems with solutions. The theory and computation of automata presented in this book will greatly assist students and professors alike.

• Language: English
• Publisher: BPB Online LLP
• Release date: Aug 23, 2022
• ISBN: 9789355510716

Book preview

CHAPTER 1

Finite Automata

This chapter introduces formal languages and its finite representation. Basics of computing machines are also illustrated here, and it discusses the design of state transition automata. In this chapter, we will learn the construction of finite automaton and deterministic finite automata to accept or reject a particular set of input or strings. A finite automaton with the output for designing Moore and Mealy machine is also illustrated.

Structure

In this chapter, we will discuss the following topics:

Introduction to Formal language

Finite representation of language

A Step-by-Step Method for Constructing Automata

Finite State Machine (FSM)

Language accepted by Finite Automata

Deterministic Finite Automata

Finite Automata with output

Minimization of Automata

Objectives

The objective behind learning finite automata is to learn formal language and its relation with finite automata. In this chapter, we will understand how to Design a finite automaton for a given problem, handle all end conditions and reject states in automaton, design finite automata with the output such as Moore and Mealy machine approximation algorithms, apprehend randomized algorithms, and the use of parallel algorithms, and perform inter-conversion of Moore and Mealy machines.

1.1 Introduction to Formal language

A language is a subset of all possible strings formed by a given set of symbols. In general, a natural language is the one that has evolved over time for the purpose of human communication. Examples include English, German, Hindi, and so on. Such languages continue to evolve without regard for formal grammatical rules. Natural languages rarely conform to simple or obvious grammatical rules. In contrast to natural languages, formal languages are defined by pre-established rules and hence rigorously conform to the rules, viz mathematical languages such as algebra and prepositional logic. It is because of this adherence to rules that the construction of efficient computerized translators for programming languages is possible, whereas it is the lack of adherence to established rules that makes it difficult to construct a translator for a natural language.

1.2 Introduction to Language Translation Logic

A language translator is a computer program that performs translation of a source program written in some programming language to a functionally equivalent program in another computer language. The language translator is an example of system software. It is the responsibility of language translator that it should not alter or lose the functional or logical structures and semantics of the original code. It mainly consists of translation between high level languages, for example, High level languages (HLL) such as C, C++, Java and low level languages (LLL) such as, machine language, assembly language, and byte code.

The computer can understand and execute programs in machine language only. So, language translators are necessary component of the system software. Let us consider the following language translators:

Assembler: It is a language translator that converts an assembly language program into machine language. If the assembly language code contains any syntax errors, those errors are reported at the end of the translation process. This translation process is also called assembling the program, as shown as follows:

Compiler: It is a language translator that translates a high level program into machine language. During the process of translation, if some errors are encountered, then the compiler displays them as error messages, as shown as follows:

Interpreter: Like a compiler, an interpreter translates high level language code into an executable code. The way it differs from a compiler is that a compiler compiles the whole source code in one go and then executes it. Whereas an interpreter translates (or interprets) each line and executes it. If the source code contains any error, it reports the error on the same line. An interpreter will interpret and execute the next line only if the present line of source code is error free. This way, the language translation and code execution goes hand in hand in an interpreter.

1.3 Essentials of Translation

A translator is very essential for a program which is written in a given programming language and is to be converted into a functionally equivalent program. It should work in an efficient way without losing functional or logical structure of the original code. As the computer does not understand the high-level language, there is a necessity of a translator to translate it into machine level language. Semantic plays an important role for language translation that is associated with the meaning of language.

In formal languages, strings are made up of symbols from its alphabets. Each symbol should be unique, distinct with respect to all other symbols in the alphabet. A collection of symbols forms a string/sentence. A grammar is a set of rules that specify how symbols come together to form a valid string in a language. Lexical analyzer generates a string of tokens where it processes string and verifies whether a valid string is to be generated by the grammar. Working of lexical analyzer is discussed in Section 1.7.

1.4 Alphabets and languages

Language consists of alphabet, Lets study the definition of an alphabet.

1.4.1 An Alphabet (Σ)

An alphabet is a set of symbols that is finite and non-empty. Strings are formed using set alphabet. It is denoted by Σ. The symbols may be numbers or letters.

Example 1.1:

= {0, 1}

= {a, b, c, …… z}

= {0, 1, 2, …… 9}

Power of an alphabet:

Σ represents an alphabet. A set of strings of length k from that alphabet is nothing but the power of alphabet.

Example 1.2:

Σ = {0, 1}

Σ¹ = {0, 1}

Σ²= {00, 11, 01, 10}

Σ³ = {000, 001, 010, 011, 100, 101, 110, 111}

Σ* is a set of all strings of finite length, including the empty string which are constructed by taking symbols from alphabet Σ.

Generally, lowercase beginning alphabets are used as symbols and lowercase end alphabets like, u, v, and w, are used as strings.

1.4.2 Languages (L)

Language: A subset of Σ* is called language overΣ. It is a subset of all strings which are selected from Σ*. If Σ is the alphabet and L ÍS *, then L is a language over the alphabet Σ.

An empty set φ and {ε} are languages.

The important point to note here is that φ and {ε} are different. φ is an empty set { } while {ε} has one member ε.

Language L may be a finite or infinite set.

Example 1.3:

Consider the alphabet Σ= {a} then:

Σ* = {ε, a, aa, aaa, aaaa, …. }

Let Σ= {0, 1} then:

Σ* = {ε, 0, 1, 01, 10, 00, 11, …. }

The important feature of language is that all alphabet are finite. The language designed from finite alphabet may be finite or infinite depending on the constraints imposed on the strings belonging to the language.

1.5 Finite Representation of Language

Definition:

An alphabet is a finite, non-empty set of symbols. We use Σ to denote this alphabet.

Note: Symbols may be more than one English letter long, for example, while is a single symbol in Pascal.

Finite sequence of symbols from Σ is called string.

Number of symbols in a string denoted as | S | is the length of the string.

String of length zero is an empty string that is denoted as ε.

Σ * denotes the set of all sequences of strings that are composed of zero or more symbols of Σ.

Σ+ denotes the set of all sequences of strings composed of one or more symbols of Σ, that is, Σ*= Σ*–{ε}.

A language is a subset of Σ *.

More Definitions:

The concatenation of two strings is formed by joining the sequence of symbols in the first string with the sequence of symbols in the second string.

If a string S can be formed by concatenating two strings A and B, S=AB, then A is called a prefix of S and B is called a suffix of S.

The reverse of a string S, SR, is obtained by reversing the sequence of symbols in the string.

Example 1.4: If S = abcd, then SR = dcba.

Any string that belongs to a language is said to be a word or a sentence of that language.

1.5.1 Operations of Languages

Languages are sets. Therefore, any operation that can be performed on sets can be performed on languages.

If L, L1 and L2 are languages, then:

L1 – L2 is a language.

L1 ∩ L2 is a language.

L1 ∪ L2 is a language.

~ L = Σ*~ L, the complement of L, is a language.

In addition:

L1.L2, the concatenation of L1 and L2, is a language.

(The strings of L1, L2 are strings that have a word of L1 as a prefix and a word of L2 as a suffix.)

Ln, the concatenation of L with itself n times, is a language.

L* = φ∪ L ∪ L ∪ LL ∪ LLL ∪ LLLL ……, the star closure of L, is a language.

L

+ = L ∪ L ∪ LL ∪ LLL ∪ LLLL ……, the positive closure of L, is a language.

Derivations:

Productions are rules that can be used to define the strings belonging to a language.

Suppose language L is defined by a grammar G = (V, T, S, P). You can find a string belonging to this language as follows:

Start with a string w consisting of only the start symbol S.

Find a substring x of w that matches the left-hand side of some production p in P.

Replace the substring x of w with the right-hand side of production p.

Repeat Step 2 and Step 3 until the string consists entirely of the symbols of T (that is, it doesn’t contain any variables).

The final string belongs to the language L.

Each application of Step 3 is called a derivation step.

Suppose w is a string that can be written as uxv, where:

u and v are elements of (V ∪ T)*

x is an element of (V ∪ T)+

There is a production x→ y

Then we can write:

uxv ⇒uyv

and we say that uxv directly derives uyv.

Notation:

S ⇒T: S derives T (or T is derived from S) in exactly one step.

S⇒T: S derives T in zero or more steps.

S ⇒T: S derives T in one or more steps.

1.6 Finite Automata (FA)

Automata are abstract mathematical prototypes of machines which perform computations on an input by transiting through a sequence of states or configurations.

An automation is defined as a system where energy, materials, and information are transformed, transmitted, and used for performing some functions without human interference. It is a mechanistic model of computation. Here the concept of state of machine comes into focus. For example, elevators, ovens, automatic machine tools, automatic packing machines, etc., to which we are familiar from interaction with different controllers. Algorithms are nothing but the mechanical procedures, capable of being executed automatically by a machine. We can design various abstract mechanical models or machines performing the specific task. These machines can have different capabilities to carry out the basic operations such as reading, storing, controlling, processing, and writing the data. The abstract machines can be described according to their increasing capabilities, as follows:

Basic machine

Finite state machine (Finite Automation)

Turing machine

1.6.1 Basic Machine

Basic machine is the most primitive machine with a set of inputs I and a set of output O. This machine just maps the input set I to the output set O, that is, for a specific input I, it produces a specific output O. This mapping function is called Machine Function (MAF), as shown as follows:

I 0 (MAF)

Example 1.5: Consider input binary number {0,1} given as input to AND gate with output, as shown in Table 1.1:

Table 1.1: AND gate for example 1.5

The basic machine has very limited capability. It can only respond to a set of input data and produce an output set. It is also called a combinational machine. It can respond to the input, but it cannot remember or identify the intermediate machine state as it does not possess the memory. Different logical gates such as AND, OR, NOT, NOR, NAND, EXOR all are basic machines.

Note that when the AND gate receives input in the form of (0 AND 0), it will give the output 0. When the AND gate receives the input in the form of (0 AND 0 AND 0), it will not deliver any output as it has the input capacity of two bits only and it does not have any memory to store intermediate results.

Example 1.6: Candy Vending Machine

Consider a typical vending machine that serves a person’s choice of candy after it has received a total of 30 rupees in the form of five-, ten-, and twenty-five-rupee coins.

In this case, the automaton’s input alphabet consists of three different sizes of coins, a state of the machine is the total amount of money that has been received since the last candy was dispensed, the initial state is that not having received any coins since the last candy was dispensed, and an accept state is that of having received at least 30 rupees. Assuming that the machine is not designed to make change and will therefore merely consume any overpayment, its transition diagram would look like the one shown in Figure 1.1. An input is accepted if it leads to the accept (30 rupees) state. In this state, the machine will serve a candy bar when the operator pushes the button, as shown in Figure 1.1:

Figure 1.1: Transition diagram for Candy vending machine

Hence the basic machine needs to be modified by remembering its intermediate states and produce output for a specific input. Such a model is called a finite state machine (FSM) or finite automaton.

1.6.2 Constructing Simple Automata

Let us see the construction of a simple finite automata.

Example 1.7: An automaton whose alphabet is binary alphabet {0, 1}. It should accept any input string that begins with 1 and reject all other input that are beginning with 0. The string beginning with 1 is 1 itself. The set of all inputs accepted by this automaton is { 1, 11, 10,100,101,110,1111….}. From this infinite set, if any number is given as input, then the automaton should halt in the final state. The set of inputs rejected by this automaton is { 0, 01, 01,001,010,011,0000….}.

The automaton for the previously mentioned example is as shown in Figure 1.2:

Figure 1.2: An automaton for string that begin with 1

An automaton begins in start s0. As it should accept strings that start with 1, the first input symbol must be 1. If the input symbol is 1, the automaton remembers the condition that the first symbol was 1 by changing its state from s0 to s1. Therefore, the arrow going from s0 to s1 is labeled with 1. State s1 indicates that it is a final state, as shown in Figure 1.2. It shows that input 1 is accepted by the automaton. After that, any input that arrive that is 0,1, should be accepted by the automaton. The count of the number of 0s or 1s after the first symbol 1 doesn’t matter because our necessity condition is that the string should begin with 1. After this, there is no need of remembering the symbol to the automaton. Therefore, no state change happens for the input symbols 1 or 0 and we have the loop from s1 to s1. The loop can be traversed by automaton any number of times consuming 1s or 0s .

1.6.3 Handle End Conditions

Let us consider the example of automata that has a constraint at the end of input and not at the beginning.

Example 1.8: Let us consider the automaton that recognizes even number. We know that every even binary number ends in alphabet 1. Figure 1.3 shows the automaton that accepts only numbers that end with a symbol 1:

Figure 1.3: An automaton for string that ends with 1

The automaton doesn’t know the length of input; it can’t identify the last symbol. The automaton uses a greedy strategy where every time symbol 1 appears, it considers it as a last symbol in the input and goes to the final state s1. If additional symbol appears, then automaton modifies its behavior accordingly.

Suppose in the start state so, if input symbol is 0, then it does not remember the state and remains in the same state so. On the other hand, if the input symbol is 1, then automaton remembers the state and changes from state s0 to state s1. After reaching to the final s1, there are possibilities of two inputs as 0 and 1. If the input symbol is 0, then there is no need of remembering the fact of the present problem. Hence automaton comes back to the state s0 from s1. If the input symbol is 1, then it remains in the final state s1, and the input is still ending with 1. Hence, the loop from s1 to s1 is labeled by symbol 1.

The execution of automaton can be traced by various inputs as sequence of state transition ending in the halting state. For example, given 0011, the trace is so➔so➔s1➔s1(accepted). For 011001010 s0➔s1➔s1➔s0➔s0➔s1➔so➔s1➔so(rejected).

1.6.4 Handling Reject States

The next example introduces the concept of reject state. Reject state is generally used to reject bad inputs. It is also known as the dead state as it is never reachable for the set of acceptable inputs. This state does not have any other transitions to other states.

Example 1.9: Let us consider the automaton that only accepts the string which starts with symbol a, as shown in Figure 1.4:

Figure 1.4: Automation for Example 1.9

The automaton shown in Figure 1.4 illustrates that so is the starting state and s1 is the final state. When the input starts with symbol a, automaton changes the state from state s0 to state s1. If the input starts with symbol b, automaton branches to reject state R. The purpose of the reject state is to reject bad inputs that start with symbol b. At reject state R, if any number of symbols a or symbol b arrives, then it remains in the same rejected state. Reject states are often considered as optional states. If they are omitted, we must ensure that the state from which the reject state would have been reached is not a final state.

1.6.5 A Step-by-Step Method for Constructing Automata

In the previous sections, we discussed how to construct simple automata, handle end conditions, and reject state. Now, we will construct automata step by step.

Example 1.10: Construct an automaton for accepting a string containing at most three 1s; the output is as shown in Figure 1.5:

Figure 1.5: (a) Partial automaton for strings with three 1s

(b) More complete automaton with symbol 0s

(c) Final automaton for sting with at most three 1s

The requirement is to design an automaton for all inputs with symbol ‘1’ such that it contains at most three 1s and any number of 0s. The number of 1s can be 0,1,2,3, but not more than three. Let us construct the automaton step by step.

The state so accepts input 1, s1 accepts input 11, and s2 accepts input 111. As so, marked as a final state, is starting state too, it accepts a special input called null. Nothing else is accepted by the automaton. Now we have constructed the automaton to only accept the acceptable input. Further, we need to think about the input of symbol 0. There is no constraint for the number of inputs. This is introduced in Figure 1.5(b). If input symbol 0 occurs, then no need to remember the symbol b and the state transition doesn’t take place. Hence, there is self-loop at states s0, s1, and s2.

After this, we need to consider those inputs which are rejected by the automaton. Such an input is 1 as our automaton should accept only three 1s. If fourth 1 appears, it should be rejected. Figure 1.5(c) shows the modified transition that accepts all possible inputs with at most three 1s.

1.6.6 States as Memory

Automata doesn’t have a memory element. Automaton remembers anything by changing to the new state. A new state is required for the remembrance. In example 1.7, automaton for the string to begin with 1 and to remember that the input symbol is 1, automaton has to change its state from so to s1.

1.7 Finite State Machine (FSM)

This is the most general model with the internal or intermediate states of the machine. Consider the game of snake and ladder in which there are two players. Pieces are setup on a playing board. Dice are thrown and a random number is generated.

Depending on the drawn number, the pieces are rearranged on the board where there are ladders and snakes on board. If a player stops at snake’s mouth, the position is shifted down at the snake’s tail square. If he/she stops at a ladder, he climbs the ladder.

In this game, all possible combinations of positions of the pieces on board are nothing but states. The game changes from one state to another state which is totally decided by the dice, that is, input of a random generated number. For each input number, there is only one resulting state.

After certain number of moves, one of the two players wins. This is nothing but the final state of the machine. There is a possibility of winning for any one of the players, so there may be more than one possible output states. The initial or starting board position is called the start state or initial state of the machine, which is unique.

1.8 Language Accepted by Finite Automata

Let us consider one of the tasks on a compiler, that detects whether or not the given string within a source program represents an acceptable variable name. In a typical programming language, these names begin with a letter followed by an arbitrary finite combination of letters and digits. Also, any lexical structure in the programming language ends with one of set of symbols that recognize termination. Such symbols are the end of string markers. In case of variable names, these markers could be spaces, semicolons, and carriage return, as shown in Figure 1.6:

Figure 1.6: A transition graph for syntax of variable name

During compilation, the stream of characters making up the source’s program is read from left to right and grouped into lexical tokens that are a sequence of characters having a collective meaning. This process is called lexical analysis.

The lexical analysis is the first phase of a compiler. Hence, the main task of the lexical analyzer is pattern recognition. A recognizer for a language is a program that makes as input a string x and answers yes if x is a accepted sentence (token) of the language and no otherwise, which can be the best way modeled using finite automata, as shown in Figure 1.7:

Figure 1.7: Lexical Analyzer

Hence, the main task of lexical analyzer is to recognize tokens. Common examples of are keywords and identifiers. The tokens of the programming language are almost without any exception expressible using regular expressions. For example, the variable shown in Figure 1.6 can be represented as equation 1, as follows:

(letter) (letter + digit)*…………..(1)

Here, letter stands for [A – Z, a – z] and digit stand for [0 – 9]. Fortran identifiers, with length limit six and letters restricted to upper case can be expressed in equation 2, as follows:

letter (ε+ letter + digit)* ………….(2)

Here, letter [a – Z, $].

Note that blank and $ are allowed symbols in Fortran identifiers. A number of lexical analyzer generators such as Lex (or flex) of Unix, take as input a sequence of regular expressions describing the tokens and produce a single finite automaton recognizing any token.

Usually, they convert the regular expression to DFA. The lexical analyzer produced by a generator is a fixed program that interprets coded tables, together with the particular table that represents the FA recognizing the tokens. This lexical analyzer may then be used as a module in a compiler.

1.9 Definition of Regular Language

Finite automata recognize numerous symbol patterns. The language defined (also called accepted) by finite automaton is a set of strings accepted by it. Finite automata accepts those and only those strings that conform to certain compositional rules.

We can also define finite automata as a machine dividing the class of input strings into two groups; those which are acceptable and those that are not.

The language accepted by finite automata is called a regular language.

Regular language is defined recursively using the basic three set operations, as follows:

It is a regular language.

For each a ∈Σ, {a} is a regular language.

If L1, L2, …. Ln are regular language, then L1∪ L2∪ …. ∪ Ln is regular language; n ≥ 2. (Union)

If L1, L2, …. Ln are regular languages, then L1 . L2 . L3 …. . Ln is regular language; n ≥ 2. (Concatenation)

If L is a regular language, then so is L*. (Kleene’s Closure)

Nothing is a regular language unless it follows from (i) through (v).

Regular language is defined as using the three basic set of operations – Union, Concatenation, and Kleene star.

1.9.1 Kleene’s Theorem

Kleene proved the theorem in 1956 which says that if a language can be defined by either one of these – regular expression or finite automation or transition graph – then it can also be defined by the other two. In other words, all three of these methods of defining languages are equivalent, as explained as follows:

Any language that can be defined by regular expression or finite automaton or transition graph can be defined by all three methods.

This theorem is the most important and fundamental result in the theory of finite automata. As a process of proving this theorem, we have to introduce the algorithms that have the practical value of enabling us actually to construct the corresponding machines and expressions.

Alternatively, we have to prove the following steps:

Part 1: Every language that can be defined by a finite automaton can also be defined by a transition graph.

Part 2: Every language that can be defined by a transition graph can also be defined by a regular expression.

Part 3: Every language that can be defined by a regular expression can also be defined by a finite automaton.

1.9.2 Regular Set

A string s or word w is said to be accepted by a finite automaton M, if δ(s0, w) = P for some P ∈ F. Here, s0 is the start state, F is set of final states, and δ is a transition function. The language accepted by M, called L(M), is the set { w |δ(q0, w) in F}. A language is a regular set (or just regular) if it is the set accepted by some finite automaton.

Example 1.11:

The following are some of the examples of regular set S:

L(1*) = {ε, 1, 11, 111, 1111, ….}

L((00)*) = {ε, 00, 0000, 000000, ….}

L((0 + 11)*) = { ε, 0, 011, 110, 011011, …}

L(0 + 1 + 00 + 11) = {0, 1, 00, 11}

L((0 + 1)1) = {01, 11}

Regular languages are defined using regular expressions.

1.10 Definition of Finite Automata

A finite automaton consists of a finite set of states and a set of transitions from one state to another state on input symbols selected from an alphabet S. The initial state is generally denoted by s0. For each input symbol, there is one transition for each state. There are one or more final or accepting states.

A finite automaton is formally defined by a 5-tuple (S, Σ, δ, s0, F), where:

S→ Finite set of states.

Σ→ Finite set of input symbols.

δ→ Transition function mapping S × Σ to S.

s0→ Initial state and s0∈S.

F → Set of final state/states. It is assumed that there may be more than one final state.

F ∈S.

The FA model can be represented graphically, as shown in Figure 1.8(a):

Figure 1.8(a): Block diagram of Finite Automaton

Figure 1.8(b) shows finite automata with the output:

Figure 1.8(b): Finite Automaton with Output

The finite automaton has an input tape divided into units, each containing one symbol of the input string which is built from symbols of alphabet Σ. The start of tape is indicated by # and the end is indicated by $. The tape may be finite or infinite. In case of infinite tape, the tape end marker is absent. The input string to be processed is stored in the left to right direction.

The reading head examines one unit at a time and can move one unit in only one direction generally, left to right. The current state q and input symbol read by reading head are given as input to the finite control unit. The machine may remain in the same state s or transit to a new state and the reading head moves one unit ahead to read the next input symbol. This transition is denoted as follows:

δ (si, s)→sj

1.10.1 Representation

Finite Automata can be represented using a graph or a function notation using adjacency matrix.

Transition Graph

A transition diagram or transition graph is a finite directed labeled graph in which vertices represent a state and the directed edges indicate the transition of a state, and the edges are labeled with input/output, as shown in Figure 1.9:

Figure 1.9: Transition Graph Representation for string that ends with ‘1’

Consider the figure shown in Figure 1.9; the initial state s0 is indicated by the arrow pointing to it, labelled as start. The final state a1 is indicated by the double circle. This is the transition diagram for an FA which accepts the strings that ends with 1.

State Tables

The finite state machine consists of a pair of functions, namely,

I × S→ O (MAF), (Machine Function) and

I × S→S (STF), (State Function)

The MAF maps the Cartesian product of the input set I and the set of states S to the set of output 0, whereas STF maps the Cartesian product of the input set I and the state set S to the state set S. The behavior of such a machine can be completely determined provided its initial state and the input are known.

A set of finial states is also specified. The MAF and STF for full adder are given in the following example. These tables are called state tables.

Example 1.12: Consider an example of one-bit full adder. The MAF and STF for the same are given as follows:

MAF : I × S→ O

Table 1.2: MAF for example 1.12

In Table 1.2, I shows a set of input, O shows a set of output as 1 and 0, and S as a set of carry and no carry.

STF : (I × S → S)

Table 1.3 shows STF for full adder:

Table 1.3: STF for example 1.12

Adjacency or Transition Matrix

Adjacency or transition matrix has rows/columns labeled by the states sjÎS. Along the intersection of the j-th row and the k-th column in the array, we record the input symbol ∈I which causes the transition from a present state sjto a new state sk; this is followed by the punctuation ‘/’ and the output symbol ∈ O.

In case it is required to indicate the transition from a state sj to a state sk for more than one symbol ∈ I, we use the symbol for ‘logical or’ (V) and record this in addition; if there is no transition, place the entry as ___.

Full adder: Table 1.4 shows the transition table for full adder:

Table 1.4: Transition Table for Full adder

Divisibility by 3 tester.

Table 1.5 shows the transition table for divisibility by 3 tester:

Table 1.5: Transition Table for Divisibility by 3 tester

Finite control of FA over string

FA is popularly used as a language recognizer or acceptor. Language accepted by FA, say M, is denoted as (CM) and is a set of all strings accepted by M over alphabetΣ.

Extended δ function:

The transition function δ describes the transition of FA from one state to another state on the input of one symbol. To describe formally the behavior of an FA on a string, we must extend the transition function δ to apply to a state and a string rather than a state and a symbol. This is called the extended δ function denoted as and defined as a function from S× Σ* to S.

: S × Σ* S

That is, (s, w) is the state of FA that the FA will be after reading string w, starting with the state s. The formal definition of is given as follows:

(a, ∈) = a

This statement says that by the input of no symbol, the machine remains in the same state. Without any input symbol, the FA cannot change its state.

For all strings w and input symbols ‘a’,

(s, wa) = δ ( (s, w), a)

This statement tells us how to find the state after reading a non-empty input string ‘wa’. First we have to find a particular state x after reading string w from states, and then compute the δ (x, a) transition.

i.e. i) x = (s, w)

ii) Find δ (x, a)

A string ‘w’ is said to be accepted by a FA M = (S, Σ, δ, s0, F) if δ (s0, w) = x for some x ∈F. The language accepted by M is denoted as L(M). It is the set of all strings by input of which the machine reaches to one of the final states in set F. A language is a regular language if it is the set accepted by some finite automaton.

Example 1.13: Consider the FA described by the transition table, as shown in Table 1.6; this FA accepts all strings of 0s and 1s in which both the number of 0s and the number of 1s are even:

Table 1.6: Transition table for example 1.13

Assume that the input string to FA is 0 1 0 1 0 0 1 1. Then:

δ (s0, 0) = s2

δ (s2, 1) = s3

Thus:

δ (s0, 01) = δ (δ (s0, 0), 1) = s3

δ (s0, 010) = δ (δ (s0, 01),0) = δ(s3, 0)

    = s1

Thus, the whole sequence can be checked by:

The machine stops at state s0∈ F. So the string 0 1 0 1 0 0 1 1 with even number of 0s and 1s is accepted by the machine.

Structural Representations

There are two important notations that are not automaton-like, but play a vital role in the study of automata and their applications.

Grammars:

Grammars are useful models while designing software that processes data with a recursive structure.

A parser is the component of a compiler that deals with the recursively nested features of the typical programming languages, such as expressions – arithmetic, conditional, and so on. For instance, a grammatical rule like E → E ∗ E states that an expression can be formed by taking any two expressions and connecting them by a multiplication sign; this rule is typical of how expressions of real programming languages are formed.

Regular Expressions

Regular Expressions define the structure of data, especially text strings. The patterns of strings described by Regular Expressions are exactly the same, as what can be described by finite automata.

The style of these expressions differs significantly from that of grammars, and we shall content ourselves with a simple example here. The UNIX-style regular expression "[A-Z] [a-z] * [ ] [A-Z] [A-Z]", represents capitalized words followed by a space and two capital letters. This expression represents patterns in text that could be a city and state.

When interpreting such expressions, we only need to know that [A-Z] represents a range of characters from capital "A to capital Z (that is, any capital letter), and [ ] is used to represent the blank character alone. Also, the symbol * represents any number of" the preceding expression. Parentheses are used to group components of the expression; they do not represent characters of the text described.

Automata and Complexity

Fundamental to the computing science is the notation of a computational process, algorithm. It is by executing such processes that computers are able to solve problems; conversely, a problem that does not have an algorithmic solution cannot be solved by a computer.

Thus, any limitation on the capabilities of computational processes is also a limitation on the capabilities of computation machines. In this subject, we address the power of computational processes and hence to a critical study of computability.

Automata are essential for the study of the limits of computation.