A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.
The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition.
Example: coin-operated turnstile
An example of a simple mechanism that can be modeled by a state machine is a turnstile.
Considered as a state machine, the turnstile has two possible states: Locked and Unlocked.
The turnstile state machine can be represented by a state-transition table, showing for each possible state, the transitions between them (based upon the inputs given to the machine) and the outputs resulting from each input:
-
Current State Input Next State Output Locked coin Unlocked Unlocks the turnstile so that the customer can push through. push Locked None Unlocked coin Unlocked None push Locked When the customer has pushed through, locks the turnstile.
-
The turnstile state machine can also be represented by a directed graph called a state diagram (above). Each state is represented by a node (circle). Edges (arrows) show the transitions from one state to another. Each arrow is labeled with the input that triggers that transition. An input that doesn't cause a change of state (such as a coin input in the Unlocked state) is represented by a circular arrow returning to the original state. The arrow into the Locked node from the black dot indicates it is the initial state.
6-32 实验10_5_指针数组初步
已知一个总长度不超过10000的字符串，字符串中只包含大写字母“A—Z”、小写字母“a—z”和空格‘ ’。空格用于分割单词，空格的个数不超过1000个。你的任务是将字符串中用空格分隔的单词打印出来。 你要按照如下要求完成任务：
- 1.利用指针数组指向每个单词的开始位置。
- 2.把字符串中单词结束后的空格改为“\0”,然后使用指针数组将每个单词打印出来。
利用状态机建模求解
当我们扫描整个字符串时，当前查看的字符可能位于单词中，也可能位于间隔的空格上。因此，我们设计两个状态：
non-wordword
针对不同的状态，根据下一个输入的字符，可能会有状态的转移。比如：
同时，在不同状态在遇到不同的输入字符时，还会有一定的输出以及action。具体：
-
Current State Input Next State Output non-word blank non-word Replace blank with a '\0' letter word A new word found, and to do something... word blank non-word Replace blank with a '\0' letter word None
-
状态机的初始状态是non-word。对于输入字符串中的每个字符，只要不是'\0'，就运行上述状态机。也就是只要不是字符串的结尾'\0'，就重复做计算。
getString函数如下：
int getString( char * source , char *strPtr[1000] )
{
int count = 0; // count the number of word in the string
int index = 0; // index for every word
int isWord = 0; // 0 means on state non-word, 1 means on state word
char *s = source;
while (*s != '\0')
{
if (isWord == 0)
{
if (*s == ' ')
{
*s = '\0';
}
else // in case of letter
{
isWord = 1;
strPtr[index] = s;
index++;
count++;
}
}
else // in case of state word
{
if (*s == ' ')
{
isWord = 0;
*s = '\0';
}
else // in case of letter
{
// nothing to do
}
}
// next character
s++;
}
return count;
}
代码中是以状态为主轴进行计算的。也可以做适当的合并处理，简化代码。
