交換補題

形式言語の理論では、交換補題は、文脈自由言語のポンピング補題と同様に、言語が文脈自由であるための必要条件を述べています。

これは、すべての文脈自由言語に対して、すべてに対してとなる が存在し、任意の長さの単語の集合に対して、となる が存在し、分解が存在して、 、、のそれぞれがから独立し、さらに、 であり、すべてのおよびに対して単語が に含まれることを述べています。 ${\displaystyle L}$${\displaystyle c>0}$${\displaystyle n\geq m\geq 2}$${\displaystyle n}$${\displaystyle R\subset L}$${\displaystyle Z=\{z_{1},\ldots ,z_{k}\}\subset R}$${\displaystyle k\geq |R|/(cn^{2})}$${\displaystyle z_{i}=w_{i}x_{i}y_{i}}$${\displaystyle |w_{i}|}$${\displaystyle |x_{i}|}$${\displaystyle |y_{i}|}$${\displaystyle i}$${\displaystyle m/2<|x_{i}|\leq m}$${\displaystyle w_{i}x_{j}y_{i}}$${\displaystyle L}$${\displaystyle i}$${\displaystyle j}$

交換補題の最初の応用は、3 文字以上のアルファベット上の反復文字列 (つまり、 という形式の文字列)の集合が文脈自由ではないことを示すことでした。 ${\displaystyle xyyz}$${\displaystyle |y|>0}$

• 正規言語のポンピング補題

• William Ogden、 Rockford J. Ross、Karl Winklmann (1982)。「文脈自由言語のための「交換補題」」。SIAM Journal on Computing。14 ( 2): 410–415。doi :10.1137 / 0214031。{{cite journal}}: CS1 maint: multiple names: authors list (link)