计算理论导引实验三:构造图灵机

这篇具有很好参考价值的文章主要介绍了计算理论导引实验三:构造图灵机。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验描述

要求构造一个能够识别语言L的图灵机。语言L的描述和实验内容如下图所示

计算理论导引实验三:构造图灵机

形式化定义

根据实验描述,可以将图灵机进行如下设计,得到图灵机的七元祖形式化定义。

  1. 状态集为{start,q0,q1,q2,q3,q4,q5,q6,q7,q9,accept,reject}
  2. 输入字母表为{#,+,=,1},这里使用1来表示代替题中点的特定字符
  3. 带子字母表为{#,+,=,1,X,},这里使用‘’在代码中表示特殊空白符号
  4. 起始状态为start
  5. 接受状态集为{accept}
  6. 拒绝状态集为{reject}
  7. 转移函数用状态图来描述,如下图所示,为简化状态图,没有在图中显示拒绝状态,也没有显示到拒绝状态的转移,表明一个状态对某个字符没有向外的转移即拒绝。图中的|_|用来表示特殊空白符号

图灵机M的状态图

计算理论导引实验三:构造图灵机

算法设计与描述

将整个过程抽象成两个类,分别为状态转移类,键盘输入及逻辑处理类。

状态转移关系类

该类主要用于表示转移函数中的各项,在设计中,该类的结构如下:

  1. 成员变量:当前状态,读写头指的字符,转移的新状态,是否修改纸带,要替换的字符和图灵机读写头移动的方向。
  2. 成员方法:获取和设置当前状态、读写头指的字符、转移的新状态、是否修改纸带、要替换的字符和图灵机读写头移动的方向的方法。重写tostring方法,用来得到当前对象的字符串表示。
  3. 构造方法:无参构造方法和带参数的构造方法。

键盘输入及逻辑处理类

该类是用来进行一系列的初始化、以及根据状态转移函数得到图灵机读写头移动方向及状态转移是否修改纸带等操作的类,主要包括以下几项:

  1. 初始化待识别字符串
    通过键盘输入字符串,并对输入的字符串进行前后加空白符号特殊处理后,将字符串保存到字符数组中。这里使用“_”来代替特殊的空白符号
  2. 初始化状态转移关系集合
    将图灵机的每个状态转移关系保存到集合中。每一个状态转移函数关系都是状态转移关系类的一个实例化对象,包含了读写头指的字符,转移的新状态,是否修改纸带,要替换的字符和图灵机读写头移动的方向。
  3. 图灵机状态转移处理
    对于输入的字符串中每一个真实输入的字符进行循环操作:
    a) 遍历状态转移集合,判断当前状态下,读入当前字符,根据状态转移函数中对应的操作,进行替换字符、状态转移、图灵机读写头左右移动,如果找到了符合条件的就进行b)中操作,之后进行d)操作。否则直接执行c)中操作。
    b) 此时表明存在转移,如果状态转移函数中的是否改变纸带来对纸带进行对应操作,若需要改变,则修改读写头所在位置纸带的值,根据图灵机读写头R还是L进行相应的右移和左移,同时转移到新的状态。
    c) 此时表明当前状态下,图灵机读写头对于当前字符没有任何转移操作,也就是此时便不满足该图灵机的构造,不能被识别,得出该字符串被设计的图灵机拒绝。程序结束。
    d) 在之前的步骤进行完之后,如果当前图灵机的读写头到了特殊空白符号,并且当前的状态也到了accept接受状态时,该输入字符串被设计的图灵机所接受。否则便是c)中的情况。

编码实现

此处省略代码部分。

测试运行

以输入为#1+1=1时为例,被本次设计的图灵机拒绝。
计算理论导引实验三:构造图灵机文章来源地址https://www.toymoban.com/news/detail-483031.html

到了这里,关于计算理论导引实验三:构造图灵机的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【现代密码学】笔记6--伪随机对象的理论构造《introduction to modern cryphtography》

    主要在 哈工大密码学课程 张宇老师课件 的基础上学习记录笔记。 内容补充:骆婷老师的PPT 《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell(现代密码学——原理与协议)中相关章节 密码学复习笔记 这个博主好有意思 初步笔记,如有错误请指正 快速补充一些密码

    2024年01月16日
    浏览(42)
  • R语言实验1 :数据的描述性分析

    实验 1     数据的描述性分析 一、实验目的 1. 掌握理解均值、方差等一系列统计相关概念。 2. 加深对散点图、直方图、相关系数等概念的理解。 3. 熟悉R语言等语言的集成开发环境。 二、实验分析与内容 完成教材P37第6题。 题目如下: ( 1 )(1)分别计算数学成绩和统计学成

    2024年01月18日
    浏览(49)
  • 数理统计SPSS软件实验报告一--描述性统计

    实验报告内容: 1 、实验目的: 熟练掌握利用SPSS进行描述性统计分析的基本技能。 2 、实验要求: (1) 利用SPSS软件计算常用统计量(样本均值、中位数、众数、分位数;最大值、最小值、极差、总和、样本方差、样本标准差、变异系数;偏度系数、峰度系数等)的值; (2)

    2023年04月12日
    浏览(58)
  • 【深度学习】实验05 构造神经网络示例

    神经网络是一种仿生学原理的机器学习算法,灵感来源于人脑的神经系统。它由多个神经元(或称为节点)组成,这些神经元通过连接权重形成复杂的网络结构,用来学习和提取输入数据的特征,并用于分类、回归、聚类等任务。 注明:该代码用来训练一个神经网络,网络拟

    2024年02月10日
    浏览(44)
  • Unity UI设计 软件构造实验报告

    实验 1: 仿真系统的 UI 主界面设计 (1)熟悉Unity中UI界面的设计与编写; (2)熟悉UI界面中场景转换,UI与场景内容相互关联的方式。 (3)熟悉Unity中MySQL数据库的操作 新建一个Unity场景,在此场景中实现如下功能: (1)自行设计一个登录、注册UI界面; (2)添加数据库的动

    2024年02月05日
    浏览(35)
  • Unity 三维场景的搭建 软件构造实验报告

    实验 2 :仿真系统功能实现 (1)熟悉在Unity中设置仿真场景; (2)熟悉在Unity中C#语言的使用; (3)熟悉仿真功能的实现。 新建一个仿真场景,完成下列功能: (1)使用Unity的基本建模功能设置一些三维场景(自行发挥想象,进行建模设计) (2)实现漫游功能,可以在场

    2024年02月05日
    浏览(44)
  • 《数学建模与数学实验》第5版 数据的统计描述 习题8.7

    参考教材:《数学建模与教学实验》第5版 提示:以下是本篇文章正文内容,来自参考教材课后习题。 93 75 83 93 91 85 84 82 77 76 77 95 94 89 91 88 86 83 96 81 79 97 78 75 67 69 68 84 83 81 75 66 85 70 94 84 83 82 80 78 74 73 76 70 86 76 90 89 71 66 86 73 80 94 79 78 77 63 53 55 matlab求解: 结果: 均值为:80.1;标

    2024年02月06日
    浏览(69)
  • 防火墙用户管理理论+实验

    目录 注:实验需要有安全策略配置、NAT配置基础 一、防火墙用户管理重要知识点 用户管理 访问控制策略 NGFW下一代防火墙 AAA 鉴别方式——认证 用户认证的分类: 上网用户上线流程: 二、用户认证实验: 实验拓扑 先配置防火墙上接口和区域、地址对象 配置NAT与安全策略

    2024年02月02日
    浏览(111)
  • 堆叠和集群(详细的理论和实验)

         随着企业的发展,企业网络的规模越来越大,这对企业网络提出了更高的要求:更高的可靠性、更低的故障恢复时间、设备更加易于管理等。传统的园区网高可靠性技术出现故障时切换时间很难做到毫秒级别、实现可靠性的方案通常为一主一备,存在着严重的资源浪费

    2024年02月06日
    浏览(25)
  • 实验一 第2关:从自然数中取3个数进行组合之递归算法任务描述

    任务描述 本关任务:用递归算法找出 5 个自然数中取 3 个数的组合。 编程要求 请在右侧编辑器Begin-End处补充代码,完成本关任务。 测试说明 平台会对你编写的代码进行测试,比对你输出的数值与实际正确数值,只有所有数据全部计算正确才能通过测试: 测试输入:5 3 (

    2024年02月06日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包