【形式语言与自动机】【《形式语言与自动机理论（第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?(m≥N)，对 ? h \forall h ?h， 1 ≤ h ≤ m 1 \leq h \leq m 1≤h≤m，令 δ ( 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 m≥N，所以在状态序列 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<j≤N
  • 此时有

δ ( 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 i≥0

δ ( 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) z∈L(M)，所以 q m ∈ F q_{m} \in F qm?∈F，故对于任意整数 i ≥ 0 i \geq 0 i≥0， δ ( 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 i≥0， u v i w ∈ L u v^{i} w \in L uviw∈L，注意到 k < j ≤ N k < j \leq N k<j≤N，所以 u u u， v v v满足

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

正则语言的泵引理
  • 设 L L L为一个 R L RL RL，则存在仅依赖于 L L L的正整数 N N N，对于 ? z ∈ L \forall z \in L ?z∈L，如果 ∣ z ∣ ≥ N |z| \geq N ∣z∣≥N，则存在 u u u， v v v， w w w满足：
    • z = u v w z = uvw z=uvw
    • ∣ u v ∣ ≤ N |uv| \leq N ∣uv∣≤N
    • ∣ v ∣ ≥ 1 |v| \geq 1 ∣v∣≥1
    • 对于任意整数 i ≥ 0 i \geq 0 i≥0， u v i w ∈ L u v^{i} w \in L uviw∈L
    • 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} {0n1n∣n≥1}不是 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={0n1n∣n≥1}，假设 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 z∈L，按照泵引理所述，必存在 u u u， v v v， w w w，由于 ∣ u v ∣ ≤ N |uv| \leq N ∣uv∣≤N，并且 ∣ v ∣ ≥ 1 |v| \geq 1 ∣v∣≥1，所以 v v v只可能是由 0 0 0组成的非空串
  • 不妨设

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

  • 此时有

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 为素数} {0n∣n为素数}不是 R L RL RL
解答 2 2 2
  • 设 L = { ? 0 n ∣ n 为素数 ? } L = \set{0^{n} \mid n 为素数} L={0n∣n为素数}，假设 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 z∈L，按照泵引理所述，必存在 u u u， v v v， w w w，由于 ∣ v ∣ ≥ 1 |v| \geq 1 ∣v∣≥1，所以 v v v必定是由 0 0 0组成的非空串
  • 不妨设

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

  • 此时有

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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。