FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
& THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: RESOLVING NON-PROGRESSION IN STATE MACHINES
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor,
SERVICES LIMITED Nariman Point, Mumbai,
Maharashtra 400021, India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[0001] The present subject matter relates, in general, to state machines and, in particular, for resolving non-progression in finite state machines.
BACKGROUND
[0002] In recent years, significant growth has been observed in the implementation of automated systems in several industries. Such automated systems may vary from large design units implemented in manufacturing plants to simple everyday machines, such as a soda dispensing machine. Automated systems include microprocessors, microcontrollers, semiconductors, and several other solid state components designed to work together in order to implement the automated system.
[0003] Typically, the automated systems are configured using hardware description languages, which, in turn are modeled using state machines. The state machine includes a number of states, where each state indicates a possible state of the system. Based on inputs, either external or internal, the state machine undergoes transitions from a current state to any of the possible states of the state machine. In a hardware description language comprising several state machines, the state machines typically communicate amongst each other.
SUMMARY
[0004] This summary is provided to introduce concepts related to resolving non-progression in state machines. These concepts are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[0005] In one embodiment, a method and system for non-progression in state machines are described. The method comprises identifying a plurality of state machines, where each of the plurality of state machines includes a state variable. The method further comprises ascertaining a plurality of communicating state machines from the plurality of state machines based on communicating machines determining technique. Further, the method comprises determining at least one set of communicating state machines from among the plurality of communicating state

machines, where the at least one set of communicating state machines comprises at least two state machines communicating with each other. The method further comprises analyzing each state machine in the at least one set of communicating state machines based on a plurality of input signals received by the state machine.
BRIEF DESCRIPTION OF THE DRAWINGS [0006] The detailed description is described with reference to the accompanying figure(s). In the figure(s), the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the figure(s) to reference like features and components. Some embodiments of systems and/or methods in accordance with embodiments of the present subject matter are now described, by way of example only, and with reference to the accompanying figure(s), in which: [0007] Figure 1 illustrates a network environment implementing a computing device, according to an embodiment of the present subject matter. [0008] Figure 2 illustrates a method for non-progression in state machines, according to an embodiment of the present subject matter.
[0009] Figure 2(a) illustrates a method for determining a group of valid state machines, according to an embodiment of the present subject matter. [0010] Figure 2(b) illustrates a method for ascertaining a plurality of communicating state machines, according to an embodiment of the present subject matter. [0011] Figure 2(c) illustrates a method for analyzing a set of communicating state machines, according to an embodiment of the present subject matter.
DETAILED DESCRIPTION
[0012] Method(s) and a system(s) to resolve non-progression in state machines are described herein. The systems and methods described herein can be implemented on computing devices, such as a server, a desktop, a notebook or a portable computer.
[0013] Typically, microprocessors, microcontrollers, semiconductors, and several other components of an automated system are designed using hardware description languages, based on state machines. A state machine is a representation of states of the automated system and may have a finite number of states. Such state machines are referred to as finite state machines. Generally, a hardware description language includes several state machines in communication

with each other resulting in a transition from the current state to any of the possible finite states of the state machine. For a first state machine in communication with a second state machine, in certain cases, the first state machine may receive a signal from an external entity, such as a timer, an interrupt routine, a signal from any other state machine while still being in communication with the second state machine. In such a case, the first state machine may service the signal from the external entity leading to a state of non-progression in the second state machine.
[0014] In another case, where both the first state machine and the second state machine are dependent on an input from one another, the signal from the external entity may lead to a deadlock and hence result in non-progression of the state machines.
[0015] Conventionally, for detecting deadlocks in communicating state machines, various techniques are used. For example, few conventional techniques for detecting conflicting behaviour between state machines employ a polynomial time algorithm. The polynomial time algorithm, upon analyzing a hardware description language relevant to the state machines, produces a large number of approximate results which are analysed. However, the aforesaid technique is applicable only in cases of communicating state machines which are communicating using only a single message type. Moreover, the use of polynomial time algorithm yields a large number of approximate results thereby increasing the time and effort to analyze the results. Thus, use of polynomial time algorithm for resolving non-progression may prove to be an overall tedious and time consuming task.
[0016] In accordance with the present subject matter, a method and a system for resolving non-progression in state machines is described herein. In one implementation, a hardware description language, such as verilog, VHDL, C program is analysed to identify a plurality of communicating state machines. Further, the plurality of communicating state machines are analysed and a non-progression report is obtained based on the analysis.
[0017] In one implementation, a computing device analyses a hardware description language to identify a plurality of state machines. In one example, the state machines may be modeled using If/Else statements, where each of the "If" statements indicates one state of the state machine. In another example, where the state machines may be modeled using switch statements, where each case within the switch statement indicates one state of the state machine.

[0018] In one implementation, each of the state machines includes one state variable. The state variable indicates a current state of the state machine. In one implementation, the state variable may be a local or a global variable. Further, the value of the local or global variable is set equal to a constant in said implementation.
[0019] In one implementation, the state machines are identified based on a modification in the state variable of the state machines. The modification, in one case, may be understood as a change in the current state of the state variable to any one of the possible states of the state machine.
[0020] Thereafter, a group of valid state machines is determined from among the state machines. In one implementation, the computing device determines the group of valid state machines based on valid machines determining technique. In another implementation, the computing device may determine the group of valid state machines based on a user input.
[0021] As stated previously, a plurality of communicating state machines is identified from among the group of valid state machines. In one implementation, the communicating state machines are identified based on communicating machines determining technique. The state machines may communicate using communication agents, such as a variable and a flag. In one example, the variable may be a state variable indicative of a current state of the state machine. For instance, the state machines are said to be communicating when a state variable of a first state machine is being processed by a second state machine. In said implementation, the computing device ascertains the plurality of communicating state machines based on the communication agent which is being used for communication. As will be understood from the foregoing description, the identification of the plurality of communicating state machines which a subset of the entire available state machines, helps in reducing the number of state machines which are to be analysed, thereby reducing the time and resources involved in resolving non-progression in state machines.
[0022] In one implementation, the computing device analyzes a set of communicating state machines from among the plurality of communicating state machines. In one example, the set of communicating state machines includes a pair of communicating state machines. In said example, the set of communicating state machines include a first state machine and a second state machine in communication with each other. In another example, the set of communicating

state machines may include at least two communicating state machines. In one implementation, a plurality of input signals received by each of the communicating state machines from among the set of communicating state machines are identified. The input signals may include a plurality of communication signal and a plurality of external signals.
[0023] Thereafter, the computing device ascertains a plurality of states being modified based on the plurality of input signals. In one implementation, the plurality of states may include the states receiving at least two input signals. In another implementation, the plurality of states may include the states in non-progression due to non-reception of an expected input signal.
[0024] Further, in one implementation, the computing device generates a non-progression report based on the analysis. In one example, the non-progression report may include parameters affecting the plurality of states such as a type of signal received, a source state from which the communication signal is received, an expected state of the communicating state machine, the position of the state in the state machine, and the like. In one implementation, the non-progression report is provided to a user, such as a domain expert. The computing device may update the hardware description language based on an input from the domain expert for resolving non-progression.
[0025] The system and the method in accordance with the present subject matter, thus provide an efficient computing device for resolving non-progression in state machines. Further, identification and analysis of communicating state machines based on input signals reduces the number of state machines which are to be analysed thereby reducing the complexity and time involved in resolving non-progression in state machines.
[0026] These and other advantages of the present subject matter would be described in greater detail in conjunction with the following figures. While aspects of described systems and methods for resolving non progression in state machines can be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary system(s).
[0027] Figure 1 illustrates a network environment 100 implementing a computing device 102 in accordance with an embodiment of the present subject matter. In one implementation, the network environment 100 can be a public network environment, including thousands of personal computers, laptops, various servers, such as blade servers, and other computing devices. In

another implementation, the network environment 100 can be a private network environment with a limited number of computing devices, such as personal computers, servers, laptops, and/or communication devices, such as mobile phones and smart phones
[0028] The computing device 102 is communicatively connected to a plurality of user devices 104-1, 104-2, ..., and 104-N, collectively referred to as user devices 104 and individually referred to as a user device 104, through a network 106.
[0029] The computing device 102 and the user devices 104 may be implemented in a variety of computing devices, including, servers, a desktop personal computer, a notebook or portable computer, a workstation, a mainframe computer, a laptop and/or communication device, such as mobile phones and smart phones. Further, in one implementation, the computing device 102 may be a distributed or a centralized network system in which different computing devices may host one or more of the hardware or software components of the computing device102.
[0030] The computing device 102 may be connected to the user devices 104 over the network 106 through one or more communication links. The communication links may be enabled through a desired form of communication, for example, via dial-up modem connections, cable links, digital subscriber lines (DSL), wireless, or satellite links, or any other suitable form of communication.
[0031] The network 106 may be a wireless network, a wired network, or a combination thereof. The network 106 can also be an individual network or a collection of many such individual networks, interconnected with each other and functioning as a single large network, e.g., the Internet or an intranet. The network 106 can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and such. The network 106 may either be a dedicated network or a shared network, which represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), etc., to communicate with each other. Further, the network 106 may include network devices, such as network switches, hubs, routers, for providing the one or more communication links. The network devices within the network 106 may interact with the computing device 102 and the user devices 104, through the communication links.

[0032] According to an embodiment of the present subject matter, the computing device 102 is configured to analyse a hardware description language based on state machines and provide a non-progression report to a user, for example, a domain expert for resolving progression in state machines.
[0033] For the purpose, the computing device 102 may include one or more processor(s) 108, I/O interface(s) 110, and a memory 112 coupled to the processor 108. The processor(s) 108 can be a single processing unit or a number of units, all of which could include multiple computing units. The processor 108 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor 108 is configured to fetch and execute computer-readable instructions and data stored in the memory 112.
[0034] The I/O interface(s) 110 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, a display unit, an external memory, and a printer. Further, the I/O interface(s) 110 may enable the computing device 102 to communicate with other devices, such as the user device 104, web servers and external databases. The I/O interface(s) 110 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the I/O interface(s) 110 include one or more ports for connecting a number of computing systems with one another or to a network.
[0035] The memory 112 may include any non-transitory computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In one implementation, the computing device 102 also includes module(s) 114 and data 116.
[0036] The module(s) 114, amongst other things, include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement data types. The module(s) 114 may also be implemented as, signal processor(s), state machine(s), logic

circuitries, and/or any other device or component that manipulate signals based on operational instructions.
[0037] Further, the module(s) 114 can be implemented in hardware, instructions executed by a processing unit, or by a combination thereof. The processing unit can comprise a computer, a processor, such as the processor 108, a state machine, a logic array or any other suitable devices capable of processing instructions. The processing unit can be a general-purpose processor which executes instructions to cause the general-purpose processor to perform the required tasks or, the processing unit can be dedicated to perform the required functions.
[0038] In another aspect of the present subject matter, the module(s) 114 may be machine-readable instructions (software) which, when executed by a processor/processing unit, perform any of the described functionalities. The machine-readable instructions may be stored on an electronic memory device, hard disk, optical disk or other machine-readable storage medium or non-transitory medium. In one implementation, the machine-readable instructions can be also be downloaded to the storage medium via a network connection.
[0039] In one implementation, the module(s) 114 further include an identification module 118, a validation module 120, an analysis module 122, and other module(s) 124. The other modules 124 may include programs or coded instructions that supplement applications and functions of the computing device 102.
[0040] The data 116 serves, amongst other things, as a repository for storing data processed, received, and generated by one or more of the module(s) 114. The data 116 includes identification data 126, validation data 128, analysis data 130, and other data 132. The other data 132 includes data generated as a result of the execution of one or more modules in the module(s) 114.
[0041] As described previously, the computing device 102 is configured to resolve non progression in state machines included in the hardware description language. In one implementation, the computing device 102 may receive the hardware description language from a user device, such as a user device 104-1. In another implementation, the hardware description language may be stored on an internal database (not shown in figure) of the computing device 102.

[0042] In one implementation, the identification module 118 is configured to identify a plurality of state machines included in the hardware description language. In one implementation, the state machine may be a finite state machine. Each of the plurality of state machines from among the plurality of state machines include a state variable, where the state variable indicates a current state of the state machine. In one implementation, the state machine may be modeled using one of a IF/ELSE condition and a SWITCH statement. In a case where the state machine is modeled using IF/ELSE condition, the state variable is included in each of the IF condition block. In another case, where the state machine is modeled using SWITCH condition, the state variable is included in each case condition block. In one example, the state variable may be one of a global variable and a local variable, where the value of the state variable is set constant as would be understood by a person skilled in the art.
[0043] The identification module 118 identifies the plurality of state machines based on a modification in the state variable. In one implementation, the state variable may modify into any one of the possible states of the finite machine. In another implementation, the state machine may modify into a default state of the state machine. In one example, the modification may be either one of a direct and indirect modification as would be understood. In yet another implementation, the identification module 118 determines the modification of the state variable in a function peripheral to the state machine and any other functions called from the state machine. The identification module 118 may store the plurality of state machines in the identification data 126.
[0044] In one implementation, the validation module 120 is configured to determine a group of valid state machines from among the plurality of state machines based on valid machines determining technique. The valid machines determining technique may include update strength and nested state machine rules. Initially, for each of the plurality of state machines, the validation module 120 ascertains whether the finite machine is nested or not. If the validation module 120 determines that the state machine is not nested, the validation module 120 ascertains an update strength of the state machine using the equation given below:
Update Strength (US) = (Total if condition block where state variable is modified) / (Total number of if condition blocks) * 100

In one example, for a state machine based on IF/ELSE condition, the update strength may be understood as a percentage obtained by dividing the total number of state variable modifications in the if condition blocks of the state machine by the total number of if condition blocks of the state machine. In another implementation, the validation module 120 ascertains the update strength for all the state machines based on SWITCH statement in a manner as described above.
[0045] Further, the update strength is compared with a threshold value. In one implementation, the threshold value may be determined by a user, such as a domain expert. In another implementation, the threshold value may be pre-determined by the validation module 120. In a case where the update strength is greater than the threshold value the validation module 120 marks the state machines as a valid state machine. If it is determined that the update strength is less than the threshold value, the state machine is marked as an invalid state machine. For example, for a threshold value of 50%, a state machine having 10 possible states and undergoing 6 transitions will be marked as a valid state machine. On the other hand, if the state machine undergoes less than 6 transitions, the validation tool will mark the state machines as an invalid state machine.
[0046] In one implementation, the validation module 120 is configured to determine whether the state machine is nested or not. If the validation module 120 determines that the state machine is not nested, the validation module 120 ascertains the state machine as valid or invalid based on the update strength and the threshold value as described previously. Further, the validation module 120 ascertains whether the state machine is a peripheral state machine. The peripheral state machine may be understood as a state machine including one or more state machines. For example, a first state machine, say, SM1 and a second state machine, say, SM2 are included in a third state machine, say, SM3, then SM3 is ascertained as a peripheral state machine. If the state machine is a peripheral state machine, the validation module 120 computes the update strength of the state machine and performs a comparison with the threshold value as explained above. Based on the comparison, the validation module 120 marks the state machine as either valid or invalid state machine. Further, if it is determined that the state machine is not a peripheral state machine, the validation module 120 ascertains whether the state machine has a state variable equal to that of the peripheral state machine to which the state machine is nested thereto. If the validation module 120 determines that the state machine has a different state variable, an update strength of the state machine is computed and a comparison based on the

update strength is performed in a manner as described previously and subsequently, the state machine is marked as one of a valid state machine and an invalid state machine. If it determined that the state machine and the peripheral state machine nested thereto has the same state variable, the validation module does not mark the state machine. The group of valid state machine, as determined by the validation module 120, is stored in the validation data 128.
[0047] In one implementation, the validation module 120 is configured to enlist the valid state machines and the invalid state machines in a validation list and provide the validation list to the domain expert through the user device 104-1. Further, the validation module 120 may update the validation list, i.e., mark a valid state machine as an invalid state machine and vice versa based on an input from the domain expert. The domain expert may provide the input to the validation module 120 through the user device 104-1. An example illustration of the validation list is provided below.

State Variable Indirect
state
variable State
Machine
Type Function Start Location State variable updation info

Updated States Total Update states Strength Status
sv1 Isv SWITCH foo1 test1.c::11 3 3 100% VALID
sv2 SWITCH foo2 test1.c::22 1 3 33.33% INVALID
[0048] In the validation table illustrated above, sv1 and sv2 are the state variables corresponding to a first finite machine and a second state machine respectively. Further, in one implementation, the validation table may also include the update strength for each of the state machines enlisted in the validation table. The validation table also includes a type of the state machine and the function in which the state machine is enlisted.
[0049] In one implementation, the identification module 118 is configured to ascertain a plurality of communicating state machines from among the group of valid state machines based on communicating machines determining technique. In one implementation, the valid state machine may communicate with each other using communication agents, such as a flag and a variable. In one example, the variable may be a state variable indicative of a current state of the state machine. Further, the valid state machines may communicate either directly or indirectly

based on the communication agent being used for the communication. In one example, the identification module 118 initially ascertains whether the state variable of the valid state machine is being processed by any other state machine. For example, the processing may involve reading the state variable of the state machine, either directly or indirectly, by the other state machine. In one implementation, if the identification module 118 ascertains that the state variable is not being processed by the other state machine, the identification module 118 does not perform any action. Further, if the identification module 118 ascertains that the state variable is being processed by the other state machine, the identification module 118 then determines whether the another state machine is a valid state machine or not. If the other state machine is not a valid state machine, then the identification module does not perform any further action. Further, If the other state machine is a valid state machine, then the identification module 118 further determines whether the other valid state machine and the valid state machine have the same state variable or not. If the identification module 118 determines that the other valid state machine and the state machine have the same state variable, the identification module 118 does not further processes the aforementioned state machines. Further, if the identification module 118 determines that the other valid state machine and the state machine have different state variables, the identification module 118 determines both the valid state machine and the other valid state machine as communicating state machines. The identification module 118 stores the plurality of communicating state machines in the identification data 126. As will be understood, the identification module 118 will ascertain the plurality of communicating state machines from among the group of valid state machine in a manner as described above.
[0050] In one implementation, the analysis module 122 is configured to determine a set of communicating state machine from among the plurality of communicating state machines. In one implementation, the set of communicating state machines includes a pair of communicating state machines in communication with each other. In another implementation, the set of communicating state machines may include at least two communicating state machines. Thereafter, the analysis module 122 is configured to analyze the set of communicating state machines and generate a non-progression report based on the analyses.
[0051] In one implementation, the analysis module 122 identifies a plurality of input signals, where the input signals may include communication signals and external signals. In one implementation, the analysis module 122 identifies a plurality of communication signals received

by the communicating state machine included in the set of communicating state machine. The communication signals, in one example, may be understood as signals used for communication among the state machines. As described previously, the state machines communicate amongst each other using one or more of the communication agents. Subsequently, the analysis module 122 ascertains the signals pertaining to the communication agents as the communication signals. Further, the analysis module 122 ascertains a plurality of external signals received by the communicating state machine. The external signals may be understood as a signal from external entities such as timers, interrupts/port, and a signal from any other communication state machine. In one implementation, the analysis module 122 is configured to identify the external signals from the interrupt routines. In said example, if a global variable is set in an interrupt routine, the analysis module 122 validates the global variable of the interrupt routine as an external signal. An illustration of an interrupt routine including a global variable, where the global variable is set is provided below.
ISR_Routine()
{
if (signal constant for some period)
{ set a shared variable SH as true
}
} [0052] Here, SH is a global variable, interchangeably referred to as shared variable, being set in the ISR routine. Further, in application, the global variable is considered as an external signal and the global variable may be accessed by a communicating state machine.
[0053] Further, the analysis module 122 identifies the external signals from the timers based on one or more preconfigured rules. In one implementation, based on the pre-configured rules, the analysis module 122 may ascertain a list of timer variables. In another implementation, the pre-configured rules may consider timers as a global variable, included in an assignment, increment/decrement operation, and comparison operation, where the value of the timer is constant throughout the operation. In yet another implementation, the timers with at most one increment/decrement in the value are considered. The analysis module 122 may store the identified external signals from the interrupts and the timers in an external signal list in the

analysis data 130. In one example, the analysis module 122 may update the external signal list based on an input received from the domain expert through user device 104-1. In one implementation, the pre-configured rules may be based on timer patterns. An illustration of the timer patterns is provided below.
static void SmTimerTask(int var) {
if ( timer[VAL] != 0 ) // timer present in controlling statement
{ timer[VAL]-- ; // timer is decremented
} }
[0054] In the illustration above, the timer is decremented once. As described previously,
the timers whose value is decremented by one is considered as an external signal.
[0055] Thereafter, the analysis module 122 ascertains a plurality of states of the communicating state machine, where the plurality of states are being modified based on the input signals, where the input signal may be one of the plurality of communication signals and the external signals. In one implementation, the analysis module 122 ascertains the plurality of states being modified based on both the communication signals and the external signals. In one example, a communicating state machine SM1, in a current state sv1 may receive two signals at a given instant of time. In one case, the two signals may be a communication signal and an external signal. In such a case, the SM1 may not transit to an expected state of the SM1. For instance, while servicing the external signal first the SM1 may transit to an unexpected state sv4, while the expected state of the SM1 may be sv2. In such a case, the analysis module 122 identifies the state and enlists the same in the non-progression report. In another implementation, the analysis module 122 may further include the states affected as a result of missed signals due to the unexpected transition of the states of the communicating state machine in the non-progression report.
[0056] In one implementation, the non-progression report may include the plurality of states identified by the analysis module 122. Further, the non-progression report may include other parameters for each of the states from among the plurality of states such as all events for where at least two signals are received by the state. The non-progression report may further include the type of signal, either one of the communication signal and the external signal, the

expected state, the unexpected state, and a source state from which the signal is being sent. An illustration of the non-progression report is provided below.

Review ID State machine receiving signal State machine sending signal

Signal information State machine information State machine information

Signal Name Type of signal Transition Controlling Statement State Variable Name Start location State Transition State Variable Name Start Location State Transition
Statement Location Start state Line no. End state Line no. Start state Line no. End state Line No.
1 extSig External if ( extSig == 1) can.c::20 sv2 app.c::1 8 3 20 4 30 sv1 usm.c::12

comm Communicating if ( comm == 1) can.c::23 sv2 app.c::1 8 3 20 5 31 sv1 usm.c::12 1 14 2 20
[0057] As illustrated above, the non-progression report includes the type of the input signal, the state variable, the current state and the expected state, the current state and the unexpected state, the position of the state variable, and the source state of the communication signal. The analysis module 122 may store the non-progression report in analysis data 130. In one implementation, the analysis module 122 may provide the non-progression report to the domain expert.
[0058] Figure 2 illustrates a method 200 for resolving non-progression in state machines, in accordance with an embodiment of the present subject matter. Figure 2(a) illustrates a method for determining a group of valid state machines, in accordance with an embodiment of the present subject matter. Figure 2(b) illustrates a method for ascertaining a plurality of communicating state machines, in accordance with an embodiment of the present subject matter. Figure 2(c) illustrates a method for analyzing a set of communicating state machines, in accordance with an embodiment of the present subject matter.
[0059] The order in which the methods 200, 204, 206, and 210 are described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the methods 200, 204, 206, and 210 or any alternative methods. Additionally, individual blocks may be deleted from the methods 200, 204, 206, and

210 without departing from the spirit and scope of the subject matter described herein. Furthermore, the method(s) 200, 204, 206, and 210 can be implemented in any suitable hardware, software, firmware, or combination thereof.
[0060] The method(s) 200, 204, 206, and 210 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The methods 200, 204, 206, and 210 may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
[0061] A person skilled in the art will readily recognize that steps of the methods 200, 204, 206, and 210 can be performed by programmed computers. Herein, some embodiments are also intended to cover program storage devices, for example, digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, where said instructions perform some or all of the steps of the described methods 200, 204, 206, and 210. The program storage devices may be, for example, digital memories, magnetic storage media, such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. The embodiments are also intended to cover both communication network and communication devices configured to perform said steps of the exemplary method(s).
[0062] At block 202, a plurality of state machines is identified. In one implementation, each of the plurality of state machine may be modeled using one or more of an IF/ELSE conditions and SWITCH statements. Further, each of the state machines include a state variable indicating a current state of the state machine. In one implementation, the identification module 118 identifies the state machine based on a modification in the state variable of the state machine. In one implementation, the state variable may modify into one of the several finite possible states of the state machine. In another implementation, the state variable may modify into a default state of the state machine.

[0063] With reference to method 200 as illustrated in Figure 2, at block 204, a group of valid state machines is determined from amongst the plurality of state machines. In one implementation, the group of valid state machines may be determined based on valid machines determining technique. In one implementation, the validation module 120 determines the group of valid state machines from among the plurality of state machines. The steps of determining the group of valid state machines has been described in greater detail with respect to Figure 2(a).
[0064] At block 206, a plurality of communicating state machines is ascertained from among the group of valid state machines. In one implementation, the identification module 118 ascertains the plurality of communicating state machines based on communicating machines determining technique. The steps of ascertaining the plurality of state machines have been described in greater detail with respect to Figure 2(b).
[0065] At block 208, at least one set of communicating state machines is identified from amongst the plurality of communicating state machines. In one example, the analysis module 122 identifies the at least one set of communicating state machines. In one implementation, the set of communicating state machines may include a pair of state machines in communication with each other. In another implementation, the set of communicating state machines may include at least two state machines.
[0066] At block 210, the at least one set of communicating state machines is analysed. In one example, each of the state machine included in the set of state machine is analysed. In one implementation, the analysis module 122 identifies the set of communicating state machines. The steps of analyzing the at least one set of communicating state machines have been described in greater detail with respect to Figure 2(c).
[0067] At block 212, a non-progression report is generated based on the analyses. In one implementation, the non-progression report may include a plurality of states being modified based on a plurality of input signals received by the state machine. The non-progression report may further include a type of the input signal, a source state of the input signal, an expected state of the state machine, an unexpected state of the state machine, and the like. In one example, the analysis module 122 generates the non-progression report based on the analyses. Further, in one implementation, the non-progression report may be provided to a user, for example, a domain

expert. Subsequently, non-progression of the state machines may be averted based on inputs received from the domain expert.
[0068] With reference to method 204 as illustrated in Figure 2(a), at block 214, it is determined whether the state machine is nested or not. If it is determined that the state machine is not nested, the method proceeds to block 216. At block 216, it is determined whether an updated strength of the state machine is greater than a threshold value or not. In one implementation, the validation module 120 determines the update strength of the state machine based on the number of state variable modifications of the state machine as described previously. If it is determined that the update strength is greater than the threshold value, the method proceeds to block 218 and the state machine is ascertained as a valid state machine. Further, if it is determined that the update strength is equal to or lower than the threshold value, the method proceeds to block 220 and the state machine is ascertained as an invalid state machine.
[0069] At block 222, it is determined whether the state machine is a peripheral state machine or not. If it is determined that the state machine is a peripheral state machine, the method proceeds to block 216 and the state machine is ascertained as either a valid state machine or an invalid state machine as described previously. If it is determined that the state machine is not a peripheral state machine, the method proceeds to block 224.
[0070] At block 224, it is ascertained whether the state machine has the same state variable as the peripheral state machine nested thereto. If it is determined that the state machine and the peripheral state machine have different state variable, the method proceeds to block 216 and the method proceeds as described previously. If it is determined that the state machine and the peripheral state machine nested thereto have the same state variable, the method proceeds to block 226. At block 226, the state machine under consideration is not marked as a valid/invalid state machine. In one implementation, the validation module 120 may not further evaluate the state machine.
[0071] With respect to method 206 as illustrated in Figure 2(b), at block 228, it is determined whether the state variable of the valid state machine is being processed by an other state machine or not. If it is determined that the state variable is not being processed by the other state machine, the method proceeds to block 230. At block 230, the valid state machine is not

processed any further. If it is determined that state variable is being processed by the other state machine, the method proceeds to block 232.
[0072] At block 232, it is determined whether the other state machine is a valid state machine or not. If it is determined that the other state machine is a valid state machine, the method proceeds to block 234. If it is determined that the other state machine is not a valid state machine, the method proceeds to block 230.
[0073] At block 234, it is determined whether the other valid state machine has the same state variable as the valid state machine. If it is determined that the other state machine has the same state variable as that of the valid state machine, the method proceeds further as described previously in block 230. If it is determined that the other state machine does not have the same state variable as that of the valid state machine, the method proceeds to block 236. At block 236, the valid state machine and the other valid state machine are ascertained as communicating state machine.
[0074] Although the aforementioned method has been described with reference to the use of state variables for communication amongst valid state machines, the method 206 will proceed in a similar manner, as described above, in an implementation where either one of a flag or any other variable is used for communication amongst valid state machines.
[0075] With reference to method 210 as illustrated in Figure 2(c), at block 238, a plurality of input signals received by each of the set of communicating state machines are identified, where the plurality of inputs signals include communication signals and external signals. In one implementation the communicating state machine may receive the external signals from external entities, such as interrupt routines, ports, timers, and a signal from another communicating state machine. The communication signals may be understood as signals received from a second communicating state machine included in the set of communicating state machines.
[0076] At block 240, a plurality of states being modified based on the plurality of input signals are ascertained. In one implementation, the plurality of states may include each state receiving at least two input signals. For example, a state (sv1) of a state machine (SM1) receiving two input signals, one each from the communicating state machine and the external entity, at a same instant of time will be included in the plurality of states being modified. In one

example, the modification may be understood as a transition of the state, and hence the state machine, from a current state to different state. In one implementation, the state machine may transit to a state different than an expected state based on the input signal received. As explained in the previous example, the state machine may prioritize the signal from the communicating state machine and may transit to a state, say, sv3 different than an expected state, say, sv2. In such a case, the external signal from the external entity may be missed. In a case where the state machine prioritizes the input signal from the external entity, the state machine may transit to a state, say, sv5 different from both sv2 and sv3. In such a case, the communication signal from the communicating state machine may be missed. In one implementation, the plurality of states may also include states which are in non-progressive state due to non-reception of the input signal. In one implementation, the analysis module 122 ascertains all such states for each of set of communicating state machines.

I/We claim:
1. A method for resolving non-progression in state machines, the method comprising:
identifying a plurality of state machines, wherein each of the plurality of state machines includes a state variable;
ascertaining a plurality of communicating state machines from the plurality of state machines based on communicating machines determining technique;
determining at least one set of communicating state machines from among the plurality of communicating state machines, wherein the at least one set of communicating state machines comprises at least two state machines communicating with each other; and
analysing each state machine in the at least one set of communicating state machines, based on a plurality of input signals received by the state machine.
2. The method as claimed in claim 1, wherein the identifying further comprises determining a modification in the state variable.
3. The method as claimed in claim 1, wherein the identifying comprises determining a group of valid state machine from among the plurality of state machines, based on valid machines determining technique.
4. The method as claimed in claim 3, wherein the valid state machines determining technique comprises:
ascertaining whether each of the plurality of state machines is nested;
determine whether the each of the plurality of state machines is a peripheral state machine, in response to the ascertaining; and
comparing, to determine whether the each of the plurality of state machines is valid, the state variable of the each of the plurality of state machines and a state variable of a peripheral state machine nested thereto, when the each of the plurality of state machines is not a peripheral state machine.
5. The method as claimed in claim 3, wherein the valid state machines determining
technique further comprises:
ascertaining an update strength for each of the plurality of state machines; and
comparing the update strength with a predetermined threshold value.

6. The method as claimed in claim 1, wherein the communicating machines determining
technique comprises:
determining whether the state variable of each of the state machines is processed by another state machine;
ascertaining whether the other state machine is a valid state machine; and
determining whether the state variable of the each of the plurality of state machines is same as a state variable of the other valid state machine.
7. The method as claimed in claim 1, wherein the method further comprises generating a non-progression report based on the analysing, for resolving non-progression.
8. The method as claimed in claim 1, wherein the state variable is one of a local variable and a global variable, the state variable being indicative of a current state of the state machine, and wherein the value of the state variable is set as a constant.
9. The method as claimed in claim 1, wherein the ascertaining is based on a communicating agent used by each the of the plurality of communicating state machines to communicate, wherein the communicating agent comprises at least one of a variable and a flag.
10. The method as claimed in claim 1, wherein the analyzing comprises:
identifying the plurality of input signals for each of the communicating state machines in the set of communicating state machines; and
ascertaining a plurality of states for each of the communicating state machines, wherein each of the plurality of states are modified based on one or more of the plurality of input signals.
11. The method as claimed in claim 11, where the plurality of input signals comprises at least one of a communication signal from a communicating state machine and an external signal.
12. The method as claimed in claim 12, wherein the external signal is received from one of a timer, an interrupt routine, and a port.
13. A computing device (102) for resolving non progression in state machines, the computing device (102) comprising:
a processor (108);

an identification module (118) coupled to the processor (108), the identification module (118) configured to identify a plurality of state machines;
a validation module (120) coupled to the processor (108), the validation module (120) configured to determine a group of valid state machine from among the plurality of state machines based on valid machines determining technique; and
an analysis module (122) coupled to the processor (108), the analysis module (122) configured to
determine at least one set of communicating state machines from among the plurality of communicating state machines, wherein the at least one set of communicating state machines comprises at least two state machines communicating with each other; and
analyse each state machine in the at least one set of communicating state machines, based on a plurality of input signals received by the state machine.
14. The computing device (102) as claimed in claim 13, wherein the identification module (118) is further configured to ascertain the plurality of communicating state machines from the group of valid state machines based on communicating machines determining technique.
15. The computing device (102) as claimed in claim 13, wherein the validation module (120) is further configured to:
ascertain whether each of the plurality of state machines is nested;
determine whether the each of the plurality of state machines is a peripheral state machine, in response to the ascertaining; and
compare, to determine whether the each of the plurality of state machines is valid, the state variable of the each of the plurality of state machines and a state variable of a peripheral state machine nested thereto, when the each of the plurality of state machines is not a peripheral state machine.

16. The computing device (102) as claimed in claim 15, wherein the validation module (120)
is further configured to:
ascertain an update strength for each of the plurality of state machines; and
compare the update strength with a predetermined threshold value.
17. The computing device (102) as claimed in claim 13, wherein the identification module
(118) is further configured to:
determine whether the state variable of each of the state machines is processed by another state machine;
ascertain whether the other state machine is a valid state machine; and
determine whether the state variable of the each of the plurality of state machines is same as a state variable of the other valid state machine.
18. The computing device as claimed in claimed in claim 13, wherein the analysis module
(122) is further configured to:
identify the plurality of input signals for each of the communicating state machines in the set of communicating state machines; and
ascertain a plurality of states for each of the communicating state machines, wherein each of the plurality of states are modified based on one or more of the plurality of input signals.
19. The computing device (102) as claimed in claim 13, wherein the identification module
(118) is further configured to:
generate a non-progression report based on the analyzes for resolving non-progression; and
provide the non-progression report to a user.
20. A computer-readable medium having embodied thereon a computer program for
executing a method comprising:

identifying a plurality of state machines, wherein each of the plurality of state machines includes a state variable;
ascertaining a plurality of communicating state machines from the plurality of state machines based on communicating machines determining technique;
determining at least one set of communicating state machines from among the plurality of communicating state machines, wherein the at least one set of communicating state machines comprises at least two state machines communicating with each other; and
analysing each state machine in the at least one set of communicating state machines, based on a plurality of input signals received by the state machine.