ACSL - 6: What Does This Program Do? & FSAs and Regular Expressions

2019-10-16 Views ACSL 经验1005字5 min read

This passage will focus on the Pseudo-code and regular expression in ACSL exam.

伪代码

操作符

! (非) 
^ or ↑(指数)
*
/ (除法) 
% (取余)
+ - 
> < >= <= !=(不等于) ==(判断等于,单个等号代表赋值) && (and), || (or) 

函数

abs(x) - 绝对值
sqrt(x) - 平方根
int(x) - 最大小于等于x的整数

顺序执行语句

INPUT variable
variable = expression (assignment)
OUTPUT variable

逻辑判断语句

IF boolean expression THEN
Statement(s)
ELSE (optional)
Statement(s)
END IF

循环语句

WHILE Boolean expression
Statement(s)
END WHILE
FOR variable = start TO end STEP increment
Statement(s)
NEXT

数组

一维数组使用一个下标表示,如A[5]代表A中第六个元素(一般下标从0开始)
二维数组使用[行,列]表示,例如A[2,3]一般表示第3行,第四列
在ACSL中,数组下标的起始位置会在问题中说明

字符

S = “ACSL WDTPD” (S has a length of 10 and D is at location 9)
S[:3] = “ACS” (从下标为0开始,从左到右提取字符,到下标为3前停止;及不包括3)
S[5:] = “WDTPD” (从下标为5开始,从左到右提取字符,到字符串末尾)
S[2:6] = “SL W” (从下标为2开始,从左到右提取字符,到下标为6前停止;及不包括6)
S[0] = “A” (提取0下标字符)

字符的合并一般使用 + 号

Problems & Solutions

点此

FSA & Regular Expression

前言

regular expression picture

在以上FSA中,存在三种状态:A,B和C。初始状态为A;最终状态为C
如果要从状态A到状态C需要经过状态B,也就是走字母x
当进入状态B后,有两个规则:继续走x,即绕B一圈;走y到达C
如果到达状态C,还可以一直走y不断绕C旋转【有多个圈包裹的就是最终点】
所以我们可以把以上所描述的路线总结成这些字符串:xy,xxy,xxxyy,xyyy,xxyyyy

这就是正则表达式的图像表示,正则表达式就是提供了一个代数层面上的规则来描述这个图像

正则表达式的规则如下:

  1. 空字符是一个正则表达式
  2. 输入符号集内的字符是正则表达式
  3. 如果a和b都是正则表达式,那么遵循以下规则
    1. 合并 "ab"
    2. 并集(类似于or) "aUb" or "a|b".
    3. CLOSURE "a*" (a可以重复0到任意次数)。*被称为克莱尼星号

正则表达式运算符的优先顺序为:Kleene Star,Closure,然后是并集。与标准代数类似,括号可以用来框住子表达式,如dca*b 可以表示 dcb, dcab, dcaab。

正则表达式性质

1. (a*)* = a*
2. aa* = a*a
3. aa* U λ = a*
4. a(b U c) = ab U ac
5. a(ba)* = (ab)*a
6. (a U b)* = (a* U b*)*
7. (a U b)* = (a*b*)*
8. (a U b)* = a*(ba*)*

正则表达式符号

符号 简介
| 类似于or,分割类似项。如匹配"gray" or "grey"
* 代表重复0次到无数次
? 问号代表其前面字符出现0次或1次
+ 加号代表前面元素出现1次到无数次
. .匹配任何字符,比如a.b可以匹配"a7b", "a&b", 或者 "arb", 但是不能是 "abbb"
[] 匹配在中括号内的字母或数字等,如 [abc]匹配"a", "b", or "c"。[a-z]匹配从a到z的字母[abcx-z]匹配"a", "b", "c", "x", "y", or "z",这也可以写成[a-cx-z].
[^] 匹配不在中括号内的字符,如[^abc]匹配不是"a", "b", or "c"的字符
()

括号里代表一个子表达式

Problems & Solutions

点此


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!


References:

  1. http://www.categories.acsl.org/wiki/index.php?title=What_Does_This_Program_Do%3F
  2. http://www.categories.acsl.org/wiki/index.php?title=FSAs_and_Regular_Expressions

logo   WRITTEN BY:Serence

一个程序员和文艺青年的博客!

本文章采用CC BY-NC-SA 4.0进行许可。转载请注明出处!

上一篇

诗与话 - 2


下一篇

ACSL - 5: Data Structure & Recursive Functions