1

如果我有一种由以下上下文无关文法定义的语言 {0,1} 和起始变量 S，它是一种常规语言吗？S→TS, S→1T, S→1S T→TT, T→0T1, T→1T0 T→ε</p>

这种语言是正规的吗？

在我看来，这种语言不可能是规则的，因为它基本上是终端和变量的任意组合。而常规语言需要是右或左线性的。我是对的，还是我的想法不正确？是否有任何人推荐确定上下文无关语法是否正常的特定过程？

4

1 回答 1

2

与语法相关的语言不规则。帖子的其余部分与此声明的证明有关。

首先，请注意L(T) = {w over {0,1} | w contains equal number of 0s and 1s}.

你可以很容易地证明这一点。

证明想法。 (==>)假设w在L(T). 那么显然有相同数量的 0 和 1。

(<==)假设w包含相等数量的 0 和 1。我们通过归纳表明w可从 导出T。如果|w|<=2，那么它显然可以从 推导出来T。假设，对于归纳假设，所有长度k（偶数长度）且 0 和 1 数量相等的字符串都可以从 导出T。让w长度k+2。如果w匹配的第一个和最后一个字符（均为 0 或均为 1），则应用产生式T -> TT；第一部分和最后一部分都可以从T归纳假设推导出来；在这里，我们使用了一个明显的属性，即如果w[0]=w[|w|-1]存在一个索引i，使得w[0..i]和w[i+1..|w|-1]都在 中L(T)，并且都可以从T由归纳假设。否则，如果第一个和最后一个字符w不匹配，请使用T -> 0T1or T -> 1T0; 得到的字符串是有长度的，并且可以通过归纳假设k推导出来。QED。T

现在，语法的语言是可以由 生成的字符串集合S。请注意，它会S生成形式为 的字符串（终端和变量）(T+1)*1T。换句话说，对于任何w可由文法派生的终结符字符串，它必须是S =>* α =>* w, where αis in的情况(T+1)*1T。

现在应该很明显，可以生成的所有可能终端的集合S由正则表达式表征(L(T)* + 1)*1L(T)*。（您可以通过检查可以从 生成的终端字符串集来达到此目的(T+1)*1T。）

您可以简化L(S):的表达式，(L(T)+1)*1L(T)=(L(T)+1)*因为 的语言1L(T)是 的语言的子集(L(T)+1)^2。因此L(S) = (L(T)+1)*，该语言由包含至少与 0 一样多的 1 的二进制字符串组成。

这种语言不规则。您可以使用抽水引理证明这一点。

证明。假设，为了矛盾，那L(S)是有规律的。然后，根据抽水引理，n>0每个长度至少可以分解w为：L(S)nw=xyz

  1. |xy| <= n,
  2. y非空，
  3. 对于所有k >= 0，xy^ky在L(S)。

让w=0^n1^n是一个长度m=2n从的字符串L(S)。（引理涉及来自 的所有足够长的字符串L(S)，因此我们可以选择任何我们喜欢的字符串并且仍然具有这些属性。）让w=xyz是由引理存在的分区。显然，因为m=2nand |xy|<=n,y仅由0s 组成（并且至少一个0sincey不为空）。

显然，xy^2z零比一多，因此不在L(S). 这与抽水引理相矛盾。因此，L(S)不规律。QED。

于 2017-01-27T15:04:44.603 回答