数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学设计一个图灵机 (TM)，要求接受a和b数量相等的字符串，并且必须以a开头。
图灵机 (TM) 比有限自动机 (FA) 和下推自动机 (PDA) 都强大。它们与我们制造的任何计算机一样强大。
图灵机的形式化定义
图灵机可以形式化地描述为七元组
(Q,X, Σ,δ,q0,B,F)
其中：
Q 是有限的状态集
X 是带字母表
Σ 是输入字母表
δ 是转移函数：𝛿:QxX→QxXx{左移，右移}
q0 是初始状态
B 是空白符号
F 是最终状态。
图灵机 (TM) 是一种数学模型，它由一条无限长的磁带组成，磁带被分成单元格，输入就写在这些单元格上。它有一个磁头用于读取输入磁带。状态寄存器存储图灵机的状态。
读取输入符号后，它被替换为另一个符号，其内部状态发生改变，并且它从一个单元格移动到右边或左边。如果图灵机到达最终状态，则接受输入字符串，否则拒绝。
图灵机具有读/写头。因此我们可以在磁带上写入。
现在，让我们构造一个图灵机，它接受a和b数量相等的字符串，
它生成的语言是L ={ anbn| n>=1}，该语言接受的字符串是：
L= {ab, aabb, aaabbb, aaaabbbb,………}
示例
考虑n=3，所以a3b3，磁带看起来像：
B= 空白
我们需要将每个 'a' 转换为 X，每个 'b' 转换为 Y。如果图灵机包含数量相等的 X 和 Y，则它到达最终状态。
步骤 1 − 将初始状态设为 q0。此状态将 'a' 替换为 X 并向右移动，现在状态从 q0 更改为 q1，因此转移函数为：
δ(q0, a) = (q1,X,R)
步骤 2 − 向右移动直到看到空白符号。
δ(q1, a) = (q1,a,R)
δ(q1, b) = (q1,b,R)
到达空白符号 B 后，向左移动并将状态更改为 q2，因为我们需要将最后一个 'b' 更改为 Y。
δ(q1, B) = (q2,B,L) //1st iteration δ(q1, Y) = (q2,Y,L) // remaining iterations
步骤 3 − 当我们看到符号 'b' 时，将其替换为 Y 并将状态更改为 q3 并向左移动。
δ(q2, B) = (q3,Y,L)
步骤 4 − 向左移动直到到达符号 X。
δ(q3, a) = (q3,a,L) δ(q3, b) = (q3,b,L)
当我们到达 X 时，向右移动并将状态更改为 q0，然后开始下一次迭代。
将每个 'a' 和 'b' 替换为 X 和 Y 后，状态从 q0 更改为 q4。
δ(q0, Y) = (q4,Y,N)
N 表示不动。
| X | X | X | Y | Y | Y | B | B | ........................... |
q4 是图灵机的最终状态，q0 是初始状态，中间状态是 q1、q2、q3。
状态转换图
状态转换图如下：
3K+ 次查看
