L= {a^n b^k | 2n >= k}
例如: abb是L的元素,abbb是L的元素,ε是L的元素,但是babbb不是L的元素,abbb不是L的元素
发布于 2018-08-25 05:00:13
L
中最短的字符串是空字符串e
。给定语言中的字符串s
,则以下规则成立:
as
在L
asb
中,L
asbb
在L
中
我们可以将这些观察结果结合起来,得到一个上下文无关的语法:
S := aSbb | aSb | aS | e
根据我们的观察,这个语法生成的每个字符串都必须是L
格式的。为了证明这是一种用于L
的语法,我们必须证明可以生成L
中的任何字符串。要获取字符串a^n b^k
,我们可以执行以下操作:
x
timesy
timesz
timesx + y + z = n
y + 2z = k
设置y = k - 2z
并替换,我们得到x + k - 2z + z = n
。重新排列:
如果选择k > n
,则可以选择z
和x
,只要选择n - k = x - z
.
z
,就可以选择z
和x
。只要选择k = n
,请注意,我们不妨选择请注意,在上面的示例中,我们总是可以选择z
和x
,因为它们是0 <= x, z <= n
和0 <= k <= 2n
。
https://stackoverflow.com/questions/49596481
复制相似问题