grammar - 构建图灵机图
问题描述
我一直在尝试制作识别语言的图灵机图:
{(ab)^n(ba)^n | n >0}
如何为上述语言构建图灵机图?
解决方案
- 通过识别 b 的两个连续实例找到子字符串 bb
- 通过用磁带符号 X 替换这些来划掉这些
- 在 X 的实例部分反弹,以交替的方式划掉匹配的符号(首先划掉 a 的匹配实例,然后是 b,然后是 a,等等)
- 如果在划掉 a 的匹配实例后磁带为空,则停止接受
- 如果您提前用完符号或在删除 b 的实例后磁带为空,则停止拒绝
我将定义状态作为练习,但如果您需要帮助,我可以稍后重新访问此答案。作为提示 - 您将需要一个或几个状态来处理上述每个步骤。
推荐阅读
- android - Android JobScheduler 错误:重启后延迟增加(参数 minimumLatency)
- ruby-on-rails - Rspec:如何在不存根任何内容或在幕后更改任何内容的情况下预期收到的消息
- xcode - 运行 RNTester
- python - 退出'GAME OVER'的python应用程序
- python - 在随机持续时间后停止检查对文件的更改
- polymer - Polymer/Web 组件的 LINK 语句放置位置
- elasticsearch - ElasticSearch 返回聚合随机顺序
- c# - 使用 C# 为另一个用户设置 Office 365 外出回复
- android - 如何将 fontFamily 应用于 android 切换按钮?
- c - fwrite(-ing) 将列表写入 txt.file