首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >为什么L={wxw^R\ w,x属于{a,b}^+ }是一种常规语言

为什么L={wxw^R\ w,x属于{a,b}^+ }是一种常规语言
EN

Stack Overflow用户
提问于 2013-01-25 11:54:30
回答 2查看 21.6K关注 0票数 6

利用抽头引理,我们可以很容易地证明语言L1 = {WcW^R|W ∈ {a,b}*}不是正则语言,而是。(字母表为{a,b,c};W^R表示反向字符串W)

但是,如果我们将字符c替换为"x"(x ∈ {a,b}+),例如,L2 = {WxW^R| x, W ∈ {a,b}^+},那么L2 是一种常规语言。

你能给我一些想法吗?

EN

回答 2

Stack Overflow用户

发布于 2013-01-25 18:28:23

在语言中,任何字符串都可以被解释为以相同符号开头和结尾的语言中的字符串,在这种语言中,一个字符串以相同的符号开头和结尾。有两个符号:a和b,因此该语言相当于语言a(a+b)(a+b)*a + b(a+b)(a+b)*b。为了证明这一点,您应该形式化这样的论点:“如果y在WxW中,那么y在a(a+b)(a+b)*a + b(a+b)(a+b)*b中;如果y在a(a+b)(a+b)*a +b(a+b)(a+b)*b中,那么y在WxW中”。

因为c是一个固定的符号,所以它不能在另一种情况下工作,并且不能包含除了末端的所有字符之外的所有字符。一旦在示例中绑定了"x“的长度,语言就变得不规范了。

票数 2
EN

Stack Overflow用户

发布于 2013-02-02 13:38:44

问题是W {a,b}^+,所以a^n(a+b)a^n应该在L2语言中。现在没有这样的DFA来接受字符串a^n(a+b)a^n,因为在接受了a和(a+b)^+的n个数后,dfa无法准确记住它在开始时接受了多少a,所以L2不应该是regular.........But,因为我在搜索这个答案时,它说是regular.....this困扰着我。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14521300

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档