个性化阅读
专注于IT技术分析

图灵机接受的语言

点击下载

图灵机接受所有语言,即使它们可以递归枚举。递归表示重复相同的规则集任何次数,而可枚举表示元素列表。 TM还接受可计算的功能,例如加法,乘法,减法,除法,幂函数等。

例:

构造一个在∑ = {a,b}上接受aba语言的图灵机。

解:

我们将假设在输入磁带上将字符串“ aba”放置如下:

磁头将读出序列,直到Δ个字符为止。如果磁带头读出“ aba”字串,则TM在读取Δ后将停止。

现在,我们将看到此图灵机如何用于aba。最初,状态为q0,头指向a:

该移动将为δ(q0,a)=δ(q1,A,R),这意味着它将进入状态q1,将a替换为A,并且头部将向右移动为:

该移动将为δ(q1,b)=δ(q2,B,R),这意味着它将进入状态q2,将b替换为B,并且head将向右移动为:

该移动将为δ(q2,a)=δ(q3,A,R),这意味着它将进入状态q3,将a替换为A,并且头部将向右移动为:

移动δ(q3,Δ)=(q4,Δ,S),这意味着它将进入状态q4,该状态为HALT状态,并且HALT状态始终是任何TM的接受状态。

相同的TM可用过渡表表示:

状态一种bD.
q0(q1, A, R)
q1(q2, B, R)
q2(q3, A, R)
q3(q4, Δ, S)
q4

相同的TM可用过渡图表示:


赞(1)
未经允许不得转载:srcmini » 图灵机接受的语言

评论 抢沙发

评论前必须登录!