免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 4677 | 回复: 20

[算法] 新春快乐! 顺便请教个中学数学题目 [复制链接]

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-09 13:49 |显示全部楼层
本帖最后由 captivated 于 2013-02-09 17:06 编辑

    是关于NFA的两种处理模型的.

    NFA不同于DFA,在于其引入了epsilon转移,因此,当NFA处于某个具有epsilon转移的状态,并且处于输入流上的某个点时,实际上NFA需要对剩下的输入流做一个猜测。

    考虑正则表达式 a*ab:
   

dfa of a*ab

dfa of a*ab

    figure 1

    figure 1中, 蓝色圆圈标明的状态为接受状态.

    RE a*ab可以匹配 ab, aab, aaab, aaaab, aaaaab,... etc.
    epsilon转移的引入,使得在状态s0遇到输入字符a时, NFA可以采取两种不同的转移: s0 ---epsilon---> s1,    or s0---a--->s0.
    也即, 当处于状态s0时, NFA需要“猜测”正确的转移: 根据剩下的输入流,应该转移到s0呢,还是转移到s1?

    对于NFA的这种"猜测"的处理,历史上有两种基本模型。
    1) 每次NFA必须进行非确定性选择时,如果有使得输入字符串转向接受状态的转移存在,则采用这样的转移。如果从编码的角度来说,就是先采用某个转移,然后继续匹配下去,当耗尽输入流时仍未到达接受状态,或者继续匹配导致转移到错误状态,那么就回溯到开始的需要进行非确定性选择的状态,选择另一个转移继续试探。简单地说就是试探--回溯。这个模型导致,如果我们使用这个NFA模型来设计词法匹配,那么这个词法匹配算法不是O(n)的(现在的词法分析器都是O(n)的;但是那是把NFA转换为DFA,然后根据DFA构建的词法分析器。这里讨论的是,假设直接在NFA上构建词法匹配算法的第一种模型)。
    2) 每次NFA必须进行非确定性选择时,NFA都克隆自身,以追踪每个可能的转移。在这个模型中,NFA并发地追踪所有转移路径。可以想象,从这个需要进行非确定性选择的状态开始,所有属于 该状态的epsilon-closure集合 的状态都被克隆,每个克隆都是从原来的“主线程” fork or clone 出来的线程,每个线程都追踪剩下的输入流。当耗尽输入流仍未到达接受状态或者继续匹配导致转移到错误状态,那么该线程自然死亡。这种想法也是NFA转换为DFA的“子集构造”算法的基本出发点。假设每次fork出来的线程都有相应的资源来处理的话,那么显然这个算法是O(n)的(事实上,我们假设直接真的用多线程来处理这个,很显然不太可能出来个线程就分配个CPU物理线程给用,所以实际上它仍然不是O(n)的,某种程度上,说“多线程O(n)算法”,就意味着这个算法实际上不是O(n)的。所以实际上编译器采用的词法分析器都是将NFA转换为DFA,然后构建O(n)算法的)。

=======================

ok. 这个是引子介绍,我要请教的问题不是这个,当然问题也不困难,只是我脑袋搭铁迷糊了,请广大CUer帮忙解答下罢~楼下继续。

=======================
update: s0---epsilon---> s1, 之前写错.

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2013-02-09 14:02 |显示全部楼层
1. translate a*ab to a+b (but it seems difficulty, but if you can detect the "collicision", just as you descripted, it is not a promble)
2. look ahead one more token, but it actually is not able to handle all collicision case...

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-09 14:10 |显示全部楼层
本帖最后由 captivated 于 2013-02-09 14:11 编辑

ok, 继续。

我们采用前述介绍的第二种模型,也就是每当需要进行非确定性选择时克隆自身。在任一时刻,存在NFA克隆副本活动状态的那些集合称为NFA的配置。当NFA到达一个配置,此时NFA已经耗尽输入流,且配置中的一个或多个克隆副本处于某个接受状态时,则NFA接受该输入流(为合法的单词/字符串)。

question 1: 具有n个状态的NFA,最多会产生 |Sigema| ^ n 个配置(sigema是字母表。希腊字母打印不便你懂的)。求解释,求证明。最好是构造性证明,也即,能够构造出具有这样的最大配置数的NFA吗?如果能,那么它长什么样?有RE吗? 请画出转移图。

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-09 14:12 |显示全部楼层
回复 2# folklore


    嗯。我还正要@你呢。算法我已经给了。我的问题不是如何编码处理NFA。问题在你回复的楼下。Thanks.

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2013-02-09 14:24 |显示全部楼层
in actually my math is very poor. @cjaizss

proof:
set alpha = the token dictory that nfa can accept
let alphas =a list of all token that the nfa accepts
you can define a regular exp such as:
[alphas]{0, the size of alphas} \<< repead it n times\ [alphas]{0, the size of alphas}

i think the above exp generating |Sigema| ^ n  nfa copies.

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-09 14:27 |显示全部楼层

论坛徽章:
11
摩羯座
日期:2013-09-16 11:10:272015亚冠之阿尔萨德
日期:2015-06-12 22:53:29午马
日期:2014-04-15 11:08:53亥猪
日期:2014-03-02 23:46:35申猴
日期:2013-12-06 22:07:00亥猪
日期:2013-11-28 12:03:13双鱼座
日期:2013-11-21 14:43:56亥猪
日期:2013-10-23 10:55:49处女座
日期:2013-10-17 18:15:43午马
日期:2013-09-27 17:40:4215-16赛季CBA联赛之青岛
日期:2016-06-22 00:45:55
发表于 2013-02-09 23:48 |显示全部楼层
本帖最后由 Ager 于 2013-02-11 04:46 编辑
captivated 发表于 2013-02-09 14:27
@幻の上帝
@starwing83
@Ager


Well, let me have a Chě:

As to the concept “configuration” you mentioned, also means the instantaneous description of a certain NFA, and I prefer to translate it with “构形” or “组态” but NOT “配置” since the latter Chinese word actually means “an action of setting upon some configuration”.

A “configuration” of a finite-state automaton M<Q,Σ,σ,s,F> should metaphysically be a singleton uqv like a dimensional formula in physics: q is a single one of states in Q, and uv is a string in Σ*. So, a configuration of M, either DFA or NFA, should be expressed as a word in QΣ*.

The method of “configuration” is frequently used in the process so-called “Powerset/Subset construction”: Be aware that NFA always has the finite numbered clones, that is to say, this number of “configuration” must be bounded ---  a piece of “configuration” either refers to a certain clone in that state or nothing to be referred to. Therefore, if this NFA has n states, it should play at most 2^n  configurations, that is a basic fact due to Powerset/Subset construction we play.

Furthermore, if we perform the behavior of a NFA, it should need a DFA who has a single state for EACH “configuration” of the former NFA. Now we denote the set of ALL Subsets of N as:

2^^N

So, this DFA's Q should be at most 2^^(NFA's Q). As we know, 2^^(NFA's Q) is finite. So, we always perform a behavior of DFA with a finite procedure which time is always consumed by a linearly growth with the length of input string.

Now we call a NFA<N,Σ,σ,n,f> as “渣”.

渣 has a certain number of “configuration”s NO more than

| 2^^N |

Well, stop here, on this great night. More stuff about so-called “proof” and/or “pseudo-/code” MAY come soon.

F-Y-I, He-he... Happy Chinese New Year {:3_193:}


论坛徽章:
2
操作系统版块每日发帖之星
日期:2015-08-05 06:20:0015-16赛季CBA联赛之北控
日期:2019-02-13 22:56:03
发表于 2013-02-10 00:04 |显示全部楼层
本帖最后由 346196247 于 2013-02-10 00:59 编辑

好吧cu的c版,改成english交流,我虽然中文english都不好,

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-10 14:41 |显示全部楼层
本帖最后由 captivated 于 2013-02-10 14:44 编辑

回复 5# folklore


    Thanks for your reply. Let me think a bit~

    Best wishes for a wonderful chinese new year!

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2013-02-10 14:57 |显示全部楼层
回复 7# Ager


    HoHo, Best wishes for chinese new year~

    about the translation of "configuration", surely "构型" or "组态" is more appropriate.

    Thanks for your reply, Let me think a bit,
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP