Префикс строки

Question

X - префикс строки y, если существует xz = y, а x - собственный префикс , если x не равен y.

Просто хотел убедиться, что я правильно понял концепцию.

Например, если существует строка y = "abracadabra", это означает, что существует множество возможных префиксов? Итак, если x является префиксом, то x может быть равно «a», «ab», «abr» или даже «abracadabra», но в этом случае, когда x = y, он теперь называется не правильным префиксом, как насколько я понимаю. Тем не менее, я не уверен в последней части, где x = y можно ли считать ее префиксом?

Язык не имеет префикса, если ни один из них не является надлежащим префиксом другого члена .

Опять же, не уверен, правильно ли я это понимаю. Если, например, существует язык = «Привет, мир! Меня зовут Андрей», я думаю, он не имеет префиксов, поскольку начало каждого члена отличается друг от друга. Однако, если у нас есть «Привет, мир! Как дела?» этот язык больше не является префиксным, поскольку «H» является префиксом как «Hello», так и «How». Правильно ли мой образ мышления или я что-то не понял?

Нет примеров, приведенных в книге, которую я читаю, и это кажется легкой темой, поэтому я думаю, что это может быть причиной того, что я не могу найти более подробные объяснения. Но я просто, во всяком случае, хочу убедиться, что я ничего не понимаю.

Буду признателен всем за ответы. Спасибо.

Answer 1

Да, «абракадабра» - это префикс «абракадабры», но не правильный - «а», «аб», «абр», ..., «абракадабр» являются правильными префиксами «абракадабры», , Ваш пример для языка немного запутан. Обычно язык определяется как набор слов/строк, но вы даете только одну большую строку в качестве примера языка.

Таким образом, языком может быть множество L1 = {"a", "b", "ab"}. Однако этот язык не префикс-свободный, так как «a» находится в L1 и является надлежащим префиксом «ab», который также находится в L1.

Язык L2 = {"abra", "cada", "bra"} является примером языка без префикса в соответствии с определением, которое вы указали: «abra» не является префиксом «cada» или «bra», «cada» не является префиксом, если «abra» или «bra», а «bra» не является префиксом «abra» или «cada».