( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230208{main}( ).../view.php:0
20.0001230952include( '/var/www/html/head.php' ).../view.php:2
30.0009250312isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(26)-使用FAS处理输入

小学计算思维课程(26)-使用FAS处理输入

小学计算思维课程(26)-使用FAS处理输入

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第二十六课:使用FAS处理输入

上节课我们通过玩游戏初步认识了有限状态自动机,也就是简称为FSA的东西。其实FSA在我们生活中挺常见的,比如我们拨打银行的服务电话时,往往会听到“自助服务请按1,人工服务请按9……”,这时你按下的数字就作为输入传送到电话那头的FSA处理机中。只要您理解它的工作原理,我们也可以轻松设计这样一个服务系统。

在计算机科学中,我们会用圆形代表各个地点,用箭头表示移动的方向,比如左图可以转化为右图:

上节课的小游戏也可以用下面的FSA图表示:

最终目的地“长老殿”使用双线圆圈表示。在FSA中,我们说上图中一共有7个状态,7号为终结状态,输入A或B可以引起状态的转移。

问题:

1.上图中,到达“长老殿”的最短路线需要输入哪些字母?

2.上图中,是否存在循环路线,请举例说明。

3.请问输入BBBABBABAB能达到“长老殿”吗?

4.输入BAABAAABABAB能达到“长老殿”吗?

5.输入BBBAAAB能达到“长老殿”吗?

FSA是验证输入是否合法的最有效手段,下面有3个FAS图:

1.请问在(a)图中,下面哪个指令可以被接受(达到终结状态)。

AB     BABAA         ABBBA         AAABABA         AAABA

说一说可被接受的输入有什么共同点?


2.请问在(b)图中,下面哪些指令可被接受。

AB     BA     ABAB     AABB     ABABA         ABBA

说一说可被接受的输入有什么共同点?


请问在(c)图中,下面哪些指令可被接受。

B        BBB         BBA         ABBA         AAA

说一说可被接受的输入有什么共同点?


除了以上用途,某些使用FSA的计算机程序,不仅可以处理用户输入的句子,甚至可以自己有模有样的造句呢!请观察下面的FSA图,试着用它来造几个句子。

试着设计一个能造句的FSA,让你的同学也来用它造句。