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

图灵机的例子

点击下载

范例1:

为语言L = {0n1n2n}构造一个TM,其中n≥1

解:

L = {0n1n2n | n≥1}表示只使用3个字符(即0、1和2)的语言。在这种情况下,一定数量的0后跟相等数量的1,然后再相等数量的2。属于此类别的任何类型的字符串都将被该语言接受。

001122的仿真如下所示:

现在,我们将看到此图灵机如何在001122上工作。最初,状态为q0,并且将head指向0的情况是:

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

移动将为δ(q1,0)=δ(q1,0,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:

该移动将为δ(q1,1)=δ(q2,B,R),这意味着它将进入状态q2,由B代替1,并且头部将向右移动为:

移动将为δ(q2,1)=δ(q2,1,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:

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

现在移动δ(q3,2)=δ(q3,2,L)和δ(q3,C)=δ(q3,C,L)和δ(q3,1)=δ(q3,1,L)和δ(q3,B)=δ(q3,B,L)和δ(q3,0)=δ(q3,0,L),然后移动δ(q3,A)=δ(q0,A,R) ,这意味着将进入状态q0,将A替换为A,并且head将向右移动为:

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

该移动将为δ(q1,B)=δ(q1,B,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:

该移动将为δ(q1,1)=δ(q2,B,R),这意味着它将进入状态q2,由B代替1,并且头部将向右移动为:

该移动将为δ(q2,C)=δ(q2,C,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:

该移动将为δ(q2,2)=δ(q3,C,L),这意味着它将进入状态q3,将2替换为C,并且磁头将向左移动,直到我们到达A为止:

紧接B是A之前,这意味着所有0都被A卖出。因此,我们将向右移动以确保不存在1或2。移动将为δ(q2,B)=(q4,B,R),这意味着它将进入状态q4,不会更改任何符号,并向右移动为:

移动将是(q4,B)=δ(q4,B,R)和(q4,C)=δ(q4,C,R)这意味着它将不更改任何符号,保持相同的状态并移动到正确的是:

移动δ(q4,X)=(q5,X,R),这意味着它将进入状态q5,该状态为HALT状态,而HALT状态始终是任何TM的接受状态。

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

范例2:

构造一个TM机器,以检查均匀长度的字符串的回文。

解:

首先,我们从左侧读取第一个符号,然后将其与右侧的第一个符号进行比较,以检查其是否相同。

同样,我们将左边的第二个符号与右边的第二个符号进行比较。我们对所有符号重复此过程。如果发现任何不匹配的符号,则无法使机器进入HALT状态。

假设字符串是ababbabaΔ。 ababbabaΔ的仿真如下所示:

现在,我们将看到此图灵机如何在ababbabaΔ上工作。最初,状态为q0,头指向a:

我们将用*标记它,并在右端搜索a:

我们将向上移动到Δ,如下所示:

我们将向左移动并检查是否为:

它是“ a”,因此将其替换为Δ并向左移动为:

现在向左移动到*为:

向右移动并阅读

现在将b转换为*并向右移动为:

右移至Δ以搜寻b为:

向左移动,如果符号为b,则将其转换为Δ,如下所示:

现在左移直到*为:

用*替换a,然后右移至Δ,如下所示:

我们将向左移动并检查它是否为a,然后将Δ替换为:

它是“ a”,因此用Δ替换为:

现在向左移动,直到*

现在向右移动为:

将b替换为*,然后右移至Δ,如下所示:

向左移动,如果左侧符号为b,则将Δ替换为:

向左移动直到*

向右移动并检查是否为Δ

进入暂停状态

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

范例3:

构造一个用于检查奇数长度字符串回文的TM机器。

解:

首先,我们从左侧读取第一个符号,然后将其与右侧的第一个符号进行比较,以检查其是否相同。

同样,我们将左边的第二个符号与右边的第二个符号进行比较。我们对所有符号重复此过程。如果发现任何不匹配的符号,则会使计算机进入HALT状态。

假设字符串是00100Δ。 00100Δ的仿真如下所示:

现在,我们将看到此图灵机如何在00100Δ下工作。最初,状态为q0,并且通过以下方式指向0:

现在将0替换为*,并向右移动为:

向右移动到Δ,如下所示:

左移并用Δ替换0并左移:

现在左移至*为:

向右移动,将0转换为*,然后向右移动为:

右移至Δ

向左移动并用Δ替换0为:

左移直到*为:

向右移动并将1转换为*为:

向左移动

由于它是*,因此进入HALT状态。

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

范例4:

为一元数系统的加法函数构造TM。

解:

一元数仅由一个字符组成,即数字5可以在一元数系统中写为11111。在此TM中,我们将对两个一元数进行加法运算。

例如

2 3即11111 = 11111

如果你观察到这种加法过程,你会发现与字符串串联函数的相似之处。

在这种情况下,我们只需将其替换为1,然后向右移动以搜索字符串的末尾,我们会将后1转换为Δ。

输入:3 2

11111Δ的仿真如下所示:

向右移动以签名为:

转换为1并向右移动为:

现在,向右移动

再次向右移动

现在已经遇到了Δ,因此向左移动为:

将1转换为Δ

因此,磁带现在由两个一元数相加组成。

TM如下所示:

在这里,我们正在实现f(a b)= c的功能。我们假设a和b都是非零元素。

范例5:

构造一个用于减去两个一元数f(a-b)= c的TM,其中a始终大于b。

解决方案:这里我们有一些假设,因为第一个数字大于第二个。让我们假设a = 3,b = 2,因此输入磁带将是:

我们将向右移动-符号,从第一个数字开始减少1。让我们看一下模拟以了解逻辑:

右移至-为:

向右移动并将1转换为*为:

现在向左移动

再次向左移动

将1转换为*并向右移动

现在右移至1

将1转换为*并向左移动

将1转换为*并移动

向右移动直到Δ为:

现在我们处于HALT状态。

因此,我们在输入磁带上得到1作为f(3-2)的答案。

图灵机将如下所示:


赞(1)
未经允许不得转载:srcmini » 图灵机的例子

评论 抢沙发

评论前必须登录!