考虑以下BNF语法(BNF、递归和派生)

Question

考虑以下BNF语法：

<S> ::= a <S> c <B> | <A> | b
<A> ::= c <A> | c
<B> ::= d | <A>

好的，那么我得到了各种字符串，其中之一是：

aabccd

如果字符串可以从BNF语法派生，那么我应该提供一个派生。

所以我从一个非终端开始(据我所知)：

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c c <B> ->  a b c c c d

这是正确的吗？所以它不能导出吗？因为我有三个C？还是我做错了。当涉及到BNF时，总n00b。

编辑:好的，从一个更“免费”的方法来看它。将称为"c“的终端/令牌与非终端(换句话说，在字符串中的"c”)转换为"c“是否有效/合法？既然"c“就是" A”？因此，允许我将它们转换为简单的"c“。这样我就可以获得请求的字符串：

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c <B> ->  a a b c c d

有效吗？

编辑:我不知道如何使小于和大于符号出现，尝试使用美元符号，但我想它在这里行不通。

Answer 1

您的第一个派生是正确的，并且'aabccd‘不使用此语法进行解析。你需要第三个'c‘才能被解析-所以'aabcccd’可以被解析，而不是'aabccd‘。

祝你好运。

Answer 2

因为您的语法是上下文无关的，所以您可以将其转换为乔姆斯基范式(CNF)，并应用西克(库克-杨-卡西米)算法来检查单词是否是L(G)的一部分，以便有一个无猜测、确定性的方法。