可以使用上下文无关语法描述char数的语言吗？

我正在查看德国的HBCI/FinTS协议。该协议的一个特点是它可以包含二进制斑点，前缀为@[email protected]。否则，该协议是很简单的，语法可以被描述如下（有点简化，端子通过引述“）：可以使用上下文无关语法描述char数的语言吗？

message = segment+ 
segment = elements "'" 
elements = element "+" elements | element 
element = items 
items = item ":" items | item 
item  = [a-zA-Z0-9,._-]* | escaped item 
escaped = ?[[email protected]?_-a-zA-Z0-9,.] 

The @ is missing here!

样品消息可能看起来像这样

FirstSegment+Elem1+Item1:[email protected]@:'[email protected]+The_last_four_chars_are_binary+Elem4'SecondSegment+Elem5'

可以这样语言（二进制字符串的转义）由上下文无关文法来描述？

来源

2014-01-08 Paul

这个问题似乎是题外话，因为它是关于计算机科学理论而不是一个特定的编程问题。它已被问及并在http://cstheory.stackexchange.com/questions/9645/can-bencodes-be-described-with-a-context-free-grammar/9663#9663 –

@ A.Webb回答谢谢你单挑。我不确定，因为1）我在编程环境中需要这样的内容，2）关于SO的CFG有很多问题。下次会检查CSTheorySE。 – Paul

不，这语言不是上下文无关的。你所描述的格式基本上等同于这种语言

{@ n @ w | n是自然数并且| w | = n}

通过使用无上下文抽象引理可以证明这不是上下文无关的。假设抽吸长度为p并考虑字符串@^{@^{1111 ... 1（p次）}。这是显示长度为111 ... 1（p次）的二进制数据段的字符串编码。现在将字符串拆分为u，v，x，y，z，其中| vy | > 1和| vxy | ≤ p。如果v或y是@符号，那么z不在语言中，因为它没有足够的@符号。如果v和y纯粹包含在1 ^p中，那么抽取字符串将最终生成一个不在该语言中的字符串，因为二进制数据字符串的大小不合适。类似地，如果v和y纯粹包含在x中，那么111或1（p次）}，向上或向下泵送将使有效载荷大小错误。最后，如果v在长度字段中并且x在有效载荷中，则同时向上泵送v和x将使得有效载荷具有错误的长度，因为v以十进制写入（因此每个额外字符将有效载荷大小增加十倍）而x的长度不是。

希望这会有所帮助！

来源

2014-01-08 22:15:48 templatetypedef

谢谢你的回答！我确实快速浏览了上下文无关的抽象引理，但是我没有看到在这种情况下如何应用它。你的解释非常好！ – Paul

可以使用上下文无关语法描述char数的语言吗？

回答

相关问题