|
|
不多废话啊全明星赛模考18-19题就是这个FSA和正则表达式
什么是FSA -- Finite State Automation, 即有限状态自动机
可以理解为一个游戏
你是一个主角，你读字符，如果有相对应的字符，就按箭头移动，如果存在一种情况使得最后字符读完你刚好站在终点，那么这个字符串就是可以被接受的。
因此所谓FSA重要的只有：state, start state, final state, transition（我的状态，我最开始和最后的状态，以及字符往哪走）
基本上做这种FSA的题，如果没有联动正则，就手动遍历完事，类似布尔代数，这种逻辑类的题目他最多给你3-4个变量你手动遍历最简单最直接最高效最不绕弯子自然是好的。因此所有ACSL这种时间并没有那么紧迫的考试，如果你对这个知识点并不熟练，遍历是第一选择
那么如果要求你用正则表达式来表达FSA呢？（模考P18）
那也很简单，环就是*（因为一次性能转无穷多次），分叉就是两个的交集，正常的箭头就正常写就行
参考P18就可以简洁地理解本篇的意思
然后再难一点就是回头箭头
就是这个环路不止一个，而是很多个，那么就要整合起来循环，如类似(ab)*就是两个点之间A到B是a，B到A是b
比如起点是A那么这一小段可以代表成(ab)*a，因为*指的是可有可无
再者就是比如一个指向自身的环路，但是有两个环路a和b，那就要表示成(a U b)*
总而言之一定要模拟整条逻辑链，这样是最踏实的
|
|
发表于