STATE, STATE GRAPHS AND TRANSITION TESTING ? * i SYLLABUS [JNTU - H&A] Sate Graphs, Good and Bad State Graphs, State Testing, Testability Tips. Scanned with CamScannerFins Rte Graphs one Trarstion Testing ap Tue, State Graphs and Transition Testing (Ua Wy EAM IntrobuctION © Ql) What is finite State Machine? i Answer : o Finite state machine is a model of computation consisting of a set of sets, a sty ‘state, an input alphabet and transition function that maps input symbols and Current, states to next states. The machine Is in only one state at a time. Computing begins in the start state with an input string. It changes to new states depending on the transition function. Finite State Machines (FSM’s) can model a large number of problems such as, (2) Design automation. 2) Parsing (3) Protocol design etc. As it is limited to finite number of states, it is known as Finite State Machine. E223 STATE GRAPHS Q2) Define the term “State Graph"? Answer : ‘Stare Grarn The behaviour of the system is represented in graphical form which is known as “State Graph”. The state graph is used for functional testing of the system to, identify diferent bugs. The bugs include. (2) State Bugs. (2) Transition Bugs. Elements : The state graphs include many elements such as, a) States. (2) Inputs. (3) Transitions. (4) Outputs, SOFTWARE TESGING METHODOLOGIES — PROFESSIONAL PUBLICATIONS Scanned with CamScannerGraphs and Transition Testing [Unit - Vil] eristic> ara - tified ~ a state in a state graph is the node which represents the re ide! of the syst ystem. State graph has set of states and they © test Ste" penaviout ir numbers. qnaractere. © _ The states In the st(ate graph contains input value ‘tates. They can be denoted by numbers of characters: © : tee ena two states is known as transition. Whe! 0 the node, the state changes and the process of changing of 5 5 to represent the changes sitions 0. applied & jaown 25 transition. as output. ‘outputs * ‘after processing an input, the result is produced which is known the input and output of the state graph are separated by ~slash"(/)- .; The overall ir re taken and ney 2 processed fro! duced. Je: consider the example of aul fansitions and outputs. jy inthe first state, after inserting the card we enter pin nu! is that_ it verifl it asks for balance enquiry or mone’ d to enter the correct pin again. @ jables 2! process iS Pro! t consists of NPY process of state graph could be_ the input vari m one state to another and the result of the tS, tomatic teller machine (ATM) thal mber. rrect, it is processed ies the pin number and if it Is O! If it is incorrect, {) The second state to next step 1.€ y withdrawal. the state is repeates and if money withdrawal Is ipt is printed and receit is printed. quiry, the recei y'and'then gives out money he receit and ATM card. nted in the form of State dlagr: @) If we choose balance en chosen, it asks for mone’ #) The process ends by taking tl The whole process can be represe! am-as in Fig. 7-1- O--O—-O—-O c rt: Example of State Graph jons in the state graph can be explained” The states and inputs and transit B+ Start State + Enter pin Number 1. Verification of pin number > Pin number is wrong PROFESSIONAL PUBLICATIONS — Scanned with CamScanner"a re ri i pin number is ok Screen displays two options balance enquiry, money withdrawal if “balance enquiry” is chosen Print receit if “money withdrawal” is chosen enter amount amount is entered ore aunanew tebe bbe beuve received money receit is printed. Q3) = What is finite state machine and a state? } [May - 11, Set - 2, @4(b), M(8)], [April/May - 08, Set - 3, Q7(b), M(B Answer : | Finite State Machine Note : Refer Q.No. 1. (1) State Definition : A state is nothing but a condition which describes the behaviour of the system. There are several set of states in the state graph. With the input given, the state of the system would be changed. (2). Representation : In state graphs, states are represented using nodes. They are. identified either by numbers or characters. 4 Input Sop cre | Aort [RZ Representation of State | @) Example (The threads in java language has many states such as, new - > ready > running > — block > exit SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScanner——* Srate, State Graphs and Transition Testing [Unit > Vi] “is ann as, (i) A car which is running can be in any one of the following states such > First gear > Second gear > Third gear > Fourth gear > Fifth gear > Reverse gear > Neutral Q4) Explain about inputs and transitions in the State Graphs. Answer : The input variables changes the states and inputs are the cause for the’ transitions to occur. When a state is changed then it is said to be a transition. The general english meaning of transition is “the Process or a period of changing from one, state or condition to another”. Representation of Inputs and Transitions : The inputs which are the cause for the transitions to occur are marked on line. It means that inputs are the weights of the links. For every state there would be a (1) Inlink. (2) OutLink. 6 : If there are more than one input in a state which causes the changes to a same Subsequent state then they can be represented as single link and all the link weights Separated by comma, they need not be represented as several parallel lines. For example, a,b,¢ CLD The inputs a, b, ¢ cause transitions from state 1 to 2. So they can represented as @ single link separated by comma. eae Scanned with CamScannerSlate, State Graphs and Transition Testing [Uniy 76 HERZ Paratel Links . Consider the state graph in Fig. 7.4. The inputs that are considered:in the graph are A, B and C. “S” denotes the start state. The state graph in the Fig. 7.4 can be explained as, (2) The first state is the start state. If any input other than a keeps the graph in the, “S” state only. (2) If input “a” is given then the system transitions to next state “A”. (3) If the system is in A state and if input a is again received then it remains in same state. If b Is received, it changes to state “AB” and if input c is received, it goes to the start state "S”. . (4) After entering into state “AB”, if c is received then it enters into state “ABC” oF else it goes to start state (S)_If any input is received.in state "ABC" then it remains in the same state, All the above explanation is simplified and represented in the form of State Graph. Q5) Explain about outputs of State Graphs? Answer : Output + Each and every input is processed to give a output. Every node has a output fink: e ‘epresentation : Outputs are also represented as link weights. They are also denoted by letters or numbers. Outputs are separated from inputs by slash (/) such as, input/output. If there are several inputs for the some output then it is represented as, a, b, c,d... / output, where a, b, c, d are inputs. If there are different combinations of inputs and Outputs between two nodes, they are represented separately by parallel lines. SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS ONAL RUBLIGARONS Scanned with CamScanneree | Gate Graphs and Tran got annie consider the state diagram of Fig, 7.5, ion Testing [Unit - Vil] iu 1/00 0/01 1/11 0/10 EY State Diagram The above is the simple state graph which consists of two states S, and S2.. The inputs are O and 1. It can be explained as, bs (a) One receiving ‘1’ as input to state Si, it remains in the same state. @) On receiving ‘0’ as input to state Si, it is processed or transitioned to state S2. @) The same analysis for state S2. Now the above diagram is analyzed for inputs and outputs. (1) On processing S, on input = 1, the output = 00. (2) On receiving 0 as input at state S,, the output = 10. (3) On receiving 0 as input at state S, the output is 01. (4) If input is given as 1 at state S,, the output would be 11. For all state/transition diagrams, the output strings also plays a prominent role. Q6) Write about State Tables? Answer : State Table : The representation of state graph in the form of table is known as State Table. This is done because it would Be difficult task to go through all the nodes of the state graphs if it has more number of nodes and transitions. So if graph is converted to table, it would be more convenient. The state table is also known as state transition table. The table contains rows and columns to store information. All the inputs, transitions, outputs are represented in the table. Conventions : The conventions that are to be used while constructing state table are, (1) (2) (3) Every state in the state graph is represented as the row of table. Every input condition is specified in columns. There should be specification of next state in the table. The intersection of row and column would give next state. Example : Consider an example for hard disc recovery state graph. After drawing the state Staph, it is converted to transition or state table. SOFTWARE TESGING METHODOLOGIES PROFESSIONAL. PUBLICATIONS Scanned with CamScanner78 (1) Hard Dise Recovery : The Hard disc recovery indicates that the faulty hard disk shout be recovered. In order to recover it, we need to check whether it is a 900d sector or bad sector (Hard disc consists of several sectors of data). If it is good, no neeq to recover it and if it is bad then there are few cases that may arise. They are, () The hard disc can be “repaired.” il) It is not still repaired then “format” it by removing it. (ii) Still if it Is bad then declare the sector of hard disc as “damaged”. (2) State Graph : To draw the state graph, the inputs can be “good sector” and “bag sector” and outputs can be “NOP” (no operation), “repair”, “format” and “damage”, The state graph would look like in Fig. 7.6. 1 good sector/ NOP Trg Sy (s) bad sector/Repai 3 te Graphs and Transition Testing [Unit - viy 7 4 good sector/| Bad sector/Repair NOP damage HERI State Graph for Hard Disc Recovery THe state graph can be explained as, () “S" is the starting state and at 's’ sector and output is NOP, (i) If the hard disc have some bad sectors, state S would process to state P for repairing with input as bad sectors and output as repair. (il) If the sector Is repaired at state P, it sends input = good sector and output = NOP to state "S” and if not repaired it is send for further processing to state *Q’ with input as bad sector and output-as Repair. - if there are no bad sectors then input is good SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerFer ing (Unit - Vil] (wv) If it Is repaired at 'Q’ then the good sector/NOP is sent to starting state “S”. Else it Is processed to state R for formatting with input as bad sector and output as format. (v) If it is found to be good at state ‘R’ after formatting then the message good sector/NOP is sent to starting state “S", Else the message bad sector/damage is sent to final state °F”. Hence if state F is reached, the hard disc sector is confirmed to be a’damaged one. @) State Table : The state graph for hard disc recovery should be converted to state table. ‘ So the things to be considered are, States :S, P,Q, R, F Inputs : good sector bad sector Outputs: NOP (no operation) repair format damage. The state table would be, HEEDSERANT State Table for Graph in Fig 76 Inputs. Good Sector | Bad Sector States s S/NOP | P/repair P S/NOP | Q/repair When device has most similar but few different contro! functions. (i) The state table has more uses in, > Communications. > Telephony. Ail) This ‘technique can provide fast response time. (W) This technique would work better for small graph and not that good for big graphs. (v) For big state graphs the graphs should be Partitioned and hierarchy should be ‘considered. (® Application Comments for Testers : There are some comments that should be Considered for testers. They‘are, () The details of the implementation or the economics'of this t echnique are not considered by the independent testers. (i). But they concentrate on representation of state graph or state table and behaviour of these system would help in designing test case effectively. (li) If the implementation of the state graphs is done by the programmers eplicitly it would be easy for the tester. = (W) The tester’would be concerned only with the bugs buried in it, ( When there is an appropriate FSM model then there will also be appropriate FSM implementation. This is the relation between model and implementation, () If the programmer is shown with the tests developed it would lead them to Consider it as technique of implementation. twine resee METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerGrate, State Graphs and Transition Testing (Ug, Q10) Write testers comments about state graphs? [Aug./Sep. - 08, Set - 3, Q7(a), M(8)], [May - 11, Set - 3, Qi(), Ma [Nov. - 10, Set - 2, 9216), May Answer : Note : Refer Q.No. 9, Topic: Application Comments for Testers. EZMIE Good and Bad State Graphs Q11) Explain different good and bad state graphs with examples. [May - 11, Set - 1, Q5, M(16)], [Aug./Sep. - 08, Set - 1, Q7(b), ay [Nov. - 10, Set = 3, Q6(b), may Answer : Good State Graphs : The good and bad state what kinds of graphs are used in test desi in case of state graphs. They are, graphs are identified or judged based on igning. There are some principles of test design (2) The number of states in the state graph must be same as the product of possible number of factors that make up the state. i.e., the number of permutations of all values and all properties/attributes of the system. (2) For every unique combination of state and input, there should be only one transition / specified. 2] (3) For every transition, there should be atleast one.sensible output. ! (4) Each and every state there should be a sequence of to the starting state. inputs ‘that moves the system Other than the above stated ones there are’ some other criterions tobe considered for good graphs. They are, (1) The number of input codes for a state graph must be atleast two. because only fe” kinds of state graphs can be constructed with one input code. (2) A ‘good state graph has at least two in put symbols. With one symbol only a limited number of useful graphs are possible. Bad State Graphs : The state graphs which cannot be good and which do not follow atv Principles of good state graphs are known as bad state graphs. The state graphs which are not reachable and which are buggy are bad state graphs Examples : There are some. cases to show bad state oraphs, They are, shown in Fld 77 SOFTWARE TESGING METHODOLOGI PROFESSIONAL PUBLICATIONS PROFESSIONAL PUBLICATIONS eR al Scanned with CamScanner: 15 Gate, State Graphs and Transition Testing [Unit > Vil] 5 u ee ee a » ab b a) HERA Exampier In the above figure, the state 2 once reached would never be left. As a result the starting state cannot be achieved. It violates the principle of good state graph. » a bd wb Q) a,b HGRA Exampie2 The state *3’ cannot be entered at all as there is no path from 2 to 3. This leads to unreachable paths. Hence bad or improper graph. a,b 4,2 @) ez Example 3. Here both the states 1 and 2 are not reachable as there is no path between them. a a b @) ea There is no transition for input b at state ‘2’. If input ‘b’ is received at state ‘2’ the path is undefined. si a b 4 a,b ), a (RA Exampies There are two different paths for the same input on same state. The system will be in confusion to consider the path when input ‘a’ is given at state 1, The above discussed are some of the improper or bad state graphs. $0) SEWaRE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerBate, State Graphs and Transition Testing [Unjy ij — aca ae ae Taal lon Tse ee jh? Q12) Differentiate between good state graph and bad state grap UFeb, - 07, Set - 4, Q7(a), M(B) INov. = 06, Set - 1, Q7(b), may INov. - 08, Set- 4, arg) [May = 11, Set - 4, @2(a), wey Nov. « 10, Set - 1, @3(a), may une - 10, Set - 2, @5(a), may [Now/Dee, - 09, Set - 3, Q2(a), may WEEQEEE Comparison between Good and Bad State Graphs Good State Graph Answer : Bad State Graph If the elements of the state graph i.e., inputs, transitions, outputs are clearly specified and they are easily under- standable, then they are said to be good state graphs. If the elements of the state graph are not specified clearly thén they are said to be bad state graphs. In a good state graph, every state should havea sequence of inputs that drives the ‘system to the starting state. In a bad state graph, the sequence of in- Puts does notlead to the initial state.» There should be only oné transition | More than one Specified for one state and input combi. | fo nation. transitions are specified every state and input combination, There would be only one output for.| There might be none or moré than one every transition because unique output | output for every transition which results Bives clarity otherwise it leads to confu- | in improper state pranh, sion. Here find. EZR state Bucs Q13) Explain in detail about State Bugs? bugs are tess and they are easy to | Here bugs are difficult to find. more’ and they are very (or) Explain the reasons for occurrence of Stage Bugs? SOFTWARE TESGING METHODOLOGIES Scanned with CamScannerthe reasons for which the state bugs arise are, w Number of states. {@) Impossible states. @) Equivalent states. 1) Number of States : The number of states in the state graph can be considered as the number of states that are required to identify the behaviour of the system. In the context of the database, the state is the set of values of variables or attributes. Every state of the state graph is very important to the state testing. So it is essential to find the number of states. The number of states can be identified by, () Finding all factors of the state. (i) Finding all the possible values of each factor. The number of states can be ‘identified by multiplying the factors and all possible values. (2) Impossible States : There can be some combinations of factors that may appear to be impossible. If these factors are included, they lead to the impossible states. The impossible states do not have any meaning in the systems as the impossible states are the one which are not: possible to occur. . Example : Consider’an example to understand the case of impossible states. a EEESEEAT Example forimpossibie States $ > Direction Forward, Reverse, Stop | =3 factors Gear B,N,1,2,3,4,5. =7 factors Engine Operation | Running Stopped | =2 factors Engine Condition good, faulty = 2 factors The total number of states is obtained by multiplying factors with their possible values, 5 The total number of possible states in the above example are 3*7*2*2 = 84 states. Out of 84 states, all states may not be possible to’ achieve. 8 OFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerition Testing [Urine Tics. es ae sqeiorepta ot transition TSG In Table 7.3, there are two functions of engine ‘operation and engine Condition, ing nm runn stopped ‘engine operation 7. good engine condition faulty The possible states with this are, 2"254. They are, (2) Good, Funning (2) Good stopped. 3) Faulty, running (4) Faulty, stopped. Consider the third case, when the engine condition is faulty the engine is in running operation mode. But in real world, when an engine is not working, how can a vehicle be in running mode? The condition is impossible to occur. Out of 4 states. Only 3 states are possible and 1 staté is impossible. If only three possible states are considered, then the total number of states would be, 3* 7 * 3 = 63 states. Out of 84 states, only 63 are possible and 21 are impossible. InrERENce + The above discussion concludes that the “impossible statés” increases the number of states and there by increases the test cases. Therefore they should be identified and removed. (8) Equivalent States : If every sequence of inputs from one state generates exactly the same sequence of outputs as other states, then both the states are said to be equivalent states. When both the states produce same output then only state would be enough instead of two states, SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannergE ; Ph Fiate Graphs end fran: ing [Unit - Vil] Example : Consider.an example to understand the concept of equivalent, states: Example of Equivalent States In Fig. 7.12, the ‘S’ is the start state and after receiving inputs i, j from start state, the states travel in different branches. But after travelling a sequence of steps, they are resulted in the same output j.e., reaching the same’state "R”. Such states are considered as equivalent states. ‘The routines 1, 2 and 3 in the above figure are a set of statements which are not important to be mentioned. When two states are found to be equivalent, they can be minimized by combining the states as shown in Fig. 7.13. Combined Equivalent States The equivalent states are merged or combined in order to, “() Simplify the software. a (i) Reduce the bugs. But still bugs may occur due to differences in views made by the programmer or tester 'n determining the equivalent states. In order to avoid such confusions, a common Procedure is developed to identity these equivalent states. Procedure : When the state table is drawn for the given state graph’ then, » ") If one state of row has the same sequence of inputs, transitions and outputs as the other row except the state names and inputs, then the behaviour of the system 'n two sets of rows is identical. So the two states can be considered as equivalent States and they can be combined, Q i ) I two sets of rows have same identical state graphs with respect to the same: sequence Of inputs, transitions and outputs except state names then those two sets can be Combined with each other as they are equivalent states. Scanned with CamScanner| Example : Consider an example to'illustrate the above two steps. " " WERENT eauivatent States The above Fig. 7.14, is the example of Step 1. Apart from the inputs p and-g the behaviour of states 1 and 2 to distinguish them, there is no other difference, There is no difference in the bahaviour in two states @ and @ other than their inputs. So they are considered to be equivalent and they can be merged, (3) Consider another example to demonstrate step ©. J Ss nh i | a | 3 aaa 22 3 2 em | SOFTWARE TEEGING METHODOLOGIES PROFESSIONAL PUBLIGATIONS — Scanned with CamScanner721 (c) [EERE Mersed Equivaient states In Fig. 7.15(b), the rows are identical except’for the state name. The rows that gre equal are 11 = 21, 12 = 22, 13 = 23. 0 the state graph can be replaced with Fig. 7-15(c). It is not that easy to find the state graphs with equivalent states. Bugs arises in the cases where states seems to equivalent but the proof of equivalence cannot be carried at every input sequences. ‘ Such an example is shown in Fig. 7.16. ply p/w p/u ply “ piw piu =U States That Cannot be Merged In the Fig. 7.16 the input and output’ sequences would be, The two set are not equivalent but if analysis is not completely done, there are chances ef believing them as equivalent states. aaas é EN Ky SOMWawe recnnsa ucruanaLaGis PROFESSIONAL PUBLICATIONS Scanned with CamScannerSS ee EZ@ transition Bugs © Q14) Explain about transition bugs with examples? Answer : The transitions bugs can be caused due to, a) Unspecified and Contradictory Transi-tions. (2), Unreachable states. (3) Dead States. (@)_ Unspecified and Contradictory Transitions ® Unspecified Transitions : Transitions are nothing but the lines that are used to link the states. For every state input combination, there should be a transition specified. If the transitions are not specified then the bugs can occur. due to unspecified transitions between the: states. The system should adopt a mechanism such that when the transition is not Possible in the state then there should be a method that prevents the occurrence of input in that state. If such a method is not there, then the input becomes useless or inefficient. It means that there should be only one transition specified for each state and input combination so that the transition bugs due to unspecified transitions can be avoided. Gi) Contradictory Transitions : Contradictions and ambiguities cannot occur in a Program. It Is impossible for a program to be ambiguous because every input is processed to produce some or other output. It does not matter whether the output is correct or incorrect. In the same way, the program or the software cannot be contradictory even because the computers can perform only one thing at a time. Example : If a single bit in a state is either hidden or misplaced by the programmer then the number of states in the graph may be doubled. Those states may produce contradictory and ambiguous outputs. Such contradictions and ambiguities can be caused by transition bugs. Hence the state graphs must be designed carefully and efficiently so that for each state input combination, the transitions and outputs must be recorded to identify ie reduce the transition bugs. (ili) Conversion of Specifications Into State Graph ; The most common source for ambiguities and contradictions are specifications. There is a method for converting the specifications into state graphs so that the contradictions can be removed: SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScanner |yo rules for Conversion : There are some rules that are to be followed while conversion. These are in case of tape control. Rut 1: An error counter will be maintained by the program. The counter will be incremented when there is an error. Rute 2 : The block should be rewritten if there is an error. Ruut 3: If there are three continuous errors, erase the tape to some extent and rewrite the block. Ruut 4 : If there have been three such erasure i.e., removing the errors and if another error occurs then put the unit as “out of service.” Ruut 5 : If the act of removing the errors i.e., erasure was successful then return to normal state and error counter should be cleared. Rute 6 : If the “rewrite” was done unsuccessfully then increment the counter, forward the state and try to rewrité it once again. Rute 7 : If “rewrite” was done successfully then decrement the counter, return to previous state. Example : Consider the example of the usage of the tape control routine. Le the state graph look like in Fig. 7.15. ok 8 ore) © 265) 8G) oso : alg Example State Graph Ruut 1. As no error has occurred, assign input = ok and no operation is performed. So O/none is assigned. If error occurs then it is incremented as in Table 7.4. EES State Table for Rule 1 SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerRute 2: As there is an error rewrite the block. Son on “rewrite”, we gét, State Table for Rule 2 2/rewrite 3/rewrite Rute 3 : From the above table, as there are three successive errors, erase some amount of tape at 3° error and then rewrite it. MEERA State Table torres Input > . oe ok are A 0/none 1/rewrite B 2/rewrite iS 3/rewrite, erase, rewrite D 4/ rewrite, erase, rewrite E 5/ rewrite, erase, rewrite F 6/ rewrite, erase, rewrite : SOFTWARE TESGING METHODOLOGIES Pi 'ROFESSIONAL PUBLICATIONS ESIGN AE RUBITCHTIONS Scanned with CamScannerFae Graphs and Transition Testing [Unit = VI 7] 7.25 : gue 4 Even after erasing some amount of tape, if there is occurrence of one more error then put “out of service” to that unit. EAA State Table for Rule 4 4/erase, rewrite 5/erase, rewrite Rue 5 : If erasure was successful, then return to normal state and clear the counter. HESERZT State Table for Rule 5 Input > ok Error State 1 A Q/none| — 1/rewrite : B 2/rewrite c 3/erase, rewrite D 0/none | 4/erase, rewrite E 0/none | 5/erase, rewrite E 6/out Rute 6 ; If rewrite is unsuccessful, the error counter should be incremented and State should be forwarded and try another “rewrite”. Ruut 7 ; 1f rewrite is successful then the counter should be decremented and should be returned to the previous state. Swans RETESGING METHODOLOGIES. PROFESSIONAL PUBLICATIONS Scanned with CamScannerind Transition Testing [Uap 7.26 TERA State Table for Rule 7 vi 2/rewrite 3/etase, rewrite 4/erase, rewrite 5/erase, rewrite 6/out ! This is how’ the specifications are got rid of ambiguities and converted to state graphs. (2) Unreachable State: + If there is some state which no input sequence can reach then that state is known as unreachable state. There is possibility of unreachable states fo occur. There are transitions from unreachable states to other states even, because the states became unreachable due to incorrect transitions, The unreachable states can occur from “impossible states.” If groups of connected states are isolated, there can be two possibilities, They are, (The missing of transition may result in a bug. (i) There are some unknown transitions which the Programmer does not know: (3) Dead States : Dead state is such a state that if it is entered once, that state cannot be left. The inputs cannot be processed from the dead state. Example b ab a HERG Dead State Gran SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerIn Fig. 7.18 if the state @ is reached then that state cannot be left. So state @ can be considered’ as dead state. The “dead state” is not completely a bug. But it is supposed to a bug- For example, if some software is designed to fuse the bomb then should be atleast one such dead state. A set of dead states occur in the software program because the programs has two operation modes. They are, (In the first stage, an initialization process takes place that consists of number of states to ‘be initialized. In the second stage, the strongly connected set of functional states takes place in which the routine of operations of the states cannot be completed. Encoding is an essential process for converting or coding the inputs, transitions and outputs of the states in order to obtain the secure process of finite state machine. Encoding process is applied in both explicit and implicit finite state machines. The encoding bugs are more common at the time of input coding, output coding and state coding in an explicit finite state machine. On the other hand, the encoding bugs may also exist in an implicit finite state machine, because of different views made by the programmer and tester. Q15) Explain all the rules in the conversion of specification into a state graph? [April/May = 09, Set = 2, Q7(b), M(8)], [April/May - 08, Set - 4, Q7(b), M(8)] Rules for Conversiot 16) Explain with example how to convert a specification into a state graph. Also discuss how contradictions can come about? [April/May - 09, Set - 1, Q7, M(16)}, [Aug./Sep. - 08, Set - 4, Q7, M(16)] [Dec. - 11, Set - 1, 2, Q2(b), M(Q)], [Dec. - 11, Set - 3, Q4(b), M(8)] [Dec. - 11, Set - 4, Q5(b), M(8)] Answer ; Note : Refer Q.No. 14, Topic : Conversion of Specifications into State Graph. fo WARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerTG ee Q17) Explain the reasons the arises state bugs and transition bugs with rules? [une - 11, Set = 1, Q6, Mcrgy Answer : Refer Q.Nos. 13 and 14. EES Output Errors Q18) Explain output errors in State Graphs. Answer : ‘The output for the transition could be wrong even if all the states, the transitions ‘and inputs are correct and there are‘no dead or unreachable states. Outputs are not dependent on transitions and inputs. They should also be tested and verified independently. The tester needs to distinguish the state graph that is correct and whose output iis incorrect. ‘The reason for the wrong output would be incorrect call to the routine that should be executed for output. This is a minor bug. EZEZM Encoding Bugs Q19) Write about Encoding bugs? Answet : The process of converting or coding the inputs, transitions and outputs of the states in order to obtain the secure process of finite state machine is known as encoding and it is the most essential process. Encoding is done both in explicit and implict way. The probability of bugs is more in explicit finite state machine implementation. Bugs can even ccur in implicit finite state machine. This can be because of different views made by Programmer and tester. ‘The behaviour of finite state machine is invariant under all encodings. Consider that the states are numbered form 1 to k. If the states are*numbered again with arbitrary Permutation, even then there is no change in finite state machine. But in programmer's view, the behaviour of finite state machine is changed when different encoding is applied. The potential size of the code is understood by the implementation of fields as @ bunch of bits or bytes. The encoding process is said to be running if the number of code value is less than this potential. 3 In strongly typed languages, the process of encoding is a type conversion from @ pointer type conversion from a pointer type of inte: ger and so on. m has tO be viewed for this kind of bugs, 3 4 yn. The progral SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScannerZo Grate Orphd id Veni Taam a rc Go Slate Graphs and Transition Testing [Unit Vi] os 920) Write short notes on, . (a) Transition bugs (b) Dead states. (ou statelEnexe (@) Encoding Bugs. [Aug./Sep. - 08, Set - 2, Q7, M(4+4+4+4)] [Feb. - 08, Set - 2, Q7, M(4+4+4+4)] INov. - 06, Set - 2, Q7, M(4+4+4+4)], [Nov. - 05, Set - 2, Q7] [Nov./Dec. - 09, Set - 2, @4, M(16)] Answer : (@) Transition Bugs Note : Refer Q.No. 14, Topic : Unspecified and Contradictory Transitions. (&) Dead States Note : Refer Q.No. 14, Topic : Dead States. (@ State Bugs Note : Refer Q.No. 13. (@) Encoding Bugs Note : Refer Q.No. 19. | 21) What are the types of bugs that can be caused in state graphs? [Aug./Sep. -'08, Set - 3, Q7(b), M(8)] Answer : The different kinds of bugs that can bé@Bused in state graphs are, (1) State Bugs. : (2) Transition Bugs. (3) Output Errors. (4) Encoding Bugs. = Scanned with CamScanner7.30 State, State Graphs and Transition Testing (uni > Vij () State Bugs | | Note : Refer Q.No.13, | @) Transition Bugs Note : Refer Q.No,14. 3) Output Errors Note : Refer Q.No. 18. @) Encoding Bugs Note : Refer Q.No. 19. EZR state testinc 'Q22) Explain State Testing? [May - 11, Set - 3, Q1(a), M(8)], [Nov. - 10, Set - 2, Q3(a), Ma) : _ (or) What are the principles of state testing? Explain its advantages and disadvantages? [May - 11, Set - 2, Q4(a), M(8)], [May - 11, Set - 4, Q2(a), M(8} INov. - 10, Set - 1, Q3(b), ‘M(8)], [June - 10, Set - 4, Q2(b), M(8)] [Nov./Dec. - 09, Set - 3, Q2(b), Mi: i. [April/May - 08, Set - 3, Q7(a), M(8)] ~ 07, Set - 4, Q7(b), M(8)], [Nov. - 06, Set - 1, Q7(b), M(8)] [Nov. - 05, Set - 4, Q7(b)} Answer : State testing is defined as a functional testing technique to test ti: functional bugs in the entire system. The principles for state testing are very similar to the principles for Path testing. For path-testing it is not possible to test every possible path in a flowgraph. Similarly for state testing, it is not possible to test every possible path is a state graph. In.a state graph a path is a sequence of transitions caused by a sequence of inputs like path testing, state testing examines each transition in a state graph to guarantee complete testing. One of the important principles of a state testing is that it allows the testers to gv _ the priority to the interesting nodes in order to initiate the state. In state testing, the primary interest is given to the states and transitions rather than outputs. SOFTWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS Scanned with CamScanneree Gare State Graphs and Transition Testing [Unit viy 7.31 To begin state testing do the following, (0) Define a set of input sequences such that when the system starts from the initial state, after going through all states it gets back to the initial state. Define expected next state, expected transition and also expected output code for each step in each input sequence. @) At last, @ set of tests define three sets of sequences such as input sequences, transition sequences and output sequences to complete the test. advantages : The advantages of state testing are as follows, (1) State testing is useful when the error corrections are less expensive. (2) State testing Is also useful when the testers want to detect a specified input or when the order of inputs sequence is important. @) A state testing is specifically designed for catching the deep bugs. (4) A state testing provides the biggest rewards during the design of the tests. Disadvantages : The disadvantages of state testing are as. foiiows, {i) State testing does not provide thorough testing because when a test is completed, there might be some bugs remained. in the system. (2) Testers requires large number of input sequences to catch transition errors, missing states, extra states and the link. Q23) What are the software implementation issues in State Testing? [Aug./Sep. - 08, Set - 1, Q7(a), M(8)] © Answer : Testing plays a very important and major role in process of development. Implementation Issues i (1) The bugs in the software can occur through many different cases. Due to these bugs it is impossible to pass through or cover all the paths-in the state graph. The bugs May occur due to, () Incorrect number of states. (i) Incérrect, state transitions. (il) Incorréct transition output. (iv) Dead states. (v) Unreachable states. The occurrence of bugs will be more in strongly connected graph. SORWARETESGING METHODOLOGIES ~~ PROFESSIONAL PUBLICATIONS Scanned with CamScanner——aararare raphe and Tramtion Tasting [Unity ee Eee 7.32 ne It means some state graphs ma (3) The state graphs are generally y + consume less time and some ma’ jot time bounded. y consume more time. (4) When the system has no state and when there are improper responses, the stat. diagrams are not applied. (5) The output errors in state graphs can be caught easily but for sequence covers should be used. transition errors tong (6) Bug catchers should have a sufficient demonstration inorder to catch different kings of state graph errors. (7) When each and every thing is clearly specified such as transitions and outputs for each state input combination, it would be easy to catch bugs. (8) State testing is considered as bottom line method as it supports functional model rather than the structural details. EZGHMETESTABILITY TIPS EZGKN Switches, Flags and Unachievable Paths Q24) Write short notes on switches, flags and unachievable paths. Answer : The switch and flag functions in the same way. The switches and flags are most essential tools for testing the state graphs. They are used to test the finite state machine in every possible state, In the early stages of finite state machine, a flag is initialized. and depending on this value a specific path is selected to find the easiest path for testing the finite state machine. Example ; (1) Consider the example of a program with one flag variable as shown in Fig: 7:19. A “ LA m “OL O—GLO A 5 x ‘ ) GRALY Program with One lag In Fig. 7.19(a), the flag value ‘A’ is assig-ned a value and it is to be-evaluated- Depending on that value, the path is branched to continue the testing in both the ways. This testing can also be done by removing the flag and dividing ‘L’ into’ "© paths as shown in Fig. 7.19(b). SOFTWARE TESGING METHODOLOGIES PROFESSIONAL. PUBLICATIONS _— A. $$... _ROFESSIO NAL» PUBLICATIONS a Scanned with CamScannerGate, State Graphs and Transition Testing [Unit = Vil] 7.33 There are four paths named k, M, N, 0.-Where two paths are not achievable. The paths which cannot interact with each other are known as unachievable paths. _ The path ‘k’ is unachievable to ‘0’ and the path ‘N’ is not achievable to ‘M’. Two.paths are achievable. The path ‘x’ is achievable to M and the path ‘N’ is achievable to ‘O' Hence paths ‘KM’ and ‘NO’ are needed to cover the branches. (2) Consider’an example of a program with flag variables. K A Le ist Le DH [ER Program with Two Flags In the Fig. 7.20, there are two flags A and B. These variables are evaluated based on which the paths are branched. The option must be chosen to select the easier path. The main advantage of the implementation of the two flag variables is to remove the unnecessary combinations from the decision’ tree as in Fig. 7.20(b). Thus all the paths are achievable and all. are needed to cover the branches. [2 Essential and Inessential Finite State Behaviour Q25) Write short notes on essential and inessential finite stat’ “ehuviour. Answer : To understand an essential and inessential finite state behaviour, we need to know the concept of finite state machines and combinational machines. There is a difference between finite state machines and combinational machines interms of quality. In Combinational machines, a path is chosen depending on the truth values of predicates, Which in turn rely on the previous processing. The predicate truth values are the values Which once determined will never change and always remain constant. In these machines, @ path is equivalent to a boolean algebra expression over the predicates. Moreover, the Srder in makiiy decision is not important because it can be in any order. Combinational machines involve concurrent selection of paths as well as decisions. The sequence and finite state behaviour are not mandatory but they are outcomes of ©ombinational machines. For all possible inputs, the combinational machine. has exactly . %e state and one transition that leads to itself. SOFWARE TESGING METHODOLOGIES PROFESSIONAL PUBLICATIONS. a Scanned with CamScanner734 trate, State Graphs and Transition Testing [Unit yp State, State Graphs and Transition Testing [Unity The implementation of combinational program is based on decision table or decision tree to classify its control logic. Essential finite state machine is purely based on acknowledgement and has no Specific logic for implementation without acknowledgement. Even decision table or is unable to classify its behaviour until acknowledgement is stored in a table ang repeatedly called. The only problem with the essential finite state machine behaviour jg that it provides lots of work i.e., just for the sake of branch testing, every state must be tested which is not mandatory or essential. ‘The following are the conditions of inessential finite state behaviour. If these conditions are not satisfied then the behaviour of finite state machine is known as essential, (2)_If behaviour can be obtained by parallel program in data flow machine. (2) If behaviour is obtained from decision table or decision tree. (3) If expression of exit is equal to unity for a program including loops. (4) If the program's exit expression is not equal to unity but we don’t want to loop under the looping conditions. Q26) Write short notes.on, (@ Switches, Flags and Unachievable paths. (ii) Essential and Inessential finite state behaviour. [Nov. - 06, Set - 4, Q7(b), M(5+5)], [March - 06, Set - 1, 2, Q7(b)] INov. - 05, Set - 3, Q7(b)] Answer : : @ Switches, Flags and Unachievable Paths Note : Refer Q.No.24, (i) Essential and Inessential Finite State Behaviour Note : Refer Q.No. 25. EZEE Design Guidelines for Building Finite State Machines Into Your Code Q27) Write the design guidelines for building the finite state machine into code. [April/May - 09, Set - 2, 4, Q7(a), M(@)) (or) } Mention design guidelines for building finite state machines into your code? SOFTWARE TES‘ ING METHODOLOGIES PROFESSIONAL PUBLICATIONS SOFTWARE TESGING METHODOLOGIES PROFESSIONAL _PUBLICATIO™= Scanned with CamScannerE.: “Fate Graphs ‘and Transition Testing [Unit - Vil] 735 [Nov. - 06, Set - 4, Q7(a), M(6)], [March - 06, Set - 1, 4, Q7(a)] [Nov. - 05, Set - 3, Q7(a)], [Dec. - 11, Set - 1, Qi(a), M(8)] = 11, Set - 2, Q2(a), M(8)], [Dec. - 11, Set - 3, Q4(a), M(8)] [Dec. - 11, Set - 4, Q5(a), M(8)] jaswer qnere are some guidelines for building the finite state machine into the code. They we, i Know how the Implementation is of finite state machine is done both in software and hardware. {9 Now start the designing of abstract machine and check it for the requirements that you want. Carry out the analysis in the form of a state graph or state table with three or more states. {@) Design the state machine explicitly i.e., clear and understandable. It includes, {Input encoding. (i) Output encoding. i) State-code assignment. (iv) Transition table. {y), Output table. (vi) State storing. (vil) State symbol product. All this process is done at PDL level and its main aim is that it should be clear and understandable. (4) Prototype test must be conducted thoroughly to determine the processing time and space of explicit finite state machine design. (5) If time or space is effecting the overall system, then use shortcuts to complete the design process. It can be achieved by implicit design of finite state machine in this order_output encoding, input encoding, state code, state symbol product, output table, transition table and state storage. 8) If there are more than dozen states then ‘construct a hierarchical design. () If there are more number of states routinely then build, buy, or implement tools and languages that are used to implement finite state machine as software. (8) The capability to initialize to an arbitrary state must be inbuilt together with the transition verification instrumentation. x SOFTWARE TESGING METHODOLOGIES PROFESSIONAL. PUBLICATIONS Scanned with CamScanner AQ28) Explain state testing and testability tips. Answer ; aaa hs and Transition Vij [April/May = 09, Set « 4, @7, M(16)], [March - 06, Set 4 an State Testing Note : Refer Q.No.22. q Testability Tips : The ti Q) @) 3)" (4) ips for testing differs in view of programmers and testers, Some of the tips are. The designing of the sot ftware by a programmer should be in such. a w, should be error free an id all the testing techniques should be ineffective Building explicit FSM and im The FSM can be of any length i.e, it can contain any number of states and any number Of states can be bad among them. Irrespective of those things, the FSM should be built in such a way that it should identify how to implement each part of that model, gs from the machine to test tc~aus ¢ FSM even though it is not. Identify the essential and non essential behaviour of FSM and non essential part should not be implemented. ay that jg e, plementation would be. the primary key of testing, Eliminate the ‘switches, fla © with these things, the machine may look lik Following the guidelines of designing, build the finite state machine, chine is invariant under all encodings, Justify. Bone - 10, set - 3, a7, m(16), (April/May - 09, Set - 3, @7, M(16] (April/May - 08, set - 2, Q7, M(16)) Answer + Finite State Machine Note : Refer Q.No. 1. Design Guidelines Behaviour of FSM SOFTWARE TESGING METHODOLOGIES — ee es Note : Refer Q.No. 27, ae Note : Refer Q.No. 19, e © % Scanned with CamScanner