了解CFG的基本知识

Question

在Sipser的书中刚刚开始了关于CFL的章节，并且已经不理解基本的内容了。

让这是某些语言的语法：

S -> A0A 
A -> 00A | 11A | 10A | 01A | e

对于这个A0A部分，我真的很困惑。这是否意味着从0开始的左手侧应该总是和右手边一样。这是否意味着00011或000人不在这一语言中？

Answer 1

任何S都是任何A的选项，后面是一个文本0，然后是A的另一个选项。每个A都是独立的。

字符串00011在语言中，因为您可以选择两个A(例如)，这样第一个是00A，第二个是11A。如果您递归地为两个“剩余”e选择空字符串(A)，那么当您将所有东西连接在一起时，就会得到字符串00011。

您可以做类似的事情来获得字符串000。

Answer 2

A转换为空位或两个二进制数，然后A.这意味着A转换为偶数二进制数的任意序列。

S转换成A，然后0，A，这意味着S是转换成偶数的二进制数，然后是0，然后是偶数的二进制数。也就是说，S是中间有0的奇数二进制数的任意序列。

这是否意味着从0开始的左手侧应该总是和右手边一样。

没有，怎么了？两个不同的A可以转换成不同的序列。