0

问这么简单的问题让我感觉很糟糕,但我无法终生解决这个问题。我需要构建一个基于某些语言的 NFA,我唯一想不通的是这个:

L = (10)*

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

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

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

任何帮助是极大的赞赏。

4

3 回答 3

4

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

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

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

0
1
01
11
010
01010
101
10101
(etc.)

这有帮助吗?

于 2010-08-29T22:32:28.157 回答
2

您对含义的信念基本上是正确的,但并非所有内容都匹配。

与您通常的正则表达式库不同,当我们处理这样的语言理论时,正则表达式必须匹配整个字符串。因此,ε(空字符串)在语言中,10 在语言中,1010 在语言中,等等 - 完全由重复 0 次或更多次的字符串“10”组成的所有内容。

但是,01不在语言中;该字符串不包含重复 0 次或更多次的字符串“10”。1 也不是语言,你错过了最后的 0。

我不知道您是否已经涵盖了这部分,但是如果您将该正则表达式转换为 NFA(或 DFA,这个不需要非确定性),您基本上会得到这个(稍微简化,如果我正确地记得我的转换算法,但从算法到这个的变化非常微不足道):

  1
 ┌─┐
 │ ↓
→a b
 ↑ │
 └─┘
  0

wherea是一个接受状态,而b不是。

这是否有助于您了解为什么它不匹配所有内容?

于 2010-08-29T22:35:54.677 回答
1

这能用吗? http://xenon.stanford.edu/~xusch/regexp/analyzer.html

替代文字

于 2010-08-29T22:16:05.637 回答