algorithm - 正则文法产生字符串？

Question

我有一篇论文指出:

(...) languajes such as strings of x's followed by the same number of y's (for example xxxxyyyy) cannot be specified by a regular grammar or Finite States Automaton because these devices have no mechanism for remembering how many x's were generated when the time comes to derive the y's. This shortcoming is remedied by means of rules such as S → xSy, which always generate an x and a y at the same time. (...)

所以，我不明白这个说法，据我所知，这样的字符串可以用生产规则的常规语法生成:

S → xS

S → yS

S → y

其中 x,y 是终结符，S 是起始唯一非终结符。这个文法产生推导

S→xS→xxS→xxxS→xxxxS→xxxxyS→xxxxyyS→xxxxyyyS→xxxxyyyy

Answer 1

语法必须生成语言中的每个字符串，并且没有非语言的字符串。

您的语法还会在第三个产生式或 xxy 或 xyxy 中生成无效字符串 y，因此您可以NOT 说这是你的语言的语法。