Ры­ца­ри, ко­то­рые го­во­рят толь­ко прав­ду, и лжецы, ко­то­рые все­гда лгут, вы­стро­и­лись в ряд. (В ряду хотя бы один че­ло­век).Каж­дый из них про­изнёс фразу «Все мои со­се­ди лжецы». Обо­зна­чим ры­ца­ря бук­вой Р, а лжеца  — бук­вой Л. Тогда каж­дой по­сле­до­ва­тель­но­сти ры­ца­рей и лже­цов, для ко­то­рой вы­пол­ня­ет­ся усло­вие за­да­чи, со­от­вет­ству­ет не­ко­то­рое слово.

Опи­ши­те это слово, ис­поль­зуя фор­му­лу, ко­то­рая на­зы­ва­ет­ся ре­гу­ляр­ным вы­ра­же­ни­ем. Такое вы­ра­же­ние стро­ит­ся с по­мо­щью опи­сы­ва­е­мых ниже опе­ра­ций «ите­ра­ция», «умно­же­ние», «сло­же­ние».

Так для по­вто­ре­ния блока из не­сколь­ких букв ис­поль­зуй­те опе­ра­цию «звез­доч­ка» (ите­ра­ция), на­при­мер, (abb)* за­да­ет мно­же­ство слов {пу­стое слово, abb, abbabb, abbabbabb, …}. Умно­же­ние мно­жеств (эту опе­ра­цию, как обыч­но в ал­геб­ре, изоб­ра­жа­ют точ­кой при­пи­сы­ва­ни­ем вто­ро­го опе­ран­да вслед за пер­вым, что мы и будем де­лать), опи­сы­ва­ет склей­ку всех слов пер­во­го мно­же­ства со сло­ва­ми вто­ро­го (тре­тье­го и т. д.), на­при­мер a*cb* обо­зна­ча­ет мно­же­ство слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Об­ра­ти­те вни­ма­ние что слова, в ко­то­рых нет букв a или b, по­лу­ча­ют­ся за счет того, что ре­зуль­тат ите­ра­ции может не со­дер­жать сим­во­лов, то есть быть пу­стым сло­вом.

По­след­ней опе­ра­ци­ей, ко­то­рая ис­поль­зу­ет­ся в фор­му­лах, яв­ля­ет­ся сло­же­ние. Сло­же­ние со­от­вет­ству­ет объ­еди­не­нию мно­жеств. Так, обо­зна­че­ние (a + b)*c + d(ac* + ) опи­сы­ва­ет мно­же­ство всех по­сле­до­ва­тель­но­стей из букв a и b (обо­зна­ча­ет­ся (a + +b)*), к концу ко­то­рых при­со­еди­не­на буква c, объ­еди­нен­но­го с мно­же­ством слов, на­чи­на­ю­щих­ся с буквы d, за ко­то­рой сле­ду­ет буква a, а за ней любое число букв c и ещё одним од­но­бук­вен­ным сло­вом (d умно­жить на пу­стое слово  — это d).