标签: pushdown-automaton

我编写了以下程序来检查平衡括号的字符串:

isBalanced xs = isBalanced' xs []

isBalanced' [] [] = True
isBalanced' [] _  = False

isBalanced' ('(':xs) ys = isBalanced' xs (')':ys)
isBalanced' ('[':xs) ys = isBalanced' xs (']':ys)
isBalanced' ('{':xs) ys = isBalanced' xs ('}':ys)

isBalanced' _  [] = False

isBalanced' (x:xs) (y:ys) = (x == y) && (isBalanced' xs ys)

以下是一些示例数据:

positives = [
    isBalanced "",
    isBalanced "()",
    isBalanced "[]",
    isBalanced "{}",
    isBalanced "([]){}[{}]"
    ]

negatives = [
    isBalanced "(",
    isBalanced "[",
    isBalanced "{",
    isBalanced ")", …

最近我遇到了先查找后跟踪的问题

S->cAd
A->Ab|a

在这里，我对 A 的第一个感到困惑，哪个是正确的 {a} ， {empty,a} ，因为 A 的产生式中存在左递归。我很困惑是否在 A 的第一个中包含空字符串 任何帮助将不胜感激。-------------已编辑----------------

第一个和接下来的是什么，，这是我见过的如此令人困惑的语法

S->SA|A
A->a

我需要使用解析表证明这个语法不在 LL(1) 中，但无法做到，因为我没有在单个单元格中获得 2 个条目。

编辑:用户@apocalisp和@BenjaminHodgson在下面留下了很棒的答案,跳过阅读大部分问题并跳转到他们的答案.

问题的TLDR:我怎样才能从FSM表示组合爆炸的第一张图片到第二张图片,在那里您只需要在继续之前访问所有这些图片.

我想构建一个有限状态机(真的在Haskell中,但我首先尝试使用Idris来查看它是否可以指导我的Haskell),其中有一些临时状态必须在达到最终状态之前访问.如果我可以通过某种状态的谓词任意约束FSM,那就太好了.

在下图中,有一个Initial州,3个临时州A, B, C和一个Final州.如果我没有弄错,在"正常"FSM中,您将始终需要n!临时状态来表示可能路径的每个组合.

这是不可取的.

相反,使用Type Families和可能的Dependent类型,我认为应该有一种状态可以随身携带,只有当它通过某些谓词时才允许你进入最终状态.(这是否会使自动推送自动机而不是FSM？)

到目前为止,我的代码(idris),通过类比,添加成分来制作沙拉,顺序无关紧要,但它们都需要在以下内容中实现:

data SaladState = Initial | AddingIngredients | ReadyToEat

record SaladBowl where
       constructor MkSaladBowl
       lettuce, tomato, cucumber : Bool

data HasIngredient : (ingredient : SaladBowl -> Bool) -> (bowl : SaladBowl ** ingredient bowl = True) -> Type where
     Bowl : HasIngredient ingredient bowl

data HasIngredients : (ingredients : List (SaladBowl …

我相信这种语言不是上下文,因为PDA不可能比较2个0和1的相同长度的块,并且还记住它的长度以供以后使用.

不幸的是,我不知道如何证明它.

我尝试使用泵浦引理无济于事......

我还试图通过矛盾来假设语言是无上下文的,并且使用这样一个事实,即上下文无关语言与常规语言的交集也是无上下文的(通过找到一些神秘的常规语言L),并且令人惊讶(或者不是) ) - 我所有的努力都是徒劳的......

任何帮助,将不胜感激

一些编程问题不需要图灵机的全部功能来解决.它们可以用更少的功率解决.我正在寻找功能较弱的编程语言.

是否存在仅限于支持这些功能的高级编程语言:

1. 具有将值推入堆栈并将值从堆栈中弹出的操作的堆栈.

2. 有限状态机(FSM)用于输入值,从状态移动到状态,与堆栈交互以及输出结果.

我意识到我可以使用Java或C或Python(等)并通过编写仅使用堆栈和FSM的程序来约束语言.但是,我正在寻找一种只具备这些功能的编程语言,而不是更多.

换句话说,我不想使用图灵完整的编程语言来解决只需要确定性下推自动机功能的问题.我想使用只具有确定性下推自动机功能的编程语言.

所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.

我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.

它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.

所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.

如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.

如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.

如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.

任何帮助将不胜感激.谢谢.

我如何设计一个接受平衡括号和括号的PDA([] []),我很难入门.我需要帮助编写此问题的转换函数.任何帮助表示赞赏

制作PDA以识别以下语言:包含比b更多的字符串的语言

我几天来一直在努力解决这个问题,我似乎已经完成了一个完整的心理障碍.是否有人能够为我如何解决这个问题提供一些指导或指导？

我想知道是否有人可以对这两个术语之间的关系进行简单的解释，因为我对术语感到非常困惑。

有人可以帮我设计 PDA 吗？n<=m<=2n}。你能设计一个并附上解释吗？