代码之家 › 专栏 › 技术社区 › prelic

非常简单的regex表达式说明(10)*

finite-automata regex

0

prelic · 技术社区 · 14 年前

问这么简单的问题让我很难过,但我一辈子都想不出来。我需要基于一些语言构建一个NFA,我唯一无法理解的就是这个:

L = (10)*

请注意,我并没有要求有关FSM的任何帮助,只是对该语言代表的内容进行了一些澄清。其他大多数语言都以一种更易于理解的方式呈现给我:

L = {w | w contains an even number of 0's }

我认为这只是一个正则表达式,在仔细阅读了regex的备忘表之后,我唯一的猜测是它与组匹配 10 0次或更多次,但显然这似乎不正确,因为一切都会匹配。

非常感谢您的帮助。

3 回复 | 直到 14 年前

1

2

Michael Madsen 14 年前

你对意思的信仰基本上是正确的,但不是所有的东西都匹配。

与通常的regex库不同,当我们处理这样的语言理论时,正则表达式必须与 整个的 字符串。所以,_礽(空字符串)是语言,10是语言,1010是语言,等等-所有完全由字符串“10”组成的东西重复0次或更多次。

然而,01是不在语言中,字符串不包含重复0次或更多次的字符串“10”。1也不是语言,您缺少最后0个。

我不知道您是否已经讨论过这一部分,但是如果您将该regex转换为NFA(或DFA,这一部分不需要非确定性),您基本上会得到这个(稍微简化,如果我正确地记得我的转换算法,但这是从算法到这个的一个非常小的变化):

  1
 âââ
 â â
âa b
 â â
 âââ
  0

在哪里? a 是一种接受状态,并且 b 不是。

这有助于你明白为什么它不匹配所有东西吗?

2

4

Jim Lewis 14 年前

这些字符串的语言(10)*:

<empty string>
10
1010
101010
10101010
(etc.)

这些字符串不是语言(10)*:

这有帮助吗?

3

1

Chris 14 年前

alt text