32语言和文法 L3={"b"|n≥1} S→>aSb|ab L3是不能用正规式描述的语言的一个范例 若存在接受L3的DFAD,状态数为A个 设D读完e,a,aa,…,mk分别到达状态sp,s1,…,Sk 至少有两个状态相同,例如是s和s,则ab属于 3 标记为d-的路径 标记为ai的路径 标记为b的路径 ●●3.2 语言和文法 • L3  ={a nb n | n  1} S → aSb | ab • L3 是不能用正规式描述的语言的一个范例 – 若存在接受L3 的DFA D，状态数为k个 – 设D读完, a, aa, …, a k 分别到达状态s0 , s1 , …, sk –至少有两个状态相同，例如是si和sj，则a jb i属于 L3  si … f s0 标记为a i的路径 标记为b i的路径 标记为a j − i的路径 … …