这是语法{a^2n b^n | n> = 0}上下文是否空闲？

Question

这个语法环境是否免费？

{a^2n b^n | n >= 0} 

Answer 1

你问的对象不是语法，而是语言：一组字符串。一组字符串可以用上下文无关的语法来描述，这是因为存在一些语法，其规则完全生成该组字符串。

在这种情况下，您所设定的扩张看起来是这样的：

{ "", "aab", "aaaabb", "aaaaaabbb", ... } 

这是一套由偶数a -s的所有字符串，其次是一半的b -s。

这组可通过以下规则重复产生：

1. 空字符串是在该组。
2. 如果字符串s在集合中，那么字符串"aa" + s + "b"在集合中。

也就是说，是从一个集合中的任何字符串，就可以形成一个新的字符串，这也是一组，只需添加在左边的两个a -s和右侧的b。与空字符串在集合中的基本情况规则一起，这些规则描述了整个集合。

而且这些规则等同，并且可以在，上下文无关文法的形式写出：

s -> "" 
    -> "aa" s "b" 

语法是上下文无关，因为它仅具有形式的规则“一 - >符号...“：左侧只有一个非终端符号。所以世代都不依赖于上下文：一个符号被采用，并根据一些可用的规则单独替换。