如何使一个上下文无关的语法用于特定情况下

Question

问题是这样

创建CFG生成{一个^ I B^Y：2I < J + 2 < 3i的}。 我的问题是，这里有很多情况。例如，这对j = 1,2,4不起作用。对于j = 5,6,7,8,9，我们需要i = 3,3,4,4,4。所以我如何处理这样的事情，是否有任何技巧来做这样的事情，或者我会让它看起来更难。

Answer 1

你让它比现在更难。

使用语法是一种经典的递归分析技术。对于递归，您总是需要提出两个问题：如何才能进入下一步？我如何知道我什么时候完成？

第二个问题很简单：您已经发现基本案例是aabbb（即i=2, j=3）。没有更短的单词可以成为语法的一部分。

现在，假设我们有一个更长的单词，这意味着i必须大于2.我们如何进入下一步？换句话说，我们如何找到一个更短的有效单词？我们可以删除a（递减i），但我们还需要修复j。从不平等角度来看，很显然j可以减少两三个（可能两个都有效，但其中一个必须有效）。

这将导致模糊的语法，但问题并不是说语法需要明确。然而，如果两个答案都是可能的，那么基于总是在同一方向上解决决定（两个或三个）的策略，很容易提出一个明确的语法。