标签: finite-automata

是否可以编写与未出现次数的嵌套模式匹配的正则表达式？例如,当外括号内嵌有未知数量的打开/关闭括号时,正则表达式是否可以匹配开括号和右括号？

例如:

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

应该匹配:

{
  if (test)
  {
    // More { }
  }

  // More { }
}

我们需要在C中实现一个简单的状态机.
标准的switch语句是最好的方法吗？
我们有一个当前状态(状态)和转换触发器.

switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

对于简单的状态机是否有更好的方法

编辑:对于C++,我认为Boost Statechart库可能是要走的路.但是,它对C 没有帮助.让我们专注于C用例.

在阅读一些关于递归神经网络的图灵完整性的论文时(例如:使用神经网络进行图灵可计算性,Hava T. Siegelmann和Eduardo D. Sontag,1991),我感觉到那里给出的证据并不是真的那样实际的.例如,参考文献需要神经网络,神经元活动必须具有无限精确性(可靠地表示任何有理数).其他证明需要无限大小的神经网络.显然,这并不是那么实用.

但是我开始怀疑现在是否真的有意义要求图灵的完整性.根据严格的定义,现在没有计算机系统是图灵完整的,因为它们都不能模拟无限的磁带.

有趣的是,如果编程语言规范完整或不完整,那么编程语言规范最常开放.这一切归结为问题,如果它们总是能够分配更多的内存,并且函数调用堆栈大小是无限的.大多数规范并没有真正指定这一点.当然,所有可用的实现都受到限制,因此编程语言的所有实际实现都不是图灵完整的.

所以,你可以说是所有计算机系统都和有限状态机一样强大而不是更多.

这让我想到了这样一个问题:图灵这个词完全有用吗？

回到神经网络:对于神经网络(包括我们自己的大脑)的任何实际实现,它们将无法表示无限数量的状态,即通过严格定义图灵完整性,它们不是图灵完整的.那么神经网络图灵完全是否有意义的问题呢？

他们是否像有限状态机一样强大的问题早已得到了回答(1954年由明斯基回答,答案当然是肯定的)并且似乎也更容易回答.即,至少在理论上,这已经证明它们和任何计算机一样强大.

其他一些问题更多的是我真正想知道的:

• 是否有任何理论术语可以说明计算机的计算能力？(鉴于其有限的存储空间)

• 你怎么能比较神经网络的实际实现与计算机的计算能力？(如上所述,图灵完整性没有用.)

几乎所有使用的编程语言都是图灵完备,虽然这提供了语言来表示任何可计算的算法,但它也有自己的一组问题.看到我写的所有算法都打算停止,我希望能够用一种语言来代表它们,以保证它们会停止.

正则表达式用于匹配字符串和有限状态机在使用时词法,但我不知道是否有这不是图灵完整更普遍的,广泛的语言吗？

编辑:我应该澄清,通过'通用'我不一定希望能够在语言中编写所有停止算法(我不认为这样的语言会存在)但我怀疑有共同的线程停止可以推广的证明,以产生一种语言,保证所有算法都停止.

还有另一种解决这个问题的方法 - 消除理论上无限记忆的需要.一旦限制了机器允许的内存量,机器所处的状态数是有限且可数的,因此您可以确定算法是否会停止(通过不允许机器进入之前的状态) ).

我正在寻找基于其功能和限制的DFA与NFA引擎之间差异的非技术性解释.

有人可以告诉我有限状态传感器是什么吗？

我读过维基百科的文章并且不理解.

我正在寻找解决我的前端小部件代码的方法.有人建议使用有限状态机来思考我正在做的事情.我知道一个状态机模式可以适用于几乎任何问题.我想知道是否有一些经验丰富的UI程序员实际上养成了这个习惯.

所以,问题是 - 你们中的任何一个UI程序员都会在你的工作中考虑状态机吗？如果是这样,怎么样？

谢谢,-Morgan

我最近读过有关boost::statechart库(有限状态机)的内容,我很喜欢这个概念.

C#有类似的机制吗？或者可以使用特定的设计模式实现？

我正在为我的计算类理论做一个家庭作业,对于如何组合2个DFA我有点困惑.这本书说它使用"交叉点结构"这样做,但我不确定那是什么.这里有两个例子:

写一个包含偶数个0或奇数个1的表达式

我把它归结为:

1*(01*01*)* + 0*10*(10*10*)*

其中第一部分表示偶数个0,第二部分表示奇数个1

但是,应该有一个我没有看到的简化解决方案.有小费吗？