设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索
查看: 2303|回复: 7

[胡扯] [胡扯]看啥都像自动机,感觉自己学疯了

[复制链接]

Lv1.梦旅人

梦石
0
星屑
163
在线时间
249 小时
注册时间
2014-7-18
帖子
44
发表于 2018-5-22 00:36:40 | 显示全部楼层 |阅读模式

加入我们,或者,欢迎回来。

您需要 登录 才可以下载或查看,没有帐号?注册会员

x
本帖最后由 M.Winderic. 于 2018-5-22 00:44 编辑

RT,看啥都像自动机,感觉自己学疯了……
莫名地有种 hash + lambda 就可以解决全部问题的错觉……
Actor是自动机Enemy是自动机UI是自动机Story是自动机【大雾
自动机赛高?

p.s.

Role Play Games had saved me, but I can never save them.

Lv4.逐梦者

世界坑化协会

梦石
0
星屑
7528
在线时间
1546 小时
注册时间
2007-3-13
帖子
5534

极短23参与极短21参与开拓者贵宾第一届化妆舞会最佳服饰奖

发表于 2018-5-23 10:53:21 | 显示全部楼层
那么,自动机是啥????
你的肩膀上有肩周炎~♪  秒懂  ☚   \没有
回复 支持 反对

使用道具 举报

Lv5.捕梦者 (版主)

梦石
1
星屑
23963
在线时间
3338 小时
注册时间
2011-7-8
帖子
3925

开拓者

发表于 2018-5-23 13:42:21 | 显示全部楼层
自动机和元胞自动机有啥区别?
熟悉rgss和ruby,xp区版主~
正在填坑:《膜拜组传奇》讲述膜拜组和学霸们的故事。
已上steam:与TXBD合作的Reformers《变革者》
* 战斗调用公共事件 *
* RGSOS 网络脚本 *
回复 支持 反对

使用道具 举报

Lv3.寻梦者

梦石
0
星屑
1803
在线时间
133 小时
注册时间
2013-10-6
帖子
193
发表于 2018-5-23 19:26:41 | 显示全部楼层
你电脑里的CPU不是个自动机么)
←你看到一只经常潜水的萌新。
回复 支持 反对

使用道具 举报

Lv3.寻梦者

梦石
0
星屑
1803
在线时间
133 小时
注册时间
2013-10-6
帖子
193
发表于 2018-5-23 20:06:56 | 显示全部楼层
v2sam 发表于 2018-5-23 10:53
那么,自动机是啥????


自动机就是一个抽象的机器,可以用来研究可计算性问题。
而且自动机有好多种,它们的限制条件不同,适用的范围也不同(可以识别不同的语言,换句话说你给它编程的自由度不同)
举个简单的例子,有限状态自动机,对应乔姆斯基3型文法,可以识别正则语言(“正则表达式”听说过?它是一种已经规范化的成为业界标准的正则语言,尽管有许多变种)
一个确定性有限状态自动机可以描述为一个五元组(Σ,S,s0,δ,F)

这个机器可以吸进去一个有限长的纸带,然后纸带上划分好格子(一维的),每个格子上可以有一个字母,所有能用的字母构成的集合是Σ。
这个机器还能有一个状态,这个状态的所有可能取值是集合S。
机器启动的时候初始状态是s0
然后机器就一格一格地按照顺序往下读取这个纸带上的字母,设读到的字母是s
δ是状态转移函数,按照C++的话说就是
S δ(S current_state, Σ current_alphabet) {
  //根据当前状态+当前字母,转移到一个新的状态
  S new_state;
  return new_state;
}
最后F是一个集合,它是S的子集,表示终止状态

然后这个抽象机器可以干嘛呢?

比如你要识别某个字符串是否满足特定的规则。
无标题.png
它由任意个0或者1组成,并且不能包含两个或以上相邻的00。
这个有限状态自动机也能处理。一开始是q0,读到一个0就进入q1,再读到0就进入qt了。当状态为qt的时候不管读到什么都在qt里打转出不去了,并且qt不在F里面(q0和q1在)。假设我们输入“01001”,这个自动机读完纸带最终进入qt,我们就不接受这个输入。
再想想正则表达式,是不是有点这个味道了?实际上正则引擎把你输入的正则表达式变换为等价的自动机,然后用它去识别一个字符串,看它是不是自己接受的语言。

当然也有更复杂的自动机,能识别的语言更复杂,状态转移函数也更复杂。比如图灵机好像有一个可以左右来回移动的读写头,不光可以读取纸带上的字母还能把当前格子替换为其他字母…具体数学定义我就不写了,它可以搞定乔姆斯基0型文法(识别短语结构语言)

其实自动机这东西就是个数学描述而已。比如图灵机它的纸带是无限长的,而实际计算机的RAM是有限的;比如图灵机只能一个一个格子地移动读写头,但我们的RAM是可以随机存取的……

点评

想起了当凡人的幸福  发表于 2018-5-26 18:53
想起被编译原理支配的恐惧  发表于 2018-5-23 20:36
←你看到一只经常潜水的萌新。
回复 支持 反对

使用道具 举报

Lv3.寻梦者

梦石
0
星屑
1759
在线时间
2524 小时
注册时间
2010-10-12
帖子
1454

开拓者

发表于 2018-5-26 01:18:44 | 显示全部楼层
Automata? NFA, DFA, PDA

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:[email protected]|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2024-3-29 15:12

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表