srcmini

2020-02-14半瓶木阅读(1016)评论(0)赞(0)

本文概述 历史 何时使用Backbone.js Backbone.js是一个重量很轻的JavaScript库或框架，可帮助开发人员以结构化的方式创建单页应用程序。这些客户端应用程序在Web浏览器上运行。它基于MVC模式，该模式将数据抽象到模...

2020-02-14半瓶木阅读(1932)评论(0)赞(0)

自动机入门介绍 自动机理论 有限自动机 转换图 转换表 确定性有限自动机（DFA） 确定性有限自动机的例子 非确定性有限自动机（NFA） 非确定性有限自动机的例子 消除ε转换的自动机 从NFA到DFA的自动机转换 自动机从ε NFA到DFA...

2020-02-14半瓶木阅读(1843)评论(0)赞(0)

Chomsky层次结构表示不同机器接受的语言类别。乔姆斯基层次结构中的语言类别如下： 类型0称为无限制语法。 类型1称为上下文相关语法。 类型2称为上下文无关语法。 类型3常规语法。 这是一个层次结构。因此，类型3的每种语言也都是类型2、1...

2020-02-14半瓶木阅读(1568)评论(0)赞(0)

在本节中，我们将讨论字符串的不确定性，而不是图灵机的不确定性。字符串的不确定性借助Post的对应问题（PCP）来确定。让我们定义PCP。 “该帖子的对应问题由两个在输入上长度相等的字符串列表组成。这两个列表分别是A = w1，w2，w3，&...

2020-02-14半瓶木阅读(1817)评论(0)赞(0)

本文概述 减少 空和非空语言 在本节中，我们将讨论有关图灵机的所有不确定的问题。减少量用于证明给定语言是否可取。在本节中，我们将首先了解归约的概念，然后我们将在这方面看到一个重要的定理。 减少 归约是一种技术，其中，如果将问题P1简化为问题...

2020-02-14半瓶木阅读(1778)评论(0)赞(0)

本文概述 通用语言的不确定性 在计算理论中，我们经常遇到这样的问题，这些问题回答为“是”或“否”。可以回答“是”的问题类别称为可解决的或可判定的。否则，这类问题被认为是无法解决或无法确定的。 通用语言的不确定性 通用语言Lu是一种可递归枚举...

2020-02-14半瓶木阅读(3177)评论(0)赞(1)

范例1： 为语言L = {0n1n2n}构造一个TM，其中n≥1 解： L = {0n1n2n | n≥1}表示只使用3个字符（即0、1和2）的语言。在这种情况下，一定数量的0后跟相等数量的1，然后再相等数量的2。属于此类别的任何类型的字符...

2020-02-14半瓶木阅读(2342)评论(0)赞(1)

图灵机接受所有语言，即使它们可以递归枚举。递归表示重复相同的规则集任何次数，而可枚举表示元素列表。 TM还接受可计算的功能，例如加法，乘法，减法，除法，幂函数等。 例： 构造一个在∑ = {a，b}上接受aba语言的图灵机。 解： 我们将假...

2020-02-14半瓶木阅读(2219)评论(0)赞(0)

本文概述 图灵机的正式定义 图灵机由艾伦·图灵（Alan Turing）于1936年发明。它是一种接受设备，它接受由类型0语法生成的递归可枚举语言。 图灵机具有多种功能： 它具有一个外部存储器，可以记住任意长输入序列。 它具有无限的存储功能...

2020-02-14半瓶木阅读(1892)评论(0)赞(0)

可以借助以下表示对图灵机进行建模。 1.输入磁带上有无限多个单元，每个单元包含一个输入符号，因此可以将输入字符串放在磁带上。空磁带由空白字符填充。 2.有限控制和负责读取当前输入符号的磁带头。磁带头可以从左到右移动。 3.机器必须经历的一组...