# woaidongmao

## 如何将正则表达式转换为NFA

### 什么是正则表达式？

`Mar(y|k|cus) is son of bitch.`

·                                 连结 (Concatenation)，比如 bitch，由b, i, t, c, h连接而成

·                                 联合 (Union)，比如 y|k|cus，可以认为是yk或者cus

·                                 Kleene Star，比如a*，可以接受空串和若干个a连结组成的串

### 如何转换？

ab:

a*:

a|b:

`PUSH a To automaton stack`
`PUSH b To automaton stack`
`UNION`
`STAR`
`PUSH c To automaton stack`
`CONCAT`
`PUSH d To automaton stack`
`CONCAT`
`POP result`

Star

`POP T from automaton stack`
`CREATE state A, B`
`ADD transition from A to B with 'ε'`
`ADD transition from A to T.entry with 'ε'`
`ADD transition from T.exit to A with 'ε'`
`ADD transition from T.exit to B with 'ε'`
`ADD state A, B to T`
`PUSH T to automaton stack`

Concat

`POP F, S from automaton stack`
`ADD transition from F.exit to S.entry with 'ε'`
`JOIN S to F`
`SET F.exit = S.exit`
`SET F.inputSet += S.inputSet`
`PUSH F to automaton stack`

Union:

`POP F, S from automaton stack`
`CREATE state A, B`
`ADD transition from A to F.entry with 'ε'`
`ADD transition from A to S.entry with 'ε'`
`ADD transition from T.exit to B with 'ε'`
`ADD transition from T.exit to B with 'ε'`
`JOIN S to F`
`ADD state A, B to T`
`SET F.exit = S.exit`
`SET F.inputSet += S.inputSet`
`PUSH F to automaton stack`

posted on 2009-09-29 13:50 肥仔 阅读(2312) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

 只有注册用户登录后才能发表评论。 【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库 相关文章: