6

我有一个家庭作业,我完成了除一个问题(见标题)

对于我的生活,我无法弄清楚......所以我开始认为这是一个诡计问题。

我将提交的当前答案是:

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。

任何帮助/指导都会很棒。

4

1 回答 1

14

我知道截止日期已经过去,但将来有人可能会发现这很有用。

(a+b+c)*WcW^R,其中W在(a+b)+中;这是不确定的,因为您不知道“WcW”位从哪里开始。

W^RcW(a+b+c)*,其中W在(a+b)+中;这是确定性的,因为您可以编写确定性 PDA 来接受“W^RcW”形式的简单回文,并修改接受状态以在 a、b 和 c 中的任何一个上循环到自身。

这里的诀窍是 PDA 必须从左到右读取输入。

于 2012-01-06T18:03:25.150 回答