程序设计语言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