在Sipser的书中刚刚开始关于CFL的章节,并且已经不了解基础知识。了解CFG的基本知识
让这成为一些语言的语法:
S -> A0A
A -> 00A | 11A | 10A | 01A | e
我真搞不清楚这个A0A部分。这是否意味着从0开始的左手侧应始终与右手侧相同。这是否意味着00011或000不是用这种语言呢?
在Sipser的书中刚刚开始关于CFL的章节,并且已经不了解基础知识。了解CFG的基本知识
让这成为一些语言的语法:
S -> A0A
A -> 00A | 11A | 10A | 01A | e
我真搞不清楚这个A0A部分。这是否意味着从0开始的左手侧应始终与右手侧相同。这是否意味着00011或000不是用这种语言呢?
任何S
是您对任何A
的任何选项,其后是单个文字0
,然后是另一个选项A
。每个A
是独立的。
字符串00011
是在语言,因为你可以选择你的两个A
S(例如),使得第一个是00A
,第二个是11A
。如果递归地选取空字符串(e
)作为“剩余”A
的两个字符串,那么当您连接所有内容时,最终将以字符串00011
结尾。
你可以做类似的事情来获得字符串000
。
A转换为空或两个二进制数字,然后转换为A.这意味着A转换为偶数个二进制数字的任意序列。
S转换为A,然后是0,然后是A.这意味着S转换为偶数个二进制数字,然后是0,然后是偶数个二进制数字。也就是说,S是中间有0的奇数个二进制数字序列。
这是否意味着从0开始的左手侧应始终与右手侧相同。
不,为什么?两个不同的A可以转换成不同的序列。
谢谢你的回答。出于某种原因,我认为他们必须是相同的。 – Multik