规则语言和证明(计算模型)
我需要一些HW问题的帮助，我得到了我的计算课程的模型。我读了课文的相关章节(迈克尔·西普瑟的“计算理论导论”)，但我觉得这些HW问题需要这本书没有给我的知识。第一个问题是：
(1)证明不存在L语言，使L* = {a}* {b}*暗示使用矛盾。
显然，右边是一个正则表达式；0或多个a，后面是零或多个b。这也可能是空字符串epsilon。
我的麻烦来了。我完全不知道一个*应用于一种语言做什么，也不知道如何处理这个等式，因为语言L上有*。
如能为这个问题提供任何帮助或资源，将不胜感激。
=====
第二个问题比较容易，我觉得我几乎可以做到。我可以向自己证明这一点，所以我想问题是正式地写出来。第二个问题是：
(2)证明了如果A和V是同一字母(西格玛)和A(是B的子集)上的语言，则A* (是) B*的子集。提示是使用归纳法。
现在显然(例如)如果sigma = {1，0}
和A= {00，01，10，11}
和B= {00，01，10，11,100,101,110,111}
A*中的任何东西都在B*下关闭，因为B=A+其他一些东西.如果有人能帮我把它正规化成归纳形式，我会很感激的。
谢谢
回答 1
Stack Overflow用户
发布于 2012-06-25 23:32:16
(1)以下是L*的一个有用的递归定义
- 埃普西隆在
L* - 如果
x在L，x在L* - 如果
x和y在L*，xy也是 - 对于给定的
L*，L是满足1. - 3的最小语言。
有了这个定义，这里有一个矛盾的证明:假设R* = a*b*。然后ab在R*。到3.，abab也必须在R*中。但是接着是R* != a*b*，一个矛盾。因此，R* = a*b*必须是假的；换句话说，没有语言R是R* = a*b*。
直觉很简单：L*是所有字符串的语言，这些字符串可以通过从L连接零或多个字符串(允许重复)而形成。递归定义的工作方式是允许零字符串(在1.中)、从L (在2.中)接受一个字符串的字符串，以及通过从L (in 3.)连接多个字符串而形成的字符串。
(2)利用前面给出的定义，对A*中串连字符串的数目进行归纳。对于0连接，空字符串位于A*和B*中，因此我们很好(参见规则1)。对于一个级联，因为A是B的一个子集，所以A中的字符串将在A*中(见规则2)，而来自B的字符串将在B* (相同的规则)中，因此在A*中接受一个连接的所有字符串也在B*中。现在，假设k连接在A*中的所有字符串也在B*中。在k+1中使用A*连接的字符串怎么办？这些都是使用规则3形成的，在字符串x和y上，A*中的连接严格少于k+1连接，即最多是k连接。换句话说，A*中任何接受k+1连接的字符串都可以重写为xy，其中x和y在A*中，x和y最多采用k连接。由于A*中的所有字符串最多都包含在k连接中(根据我们的假设)，所以x和y都在B*中。根据规则3，xy也必须在B*中。因此，在k+1中使用A*连接的字符串也必须属于B*。这就完成了证据。
注意:这掩盖了一些细节，并不是很正式，但你应该明白这个想法，并希望能把它塑造得更好。如果你需要比这更精致的东西，让我知道，我可以试着和你合作。
https://stackoverflow.com/questions/11198547
复制相似问题
腾讯云开发者
