我有一个家庭作业,我完成了另外一个问题(见标题)
对于我的生活,我无法弄明白......所以我开始认为这是一个棘手的问题.
我将提交的当前答案是:
L1 = {a^n b^n: n>=1} is deterministic. And the reverse,
L2 = {b^n a^n: n>=1} is also deterministic.
但是,由于所有确定性语言都是非确定性语言的子集,因此L2可以被认为是非确定性的.
另一方面,我试图做的唯一其他例子是:
L3= {{a,b}a}
这似乎是可能的,因为前向存在非确定性,因为输入可以是a或b,只要其后跟a即可.
反之则存在决定论,因为它只接受'a'.但是,它引入了新的非确定性,因为第二个输入可以是a或b.
任何帮助/指导都会很棒.
Pat*_*k87 11
我知道截止日期已过,但有人可能会发现这在将来很有用.
(a + b + c)*WcW ^ R,其中W在(a + b)+中; 这是不确定的,因为您不知道"WcW"位的开始位置.
W ^ RcW(a + b + c)*,其中W在(a + b)+中; 这是确定性的,因为你可以编写一个确定性的PDA来接受形式为"W ^ RcW"的简单回文并修改接受状态以在a,b和c中的任何一个上循环到它自己.
这里的技巧是PDA必须从左到右读取输入.