Machine

Machine

In our day to day life we often used the word machine such as washing machine, sewing machine etc. A computer is a programmable machine.  It allows the user to store all sorts of information and then ‘process’ that information, or data, or carry out actions with the information, such as calculating numbers or organizing words.

“Machine in TCS, it will be logical mechanism by which we can process the given input data and will produce the output data”.

But the machines discussed in this chapter will be the mechanism used for solving the problem. It is very difficult to define a term machine, because it cannot be defined as “a member” certain class. When we talk of machine two things is keep our mind.

1. Machine is some sort of object.
2. An idea

The idea of a machine is usually centered on some abstract model or process. The algorithm is mechanical processes which do not require an intuition and can be carried out automatically by a machine.  

Simple Machine

Machines which are composed of two or more parts acting one upon another are called complex machine. Machine which consist only of one part are called simple machines. The several parts composing a complex machine are themselves a simple machine.

It is logical mechanism to recognize the given set of input strings and generates the output strings, and then it will be a machine which has a very limited capacity and will be known as a Simple Machine. This machine will produce output for each input.

Simple machine recognizes input I and gives output O. It can be mathematical interpreted as a function

F: I→ O

I is a Input O is a Output              F is a function

1. Suppose we receive two input symbols at a time and we are required to generate AND of them i.e. machine representing AND gate will be

The input (i1, i2) produces output () as shown below

2. A machine to generate 1’s complement of a given binary number will be.

The simple machine has a limited capacity. It will only react on the input. To improve the capacity of the machine it is very necessary that we should consider the state of mind during the design of the machine. There are internal states of the machine.   

Finite State Machine

The finite state system represents a mathematical model of a system with certain input. The model finally gives certain output. The input when is given to the machine it is processed by various states, these states are called as intermediates states.

The very good example of finite state system is a control mechanism of elevator. This mechanism only remembers the current floor number pressed, it does not remember all the previously pressed numbers.   

This machine will consist of input output relation at every state and also the changes of the states that will occur on receiving the input at particular state.

Mapping functions: FSM has two forms of mapping functions. They are following.

• (1) MAF (Machine Function)
• (2) STF (State Function).

MAF (Machine Function)

It is a function to which input is an argument and output is the result. There is a one to one mapping from input to output. Such a function relating input to output is known as Machine Function or MAF. The input and output alphabet could be different.

STF (State Function)

State machines are another means of describing of dynamic model elements, and they are closely related to activities. Whereas activity describes flow between area of work, state machines describe flow between states. For example, a telephone is either hung up, dialing, engaged in a call or disconnected. These are states of telephone, and we can use a state machine to link the states together and determine the legal flows through the system. While an item is in a state, work may or may not be going on – when a phone is hung up, there is no activity in the phone, but when it is engaged in a call, there are a lot of activities in the phone. States are useful logical views of an entity.   

At any state the machine is in any of its states and on arrival of an input symbol it will change the state using state function and will also give the output using machine function.  

Both of them are function of two arguments, current state and current input but their results are different. The machine can be specified by

Basically, finite state machine are studied in automata theory, which is subfield of theoretical computer science. A finite state machine or finite state automata is an abstract machine used in the study of computation and languages that has only a finite, constant amount of memory. It can be conceptualized as a directed graph. There are finite numbers of states, and each state has transition into next state. There is an input string that determines which transition is to be followed. We can have FSM to generate output string also.

In this case it will be acting as a convertor for the input string

Theory of Computation Notes

आशा करता हूँ, कि यह आर्टिकल आपको पसंद आया होगा तो सोच क्या रहे हैं अभी इसी वक्त इसे अपने दोस्तों के साथ सोशल मीडिया पर Share करें।

Thanking You………………धन्यवाद………………..शुक्रिया………………..मेहरबानी…………………..

Read More: InfoKhajana.com covered the following topics in these notes.

• R Language
• Digital Marketing
• Theory Of Computation:: Introduction of Theory of Computation
• Theory Of Computation:: Basic Terminologies of Theory of Computation
• Theory Of Computation:: Languages
• Theory Of Computation:: Kleene Closure
• Theory Of Computation:: Machine

References –
cs.stanford.edu
Wikipedia