标签: automata

我需要一些帮助来理解如何使用以下内容来制作将用于生成epsilon NFA的正则表达式.

字母是{0,1}

语言是:所有字符串的集合,以101开头,以01010结尾.

有效字符串将是:

• 101010
• 10101010
• 101110101
• 1011101010

我更关心理解如何制作正则表达式.

两种非常规语言的交集可以是常规语言吗？

设计一个图灵机，输入两个非负数并对它们进行模运算，例如 mod(3,7)=3 和 mod(7,3)=1。显然，指定有关 TM 输入和输出的任何假设和格式。

我正在Scala中组建一个基本结构库,用于生产或个人学习.我专注于在类型理论,猫理论,集合论中对所述结构的清晰描述.其中一种类型,

abstract case class Fold[A, B]() {
  type I
  def trans: I => A => I
  def start: I
  def output: I => B

  def cojoin: Fold[A, Fold[A, B]] 
  def copoint: B    
  def dimap[Z, C](f: Z => A, g: B => C): Fold[Z, C]
 }

这是(我很确定)同构的,
(信用:http://www.haskellforall.com/2013/08/composable-streaming-folds.html)

abstract case class Fold'[A, B]() {
  type W
  def MonW: Monoid[W]
  def tally: A => W
  def summerize: W => B
}

对我来说,其中一种类型非常类似于DFA,而在https://www.fpcomplete.com/user/edwardk/cellular-automata/part-2中 ,Kmett先生基本上也说了很多.我的问题是,如果不是 DFA,这种类型是什么？

关于类型类,我有一个奇怪的问题.所以你可以像这样定义一个基本类型:

class Property x where
    checkThing :: x -> Int -> Bool
    transformThing :: x -> x

如果要使用具有多个参数的类型类,可以启用:

{-# LANGUAGE MultiParamTypeClasses #-}

这将让你做以下事情:

class Property x y where
    checkThing :: x -> Int -> Bool
    transformThing :: x -> y -> Int

这是我的问题:想象一下,我想为自动机(可接受语言的那种)编写一个类型类.我会写一个看起来像这样的类型:

class Automata machine where
    isDeterministic :: machine -> Bool
    acceptsInput :: machine -> String -> Bool

自动机接受输入并确定该输入是否是语言的一部分.上述课程适用于此.但等待这个仅限于字符列表(String)如果我想通过Automata进行推广呢？好吧,我可以在我的类定义中添加另一个变量:

class Automata machine alphabet where
    isDeterministic :: machine -> Bool
    acceptsInput :: machine -> [alphabet] -> Bool

嗯那没关系.但字母表可能与机器没有直接关系.我很幸运!我可以启用:

{-# LANGUAGE …