Car*_*ine 1 theory string prefix computation-theory
如果存在xz = y,则X是字符串y的前缀,如果x不等于y,则x是正确的前缀.
只是想确保我正确理解这个概念.
例如,如果有一个字符串y ="abracadabra"是否意味着有大量可能的前缀？因此,如果x是前缀,则x可以等于"a","ab","abr"或甚至"abracadabra",但在这种情况下,当x = y时,它现在被称为不正确的前缀我认为.但是,我不确定x = y的最后一部分是否仍然可以被认为是前缀？
如果没有成员是另一个成员的正确前缀,则语言是无前缀的.
再次,不确定我是否正确理解它.例如,如果有一种语言="你好,世界!我的名字是安德鲁",我想,它是无前缀的,因为每个成员的开头都是彼此不同的.但是,如果我们有"你好,世界!你好吗？" 这种语言不再是无前缀的,因为"H"是"Hello"和"How"的前缀.我的思维方式是正确的还是我误解了什么？
我正在阅读的书中没有给出示例,这似乎是一个简单的话题,所以我想这可能是我找不到更详细解释的原因.但无论如何,我只是想确保我不会误解任何事情.
我会很感激所有的答案.谢谢.
小智 5
是的,"abracadabra"是"abracadabra"的前缀,但不是正确的 - "a","ab","abr",......,"abracadabr"是"abracadabra"的正确前缀.你的语言示例有点令人困惑.通常,语言被定义为一组单词/字符串,但您只提供一个大字符串作为语言示例.
因此,语言可能是集合L1 = {"a","b","ab"}.但是,这种语言不是无前缀的,因为"a"在L1中并且是"ab"的正确前缀,它也在L1中.
语言L2 = {"abra","cada","bra"}是根据您给出的定义的无前缀语言的示例:"abra"不是"cada"或"bra"的前缀,如果"abra"或"bra",则"cada"不是前缀,而"bra"不是"abra"或"cada"的前缀.
| 归档时间： |
|
| 查看次数： |
9973 次 |
| 最近记录： |