有限自动机和正则表达式的问题

Darth_EF · 发表于 2021-7-27 16:54:51

您需要登录才可以下载或查看，没有账号？立即注册

x

正则表达式 /(.*).*\1/
怎么用有限自动机表示

人造人 · 发表于 2021-7-27 18:09:59

首先需要明确的一个问题是
/(.*).*\1/
/.*/
这两个正则表达式是不是等价的？

Darth_EF · 发表于 2021-7-27 22:47:45

本帖最后由 Darth_EF 于 2021-7-27 22:51 编辑

人造人发表于 2021-7-27 18:09
首先需要明确的一个问题是
/(.*).*\1/
/.*/

并不是等价的.
我一开始也很诧异，但是跑了之后却发现
/(.*).*\1/.exec("test1 asdqwezxc test1") 正则表达式里的第一个括号会捕获到 "test1"

无标题.png

人造人 · 发表于 2021-7-27 22:57:29

Darth_EF 发表于 2021-7-27 22:47
并不是等价的.
我一开始也很诧异，但是跑了之后却发现
/(.*).*\1/.exec("test1 asdqwezxc test1") 正 ...

从这个图片上怎么能看出不等价？
还有，你图片上的正则表达式是 /^(.*).*\1$/ 不是 /(.*).*\1/

人造人 · 发表于 2021-7-27 23:01:14

.* 表示 0 次或多次，可以是 0 次

Darth_EF · 发表于 2021-7-29 17:42:12

人造人发表于 2021-7-27 22:57
从这个图片上怎么能看出不等价？
还有，你图片上的正则表达式是 /^(.*).*\1$/ 不是 /(.*).*\1/

正则表达式捕获的结果不一样啊
还有，有没有^$并不是重点

人造人 · 发表于 2021-7-29 17:48:13

Darth_EF 发表于 2021-7-29 17:42
正则表达式捕获的结果不一样啊
还有，有没有^$并不是重点

换一个问题
/(.*).*\1/
/.*/
第一个正则表达式不能匹配哪一个字符串
如果你找不到一个字符串是第一个正则表达式不能匹配的
那么就意味着，这两个正则表达式是等价的，因为第二个正则表达式可以匹配任意的字符串
第一个正则表达式不能匹配什么样的字符串？

账号		自动登录	找回密码
密码			立即注册