컨텍스트가 없습니다. 문법은 다음과 같습니다.

A → a | 의 | a A b | b A b | b A a B → b | a B a | a B b | b B b | b B aS→A|B|AB|BA

$S\to A|B|AB|BA$

$S \to A | B|AB|BA$

A→a|aAa|aAb|bAb|bAa

$A\to a|aAa|aAb|bAb|bAa$

$A \to a|aAa|aAb|bAb|bAa$

B→b|aBa|aBb|bBb|bBa

$B\to b|aBa|aBb|bBb|bBa$

$B \to b|aBa|aBb|bBb|bBa$

경우 → B의 BA

$A$

$A$ 로 홀수 길이의 단어를 생성 중심이다. 와 동일합니다 .a

$a$

$a$B

$B$

$B$b

$b$

$b$

이 문법이 정확하다는 증거를 제시하겠습니다. 하자 (질문의 언어).L={a,b}∗∖{ww∣w∈{a,b}∗}

$L=\{a,b{\}}^{\ast }\setminus \{ww\mid w\in \{a,b{\}}^{\ast }\}$

$L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$

정리. 입니다. 즉,이 문법은 문제의 언어를 생성합니다.L=L(S)

$L=L(S)$

$L = L(S)$

증명. 이 문법은 처럼 모든 홀수 길이의 단어를 생성하기 때문에 이것은 확실히 모든 홀수 길이의 단어에 적용됩니다 . 따라서 짝수 단어에 초점을 맞추겠습니다.L

$L$

$L$

길이가 짝수 라고 가정하십시오 . 보여 드리겠습니다 . 특히, 는 형식으로 쓸 수 있다고 주장합니다 . 여기서 와 는 길이가 홀수이고 다른 중심 문자가 있습니다. 따라서 는 또는 에서 파생 될 수 있습니다 ( 의 중심 문자가 인지 인지에 따라 ). 제의 정당성 : 송출 의 번째 문자 표시 될 되도록, . 그런 다음 부터x ∈ L ( G ) x x = u v u v x A B B A u a b i x x i x = x 1 x 2 ⋯ x n x { w w ∣ w ∈ { a , b } n / 2 } i x i ≠ x i + nx∈L

$x\in L$

$x \in L$x∈L(G)

$x\in L(G)$

$x \in L(G)$x

$x$

$x$x=uv

$x=uv$

$x=uv$u

$u$

$u$v

$v$

$v$x

$x$

$x$AB

$AB$

$AB$BA

$BA$

$BA$u

$u$

$u$a

$a$

$a$b

$b$

$b$i

$i$

$i$x

$x$

$x$xi

$x_i$

$x_i$x=x1x2⋯xn

$x=x_1{x}_2\cdots x_n$

$x = x_1 x_2 \cdots x_n$x

$x$

$x$아닌 일부 인덱스가 존재해야 되도록 . 결과적으로 우리는 및 취할 수 있습니다 . 중앙 문자 것이다 , 그리고 중앙 문자 것 때문에 공사에 의해 가 다른 중앙 편지.{ww∣w∈{a,b}n/2}

$\{ww\mid w\in \{a,b{\}}^{n/2}\}$

$\{ww \mid w \in \{a,b\}^{n/2}\}$i

$i$

$i$ u=x1⋯x 2 i − 1 v=x 2 i ⋯xnuxivx i + n / 2 u,vxi≠xi+n/2

$x_i\ne x_{i+n/2}$

$x_i \ne x_{i+n/2}$u=x1⋯x2i−1

$u=x_1\cdots x_{2i-1}$

$u = x_1 \cdots x_{2i-1}$v=x2i⋯xn

$v=x_{2i}\cdots x_n$

$v = x_{2i} \cdots x_n$u

$u$

$u$xi

$x_i$

$x_i$v

$v$

$v$xi+n/2

$x_{i+n/2}$

$x_{i+n/2}$u,v

$u,v$

$u,v$

다음으로 길이가 같다고 가정하자 . 이 있어야 함을 보여줄 것입니다 . 길이가 짝수 이면 또는 에서 파생 될 수 있어야합니다 . 일반성을 잃지 않고 에서 파생 되고 여기서 는 에서 파생 되고 는 에서 파생 될 수 있다고 가정합니다 . 만약 의 길이가 같으면, 우리는 (중앙 문자가 다르기 때문에)를 가져야합니다. 그래서 . 그래서 가정x ∈ L x A B B A A B x = u v u A v B u , v u ≠ v x ∉ { w w ∣ w ∈ { a , b } ∗ } u , v ℓ n − ℓ u ( ℓ + 1 ) / 2 vx∈L(G)

$x\in L(G)$

$x \in L(G)$x∈L

$x\in L$

$x \in L$x

$x$

$x$AB

$AB$

$AB$BA

$BA$

$BA$AB

$AB$

$AB$x=uv

$x=uv$

$x=uv$u

$u$

$u$A

$A$

$A$v

$v$

$v$B

$B$

$B$u,v

$u,v$

$u,v$u≠v

$u\ne v$

$u\ne v$x∉{ww∣w∈{a,b}∗}

$x\notin \{ww\mid w\in \{a,b{\}}^{\ast }\}$

$x \notin \{ww \mid w \in \{a,b\}^*\}$u,v

$u,v$

$u,v$길이 과 과 같이 길이가 다릅니다 . 그런 다음 중심 문자는 및 입니다. 중심 문자가 다르다는 사실은 입니다. 이후 이 의미 . 를 로 분해하려고하면 , 의 길이가 같으면 임을 알게됩니다 즉, 이므로ℓ

$\ell$

$\ell$n−ℓ

$n-\ell$

$n-\ell$u(ℓ+1)/2

$u_{(\ell +1)/2}$

$u_{(\ell+1)/2}$ u,v u ( ℓ + 1 ) / 2 ≠ v ( n − ℓ + 1 ) / 2 x=uv x ( ℓ + 1 ) / 2 ≠ x ( n + ℓ + 1 ) / 2 xx=w w ′ wv(n−ℓ+1)/2

$v_{(n-\ell +1)/2}$

$v_{(n-\ell+1)/2}$u,v

$u,v$

$u,v$u(ℓ+1)/2≠v(n−ℓ+1)/2

$u_{(\ell +1)/2}\ne v_{(n-\ell +1)/2}$

$u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$x=uv

$x=uv$

$x=uv$x(ℓ+1)/2≠x(n+ℓ+1)/2

$x_{(\ell +1)/2}\ne x_{(n+\ell +1)/2}$

$x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$x

$x$

$x$x=ww′

$x=w{w}^{\prime }$

$x=ww'$w ( ℓ + 1 ) / 2 = x ( ℓ + 1 ) / 2 ≠ x ( n + ℓ + 1 ) / 2 = w ′ ( ℓ + 1 ) / 2 w ≠ w ′ x ∉ { w w ∣ w ∈ { a , b } ∗ } xw,w′

$w,w^{\prime }$

$w,w'$w(ℓ+1)/2=x(ℓ+1)/2≠x(n+ℓ+1)/2=w′(ℓ+1)/2

$w_{(\ell +1)/2}=x_{(\ell +1)/2}\ne x_{(n+\ell +1)/2}=w_{(\ell +1)/2}^{\prime }$

$w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$w≠w′

$w\ne w^{\prime }$

$w\ne w'$x∉{ww∣w∈{a,b}∗}

$x\notin \{ww\mid w\in \{a,b{\}}^{\ast }\}$

$x \notin \{ww \mid w \in \{a,b\}^*\}$ . 특히, 옵니다 .x∈L

$x\in L$

$x \in L$

---

답변