程序设计语言S简介

变量:三种
输入变量\(X_1,X_2,... \)
输出变量\(Y \)
中间变量\(Z_1,Z_2,... \)

语句:三种
增量语句\(V \leftarrow V + 1 \)
减量语句\(V \leftarrow V - 1 \)
条件转移语句\(IF\ V\ ≠ 0\ GOTO\ L \)
若V非0则转至标号为L的语句,否则执行下一条

S语言的相关概念
1.变量:输入,输出,中间变量
2.标号:\(A_1,A_2,... \)
3.语句:增量,减量,条件转移,空语句
4.指令:一个语句或一个标号后面跟一个语句
5.程序:一个又穷的指令序列。指令数称为程序的长度
6.状态:若干个形如V=m的等式有穷集合,V是一个变量,m是一个数,代表该状态下V的值为m。
7.快相(顺势描述):有序对\((i,\sigma \),即将执行第i条指令,目前状态为\(\sigma \)。当\(i=q+1 \),q为程序长度时,称为终点快相。
8.后继:非终点快相的下一个状态。
9.计算:一个快相序列\( s_1,s_2,...\),包含初始快相、终点快相,且每一个快相之后为其后继。

    所属分类:TCS     发表于2021-09-15