Bukti NOTPAL bukan bahasa reguler yang licik

Misalkan NOTPAL = \{w \in \{a,b\}^*: w \ne w^R \} yaitu bahasa yang berisi semua string yang bukan palindrom. Jika boleh menggunakan closure theorem, tidak sulit untuk membuktikan bahwa bahasa ini bukan bahasa reguler.

Perhatikan bahwa kita cukup membuktikan bahwa bahasa PAL=\{ w \in \{a,b\}^*: w = w^R\} bukan bahasa reguler. Dengan teorema Pumping, kita bisa pilih w=a^kba^k. Semua kemungkinan kasus x,y,z dengan w=xyz,|xy| \le k,|y| \ge 1 adalah x=a^m,y=a^n,z=a^{k-m-n}ba^k. Dari sini, diperoleh xy^{\ell}z=a^{k+(\ell-1)n}ba^k. Tentunya dapat dipilih \ell=2, dan pastilah a^{k+n}ba^k \notin L.

Namun, string w apakah yang sebaiknya dipilih untuk menunjukkan bahwa NOTPAL bukan bahasa reguler? Apakah bisa menggunakan Teorema Pumping?

Jawabannya adalah bisa.

String yang dipilih adalah w=a^kba^{k+k!} yang jelas bukan palindrom. Hasil pumpingnya akan berbentuk xy^{\ell}z=a^{k+(\ell-1)n}ba^{k+k!} dengan |y|=n yang tidak kita ketahui, namun bisa bernilai n=1,2,\dots,k. Kita ingin memilih \ell \ge 0 sehingga xy^{\ell}z palindrom, yaitu

k+(\ell-1)n=k+k!.

Namun, ini jelas bisa terjadi karena untuk n=1,2,\dots,k, nilai \ell = \dfrac{k!}{n}+1 merupakan bilangan asli. Jadi, pasti dapat dipilih \ell agar xy^{\ell}z palindrom kembali.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s