子字符串(子串) 字符串中若干连续符号组成的字符串 前缀:最左端的子串 后缀:最右端的子串 例如o= abbas a,ab,abb是o的前缀 ab,ab,b是o的后缀 bd是的子串,但既不是前缀,也不是后缀 O本身也是o的子串,且既是前缀,也是后缀 e也是o的子串,且既是前缀,也是后缀
6 子字符串(子串): 字符串中若干连续符号组成的字符串 前缀: 最左端的子串 后缀: 最右端的子串 例如 ω =abbaab a,ab,abb是ω的前缀 aab,ab,b是ω的后缀 ba是ω的子串, 但既不是前缀, 也不是后缀 ω本身也是ω的子串, 且既是前缀, 也是后缀 ε也是ω的子串, 且既是前缀, 也是后缀
字符串的连接运算 设∝=an1a2…anP=b1b2…,b, aB=a1a2…,anb1b2…b称作a与B作的连接 tn a=ab, B=baa, aB=abba, Ba=baaab 对任意的字符串a,B, (1)(oB)=∞(6y) 即,连接运算满足结合律 (2) C=8=0 即,空串E是连接运算的单位元 n个a的连接记作c 如(ab)}= ababab
7 字符串的连接运算 设α=a1a2 …an , β= b1b2 … bm, αβ=a1a2 …anb1b2 … bm称作α与β作的连接 如 α=ab, β=baa, αβ=abbaa, βα=baaab 对任意的字符串α, β, γ (1) (αβ)γ=α(βγ) 即, 连接运算满足结合律 (2) εα=αε=α 即, 空串ε是连接运算的单位元 n个α的连接记作α n 如 (ab) 3= ababab, α 0=ε
形式语言 定义:∑的子集称作字母表上的形式语言, 简称语言 例如x={a,b} A={,b,,bb} B={n|n∈N Cabin,m21y D={e} 空语言O
8 形式语言 定义: Σ*的子集称作字母表Σ上的形式语言, 简称 语言 例如 Σ={a,b} A={a,b,aa,bb} B={a n | n∈N} C={a nb m | n,m≥1} D={ε} 空语言Ø