Palindrom: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
|||
| (22 revisi perantara oleh 10 pengguna tidak ditampilkan) | |||
Baris 1:
'''Palindrom''' merupakan sebuah kata, [[bilangan palindromik|bilangan]], frasa, atau susunan [[karakter (simbol)|karakter]] lain yang serupa jika dibaca dengan urutan terbalik ataupun tidak, seperti dalam ''kakak'' ataupun ''apa''. Selain itu, terdapat juga bilangan palindrom yang dapat dibaca dengan cara serupa. Sebagai contoh, susunan waktu dan tanggal tertentu seperti ''11/11/11 11:11'' ataupun [[Twosday|Selasa, 22 Februari 2022]] tergolong sebagai hari palindrom (dengan format hh-bb-tttt), karena dapat dibaca dari kiri ke kanan ataupun sebaliknya. Unsur penulisan seperti kapitalisasi, tanda baca, dan batas kata tidak diperhatikan dalam palindrom yang memiliki panjang setara dengan sebuah kalimat.
[[File:Ambigram_palindrome_ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ_(Wash_your_sins,_not_only_your_face,_in_Greek).jpg|thumb|200px|Palindrom [[Nipson anomemata me monan opsin|ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ]] {{lang-id|Basuhlah dosamu, tidak hanya di mukamu saja}} yang ditulis dalam fon air suci Bahasa Yunani.]]
Menulis karya sastra dalam bentuk palindrom adalah contoh dari [[tulisan cangkupan terbatas]].
Istilah ''palidrom'' pertama kali diperkenalkan oleh [[Henry Peacham (lahir 1578)|Henry Peacham]] pada 1638.<ref>Henry Peacham, ''The Truth of our Times Revealed out of One Mans Experience'', 1638, [https://quod.lib.umich.edu/cgi/t/text/pageviewer-idx?cc=eebo;c=eebo;idno=a09207.0001.001;node=A09207.0001.001:5;seq=134;submit=Go;type=simple;vid=14563;q1=palindrome;page=root;view=text hlm. 123]</ref> Kata tersebut berasal dari akar kata {{lang|grc|πάλιν}} 'palin' dalam bahasa Yunani yang berarti "lagi" dan {{lang|grc|δρóμος}} 'dromos' yang berarti "arah". Sementara itu, καρκινικός 'karsinik' ({{abbr|har.|secara harfiah berarti}} ''mirip-kepiting'') juga menjadi sebutan lain untuk gaya penulisan huruf per huruf yang menghasilkan sebuah kata ataupun kalimat yang dapat dibaca secara terbalik ataupun tidak.<ref>{{Cite web|url=http://www.greek-language.gr/greekLang/modern_greek/tools/lexica/search.html?lq=%CE%BA%CE%B1%CF%81%CE%BA%CE%B9%CE%BD%CE%B9%CE%BA%CF%8C%CF%82&dq=|title=Combined word search for καρκινικός|last=Triantaphylides Dictionary|first=Portal for the Greek Language|website=www.greek-language.gr|access-date=6 May 2019}}</ref><ref>[[William Martin Leake]], ''Researches in Greece'', 1814, hlm. 85</ref>
== Teori komputasi ==
Dalam [[teori automata]], suatu [[himpunan (matematika)|himpunan]] dari semua palindrom dalam komposisi [[alfabet]] yang dimasukkan bukan merupakan komponen [[bahasa reguler]], melainkan sebuah contoh tipikal dari [[bahasa formal|formal]] yang memiliki [[bahasa konteks bebas|konteks bebas]]. Hal ini berarti, mustahil bagi sebuah komputer atau mesin komputasi lainnya dengan [[automaton terhingga|kapasitas memori terbatas]] dapat melakukan palindrom dengan benar. <!-- (Must say "on one pass" because, if it were allowed random access to the data, the test becomes trivial: simply check data[n] == data[L-n] for all n up to L/2 where L is the length.) --><!-- The preceding comment does not take into account that if the memory (including registers) is only M bits, the computer can only represent these values of n from 0 to 2^M-1, so consider the problem when L >= 2^M. --> <!--(For practical purposes with modern computers, this limitation would apply only to impractically long letter-sequences.)-->
Selain itu, kemampuan komputasinya diperparah dengan kemungkinan bahwa palindrom tidak dites penggunaannya oleh ''[[deterministic pushdown automaton]]'', yang berarti mereka tidak termasuk dalam golongan fungsi parser [[LR parser|LR(k)]] atau [[LL parser|LL(k)]] yang dapat dkparserkan. Saat palindrom dibaca dari kiri ke kanan, secara esensial mustahil untuk menentukan lokasi "pusat" hingga seluruh kata atau kalimat dibaca utuh.
Akan tetapi, [[substring palindromik terpanjang]] dari input yang dimasukman masih mungkin ditemukan dengan metode [[waktu linear]].<ref name=Jewels>{{citation
| last1 = Crochemore
| first1 = Maxime
| last2 = Rytter
| first2 = Wojciech
| author2-link = Wojciech Rytter
| title = Jewels of Stringology: Text Algorithms
| title-link = Jewels of Stringology
| publisher = World Scientific
| year = 2003
| isbn = 978-981-02-4897-0
| contribution = 8.1 Searching for symmetric words
| pages = 111–114
}}</ref><ref>{{citation
| last = Gusfield
| first = Dan
| contribution = 9.2 Finding all maximal palindromes in linear time
| doi = 10.1017/CBO9780511574931
| isbn = 978-0-521-58519-4
| location = Cambridge
| mr = 1460730
| pages = 197–199
| publisher = Cambridge University Press
| title = Algorithms on Strings, Trees, and Sequences
| year = 1997
}}</ref>
'''Kepadatan palindromik''' dari suatu kata tak terhingga ''w'' atas alfabet ''A'' memiliki nilai yang didefinisikan sebagai nol jika awalan berupa palindrom dan memiliki jumlah terhingga, jika tidak, misalkan awalan palindromik dapat melebar hingga sepanjang {{Math|''n''<sub>''k''</sub>}} untuk {{Math|1=''k'' = 1, 2, ...}}'','' maka penentuan nilai kepadatan didefinisikan sebagai
:<math> d_P(w) = \left( { \limsup_{k \rightarrow \infty} \frac{n_{k+1}}{n_k} } \right)^{-1} \ . </math>
Diantara banyak kata aperiodik yang sudah ditemukan, [[kata Fibonacci]] memiliki kepadatan paling besar, yaitu sebesar {{math|{{sfrac|1=1|2=''φ''}}}}, dengan {{Math|''φ''}} melambangkan [[rasio emas]]. <ref name=AB443>{{citation
| last1 = Adamczewski
| first1 = Boris
| last2 = Bugeaud
| first2 = Yann
| chapter = 8. Transcendence and diophantine approximation
| editor1-last = Berthé
| editor1-link = Valérie Berthé
| editor1-first = Valérie
| editor2-last = Rigo
| editor2-first = Michael
| title = Combinatorics, automata, and number theory
| location = Cambridge
| publisher = [[Cambridge University Press]]
| series = Encyclopedia of Mathematics and its Applications
| volume = 135
| page = 443
| year = 2010
| isbn = 978-0-521-51597-9
| zbl = 1271.11073
}}</ref>
'''Palstar''' adalah [[gabungan]] dari sejumlah string palindrom, dan harus memiliki komposisi palindrom yang bukan terdiri dari satu huruf saja, jika tidak, semua string akan menjadi bentuk palstar.<ref name=Jewels />
== Lihat pula ==
Baris 33 ⟶ 75:
== Pranala luar ==
* {{id}}{{en}}[
[[kategori:Palindrom]]
[[Kategori:Permainan kata]]
| |||