了解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 S（例如），使得第一个是00A，第二个是11A。如果递归地选取空字符串（e）作为“剩余”A的两个字符串，那么当您连接所有内容时，最终将以字符串00011结尾。

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

Answer 2

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

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

这是否意味着从0开始的左手侧应始终与右手侧相同。

不，为什么？两个不同的A可以转换成不同的序列。