文法和语言的基本知识
一、什么形式化的方法
用一套带有严格规定的符号体系来描述问题的方法
二、什么是非形式化的方法
对程序设计语言的描述从语法、语义和语用三个方面因素来考虑
所谓语法是对语言结构定义
所谓语义是描述了语言的含义
所谓语用则是从使用的角度去描述语言
三、符号串
字母表和符号串
字母表
符号串
EX：
={a,b,c},则a,b,ab,ba,……都是上的符号串（两个1都不要）
注意：
①符号串中符号的顺序很重要；如：ab 不等于 ba
②不包括任何符号的符号串称为空串，用
表示
EX：={a,b,c,d,……z}。a,b,c……都成为符号
hello，world，def，cout，cin，都是上的符号串
符号串的长度：符号串所包含的个数，设x是一符号串，其长度记为|x|
EX: |hello|=5, |mian|=4, ||=0
四、符号串的运算
符号串的连接
设X和Y是符号串，则串XY称为它们的连接
EX：ABC，Y=10A，则XY=ABC10A，YX=10AABC
注意：X=X=X=X
符号串的集合：若集合A中元素都是某字母表上的符号串，则A是上的符号串集合
集合的乘积
设A和B是符号串的集合，则定义AB={XY | X∈A，Y∈B}
EX：A={a，b} B={c，d}，则AB={ac，ad，bc，bd}
注意：A{}={}A=A，{}≠{}＝
符号串的幂运算
EX：设X是符号串，则x自身的连接称为符号串的方幂
如：
符号串集合的幂运算
设A是符号串的集合，则定义
={}，
=A，
=AA，
=
A
符号串集合的正背包
和闭包
