来自文法的字符串

Question

我一定是在 class 打瞌睡了。我明天要考试，这是在复习 sheet 上，我不知道这意味着什么。如果有人可以解释一下 and/or 有一个 link 可以让我了解“它”的地方，那将会很有帮助。谢谢

Consider the language that the following grammar defines:

< S > ::= $ | < W > | $< S >

< W > ::= abb | a < W > bb

Write all strings that are in this language and contain seven or fewer character

编辑：这是另一个例子：

< Str >::= X< Str > | Y< Another > < Another >::= Z | Z< Another >

Write some string in this language that contains more than three characters.

Answer 1

看起来你在 Backus–Naur Form 上睡过了 class。

第一个例子有两个规则。

第一个：

< S > ::= $ | < W > | $< S >

表示 <S> 是美元符号、<W> 或美元后跟 <S>

第二个：

< W > ::= abb | a < W > bb

表示 <W> 可以是 abb 也可以是 a 后跟 <W> 后跟 bb

请注意，在此示例中，<S> 可以包含另一个 <S>，而 <W> 可以包含另一个 <W>

因此所有少于 8 个字符的字符串的列表将从：

$
$$
$$$
$$$$
$$$$$
$$$$$$
$$$$$$$

那是在我们考虑使用 <W> 规则之前。

希望你的考试题更像第二个例子。答案可能很简单 XYZZ

来自文法的字符串

Strings from grammar

context-free-grammar