formal-languages - 找到一个不确定性的CFL，其反向是确定性的

Question

我有一项家庭作业，除一个问题外，我已经完成(参见标题)

对于我的一生，我无法弄清楚……所以我开始认为这是一个棘手的问题。

我将提交的当前答案是:

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，因此引入了新的不确定性。

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

Answer 1

我知道截止日期已经过去，但是将来有人会觉得有用。

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

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

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