1

目前我正在努力学习和理解正式的语言和语法。我了解乔姆斯基层次结构，但我发现了一项我不知道他们如何获得解决方案的任务。任务是：

G=({S},{a,b},S,P)
P={S->epsilon, S->aS, S->Sb}
  1. 这个语法的最大类型是什么？
  2. 最大的类型是L(G)什么？

我知道语法是类型 2，但在答案中写的L(G)是类型 3。

似乎也有描述这种语言的第 3 类语法，但是你怎么知道哪种是形式语言的最大类型呢？有什么诀窍吗？

4

1 回答 1

0

我不认为有一些简单的算法方法可以始终判断语言L(G)的类别。我的意思是说，总的来说，我认为有些情况根本无法以一种或另一种方式证明。鉴于不受限制的语法可以编码算术，这是由于不完整/不可判定性造成的。这是非常手动的。

启发式地，您可以尝试理解您的语言是什么，您可以转换语法以尝试强制语法更简单等，但这些并不能保证成功。

在这种特殊情况下，弄清楚语言是什么，识别它是正常的，并为它写下语法并不是太糟糕。

S -> e
S -> aS
S -> Sb

派生自的任何字符串都可以以任意数量的s byS开头，并且可以以任意数量的s by结尾。我们可以假设语言是，然后通过证明 (1) L(G) 是 a b的子集和 (2) a b是 L(G) 的子集来证明它。aS -> aSbS -> Sba*b*

(1) The proof is by induction on the number of applications of S -> aS and S -> Sb. Base case: if neither of these is applied, only the string e is derivable. e is in a*b*, so the base case is confirmed. Induction hypothesis: assume any string derived by up to and including k applications of S -> aS and S -> Sb is in a*b*. Induction step: we show that any string derived using k+1 applications of these productions is also in a*b*. Any string derived in k+1 productions has one derived in k productions by skipping the k+1st production. This is because the productions keep the nonterminal sets the same. We already know this shorter string derived in k applications is in a*b*. We have two cases to consider:

  1. S -> aS: this adds one a to the front of the shorter string in a*b*, keeping it in a*b*.
  2. S -> Sb: this adds one b to the end of the shorter string in a*b*, keeping it in a*b*.

Since both cases keep the string in a*b*, all strings derived in k+1 applications of the productions are in a*b* and, by induction, all strings generated by the grammar are.

(2) Consider any string a^n b^m in a*b*. It is generated by the grammar as follows: n applications of A -> aS, m applications of B -> Sb, and one application of S -> e. Thus all strings in a*b* are generated by the grammar.

于 2017-10-13T18:16:03.153 回答