找到一个非确定性 CFL，其反向是确定性的
我有一个家庭作业，我完成了另外一个问题（见标题）
对于我的生活，我无法弄清楚这一点......所以我开始认为这是一个棘手的问题。
我当前要提交的答案是：
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。
任何帮助/指导都会很棒。
I have a homework assignment, and i am finished other then one question (see title)
For the life of my, i cannot figure this out... so i started to think it was a trick question.
the current answer that i will submit is:
L1 = {a^n b^n: n>=1} is deterministic. And the reverse,
L2 = {b^n a^n: n>=1} is also deterministic.
However, since all deterministic languages are a subset of Non-deterministic languages, L2 can be considered non-deterministic.
On a side note, the only other example i was trying to make work is:
L3= {{a,b}a}
This seems possible because forward there is non-determinism, since the input could be either a, or b as long as its followed by an a.
and in reverse there is determinism since it will accept only an 'a'. But, it introduces new non-determinism since the second input could be either a or b.
any help / guidance would be great.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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 必须从左到右读取输入。
I know the deadline has passed, but somebody might find this useful in the future.
(a+b+c)*WcW^R, where W is in (a+b)+; this is non-deterministic because you don't know where the "WcW" bit starts.
W^RcW(a+b+c)*, where W is in (a+b)+; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form "W^RcW" and modify the accepting state to loop to itself on any of a, b and c.
The trick here is that PDAs have to read input from left to right.