【形式语言与自动机】【《形式语言与自动机理论(第4版)》笔记】第五章:正则语言的性质

2023-12-14 14:43:48

5.1|正则语言的泵引理

鸽巢原理现象
  • L L L是一个 R L RL RL D F A ? M = ( Q , Σ , δ , q 0 , F ) DFA \ M = (Q , \Sigma , \delta , q_{0} , F) DFA?M=(Q,Σ,δ,q0?,F),满足 L ( M ) = L L(M) = L L(M)=L ∣ Q ∣ = N |Q| = N Q=N,不失一般性,不妨假设 Q Q Q中不含任何不可达状态
  • L L L的句子 z = a 1 a 2 ? a m ( m ≥ N ) z = a_{1} a_{2} \cdots a_{m} (m \geq N) z=a1?a2??am?(mN),对 ? h \forall h ?h 1 ≤ h ≤ m 1 \leq h \leq m 1hm,令 δ ( q 0 , a 1 a 2 ? a h ) = q h \delta(q_{0} , a_{1} a_{2} \cdots a_{h}) = q_{h} δ(q0?,a1?a2??ah?)=qh?
  • 由于 m ≥ N m \geq N mN,所以在状态序列 q 0 , q 1 , ? ? , q N q_{0} , q_{1} , \cdots , q_{N} q0?,q1?,?,qN?中至少有两个状态是相同的,不妨假设 q k q_{k} qk? q j q_{j} qj?是该状态序列中最早出现的相同状态,显然 k < j ≤ N k < j \leq N k<jN
  • 此时有

δ ( q 0 , a 1 a 2 ? a k ) = q k δ ( q k , a k + 1 ? a j ) = q j = q k δ ( q j , a j + 1 ? a m ) = q m \begin{aligned} \delta(q_{0} , a_{1} a_{2} \cdots a_{k}) &= q_{k} \\ \delta(q_{k} , a_{k + 1} \cdots a_{j}) &= q_{j} = q_{k} \\ \delta(q_{j} , a_{j + 1} \cdots a_{m}) &= q_{m} \end{aligned} δ(q0?,a1?a2??ak?)δ(qk?,ak+1??aj?)δ(qj?,aj+1??am?)?=qk?=qj?=qk?=qm??

  • 注意到 q j = q k q_{j} = q_{k} qj?=qk?,所以对于任意整数 i ≥ 0 i \geq 0 i0

δ ( q k , ( a k + 1 ? a j ) i ) = δ ( q k , ( a k + 1 ? a j ) i ? 1 ) ? = δ ( q k , a k + 1 ? a j ) = q k \begin{aligned} \delta(q_{k} , (a_{k+1} \cdots a_{j})^{i}) &= \delta(q_{k} , (a_{k+1} \cdots a_{j})^{i - 1}) \\& \cdots \\ &= \delta(q_{k} , a_{k+1} \cdots a_{j}) \\ &= q_{k} \end{aligned} δ(qk?,(ak+1??aj?)i)?=δ(qk?,(ak+1??aj?)i?1)?=δ(qk?,ak+1??aj?)=qk??

  • 因为 z ∈ L ( M ) z \in L(M) zL(M),所以 q m ∈ F q_{m} \in F qm?F,故对于任意整数 i ≥ 0 i \geq 0 i0 δ ( q 0 , a 1 a 2 ? a k ( a k + 1 ? a j ) i a j + 1 ? a m ) = q m \delta(q_{0} , a_{1} a_{2} \cdots a_{k} (a_{k + 1} \cdots a_{j})^{i} a_{j + 1} \cdots a_{m}) = q_{m} δ(q0?,a1?a2??ak?(ak+1??aj?)iaj+1??am?)=qm?,也就是说 a 1 a 2 ? a k ( a k + 1 ? a j ) i a j + 1 ? a m ∈ L ( M ) a_{1} a_{2} \cdots a_{k} (a_{k + 1} \cdots a_{j})^{i} a_{j + 1} \cdots a_{m} \in L(M) a1?a2??ak?(ak+1??aj?)iaj+1??am?L(M)

u = a 1 a 2 ? a k v = a k + 1 ? a j w = a j + 1 ? a m \begin{aligned} u &= a_{1} a_{2} \cdots a_{k} \\ v &= a_{k + 1} \cdots a_{j} \\ w &= a_{j + 1} \cdots a_{m} \end{aligned} uvw?=a1?a2??ak?=ak+1??aj?=aj+1??am??

  • 对于任意整数 i ≥ 0 i \geq 0 i0 u v i w ∈ L u v^{i} w \in L uviwL,注意到 k < j ≤ N k < j \leq N k<jN,所以 u u u v v v满足

∣ u v ∣ ≤ N ∣ v ∣ ≥ 1 |uv| \leq N \\ |v| \geq 1 uvNv1

正则语言的泵引理
  • L L L为一个 R L RL RL,则存在仅依赖于 L L L的正整数 N N N,对于 ? z ∈ L \forall z \in L ?zL,如果 ∣ z ∣ ≥ N |z| \geq N zN,则存在 u u u v v v w w w满足:
    • z = u v w z = uvw z=uvw
    • ∣ u v ∣ ≤ N |uv| \leq N uvN
    • ∣ v ∣ ≥ 1 |v| \geq 1 v1
    • 对于任意整数 i ≥ 0 i \geq 0 i0 u v i w ∈ L u v^{i} w \in L uviwL
    • N N N不大于接受 L L L的最小 D F A ? M DFA \ M DFA?M的状态数
  • 泵引理给出的是 R L RL RL的“必要条件”而不是“充分条件”
应用
问题 1 1 1
  • 证明 { ? 0 n 1 n ∣ n ≥ 1 ? } \set{0^{n} 1^{n} \mid n \geq 1} {0n1nn1}不是 R L RL RL
解答 1 1 1
  • L = { ? 0 n 1 n ∣ n ≥ 1 ? } L = \set{0^{n} 1^{n} \mid n \geq 1} L={0n1nn1},假设 L L L R L RL RL,则它满足泵引理,不妨设 N N N是泵引理所指的仅依赖于 L L L的正整数
  • z = 0 N 1 N z = 0^{N} 1^{N} z=0N1N,显然 z ∈ L z \in L zL,按照泵引理所述,必存在 u u u v v v w w w,由于 ∣ u v ∣ ≤ N |uv| \leq N uvN,并且 ∣ v ∣ ≥ 1 |v| \geq 1 v1,所以 v v v只可能是由 0 0 0组成的非空串
  • 不妨设

v = 0 k , k ≥ 1 v = 0^{k} , k \geq 1 v=0k,k1

  • 此时有

u = 0 N ? k ? j w = 0 j 1 N \begin{aligned} u &= 0^{N - k - j} \\ w &= 0^{j} 1^{N} \end{aligned} uw?=0N?k?j=0j1N?

  • 从而有 u v i w = 0 N ? k ? j ( 0 k ) i 0 j 1 N = 0 N + ( i ? 1 ) k 1 N u v^{i} w = 0^{N - k - j} (0^{k})^{i} 0^{j} 1^{N} = 0^{N + (i - 1) k} 1^{N} uviw=0N?k?j(0k)i0j1N=0N+(i?1)k1N
  • i = 2 i = 2 i=2时,有 u v 2 w = 0 N + ( 2 ? 1 ) k 1 N = 0 N + k 1 N ? L u v^{2} w = 0^{N + (2 - 1) k} 1^{N} = 0^{N + k} 1^{N} \notin L uv2w=0N+(2?1)k1N=0N+k1N/L,与泵引理矛盾,所以 L L L不是 R L RL RL
问题 2 2 2
  • 证明 { ? 0 n ∣ n 为素数 ? } \set{0^{n} \mid n 为素数} {0nn为素数}不是 R L RL RL
解答 2 2 2
  • L = { ? 0 n ∣ n 为素数 ? } L = \set{0^{n} \mid n 为素数} L={0nn为素数},假设 L L L R L RL RL,则它满足泵引理,不妨设 N N N是泵引理所指的仅依赖于 L L L的正整数
  • z = 0 N + p z = 0^{N + p} z=0N+p,其中 N + p N + p N+p是素数,即 z ∈ L z \in L zL,按照泵引理所述,必存在 u u u v v v w w w,由于 ∣ v ∣ ≥ 1 |v| \geq 1 v1,所以 v v v必定是由 0 0 0组成的非空串
  • 不妨设

v = 0 k , k ≥ 1 v = 0^{k} , k \geq 1 v=0k,k1

  • 此时有

u = 0 N + p ? k ? j w = 0 j \begin{aligned} u &= 0^{N + p - k - j} \\ w &= 0^{j} \end{aligned} uw?=0N+p?k?j=0j?

  • 从而有 u v i w = 0 N + P ? k ? j ( 0 k ) i 0 j = 0 N + p + ( i ? 1 ) k u v^{i} w = 0^{N + P - k - j} (0^{k})^{i} 0^{j} = 0^{N + p + (i - 1) k} uviw=0N+P?k?j(0k)i0j=0N+p+(i?1)k
  • i = N + p + 1 i = N + p + 1 i=N+p+1时, u v N + p + 1 w = 0 ( N + p ) ( 1 + k ) ? L u v^{N + p + 1} w = 0^{(N + p)(1 + k)} \notin L uvN+p+1w=0(N+p)(1+k)/L,与泵引理矛盾,所以 L L L不是 R L RL RL

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/134993517
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。