计算两个无限正则表达式解决方案集是否不相交

本文介绍了计算两个无限正则表达式解决方案集是否不相交的处理方法,对大家解决问题具有一定的参考价值

问题描述

在计算两个任意正则表达式是否有任何重叠的解决方案(假设有可能).

In calculate if two arbitrary regular expressions have any overlapping solutions (assuming it's possible).

例如,这两个正则表达式可以通过蛮力证明没有交集,因为这两个解集是可计算的,因为它是有限的.

For example these two regular expressions can be shown to have no intersections by brute force because the two solution sets are calculable because it's finite.

^1(11){0,1000}$ ∩     ^(11){0,1000}$        = {}
{1,111, ..., ..111}{11,1111, ..., ...11} = {}
{}                                          = {}

但是将 {0,1000} 替换为 * 消除了暴力解决方案的可能性,因此必须创建更智能的算法.

But replacing the {0,1000} by * remove the possibility for a brute force solution, so a smarter algorithm must be created.

^1(11)*$ ∩ ^(11)*$ = {}
{1,^1(11)*$}{^(11)*$} = {}
{1,^1(11)*$}{11,^11(11)*$} = {}
{1,111,^111(11)*$}{11,^(11)*$} = {}
.....

在另一个 类似问题 一个 答案是计算交集正则表达式.那有可能吗?如果是这样,如何编写算法来做这样的事情?

In another similar question one answer was to calculate the intersection regex. Is that possible to do? If so how would one write an algorithm to do such a thing?

我认为这个问题可能是 停止问题的领域.罢工>

I think this problem might be domain of the halting problem.

我已使用公认的解决方案为示例问题创建 DFA.很容易看出如何在 M_3 的状态图上使用 BFS 或 DFS 来确定来自 M_3 的最终状态是否可达.

I've used the accepted solution to create the DFAs for the example problem. It's fairly easy to see how you can use a BFS or DFS on the graph of states for M_3 to determine if a final state from M_3 is reachable.

推荐答案

不在停机问题的范畴;判断正则语言的交集是否为空可以解决如下:

It is not in the domain of the halting problem; deciding whether the intersection of regular languages is empty or not can be solved as follows:

  1. 为第一语言构建 DFA M1.
  2. 为第二种语言构建一个 DFA M2.提示:Kleene 定理和幂集机器构造
  3. 为 M1 与 M2 相交构造一个 DFA M3.提示:笛卡尔积机器构造
  4. 判断L(M3)是否为空.提示:如果 M3 有 n 个状态,并且 M3 不接受任何长度不大于 n 的字符串,那么 L(M3) 为空……为什么?

这些事情中的每一件事都可以通过算法完成和/或检查.此外,自然地,一旦 DFA 识别出您的语言的交集,您就可以构建一个正则表达式来匹配该语言.如果你从一个正则表达式开始,你可以制作一个 DFA.这绝对是可计算的.

Each of those things can be algorithmically done and/or checked. Also, naturally, once you have a DFA recognizing the intersection of your languages, you can construct a regex to match the language. And if you start out with a regex, you can make a DFA. This is definitely computable.

因此,要构建笛卡尔积机器,您需要两个 DFA.令 M1 = (E, q0, Q1, A1, f1) 和 M2 = (E, q0', Q2, A2, f2).在这两种情况下,E 是输入字母表,q0 是起始状态,Q 是所有状态的集合,A 是接受状态的集合,f 是转移函数.构造 M3 在哪里...

So to build a Cartesian Product Machine, you need two DFAs. Let M1 = (E, q0, Q1, A1, f1) and M2 = (E, q0', Q2, A2, f2). In both cases, E is the input alphabet, q0 is the start state, Q is the set of all states, A is the set of accepting states, and f is the transition function. Construct M3 where...

  1. E3 = E
  2. Q3 = Q1 x Q2(有序对)
  3. q0'' = (q0, q0')
  4. A3 = {(x, y) |A1 中的 x 和 A2 中的 y}
  5. f3(s, (x, y)) = (f1(s, x), f2(s, y))

如果我没有犯任何错误,L(M3) = L(M1) 与 L(M2) 相交.整洁吧?

Provided I didn't make any mistakes, L(M3) = L(M1) intersect L(M2). Neat, huh?

这篇关于计算两个无限正则表达式解决方案集是否不相交的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,WP2

admin_action_{$_REQUEST[‘action’]}

do_action( "admin_action_{$_REQUEST[‘action’]}" )动作钩子::在发送“Action”请求变量时激发。Action Hook: Fires when an ‘action’ request variable is sent.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$_REQUEST['action']引用从GET或POST请求派生的操作。源码(Source)更新版本源码位置使用被使用2.6.0 wp-admin/admin.php:...

日期:2020-09-02 17:44:16 浏览:1127

admin_footer-{$GLOBALS[‘hook_suffix’]}

do_action( "admin_footer-{$GLOBALS[‘hook_suffix’]}", string $hook_suffix )操作挂钩:在默认页脚脚本之后打印脚本或数据。Action Hook: Print scripts or data after the default footer scripts.目录锚点:#说明#参数#源码说明(Description)钩子名的动态部分,$GLOBALS['hook_suffix']引用当前页的全局钩子后缀。参数(Parameters)参数类...

日期:2020-09-02 17:44:20 浏览:1032

customize_save_{$this->id_data[‘base’]}

do_action( "customize_save_{$this->id_data[‘base’]}", WP_Customize_Setting $this )动作钩子::在调用WP_Customize_Setting::save()方法时激发。Action Hook: Fires when the WP_Customize_Setting::save() method is called.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_data...

日期:2020-08-15 15:47:24 浏览:775

customize_value_{$this->id_data[‘base’]}

apply_filters( "customize_value_{$this->id_data[‘base’]}", mixed $default )过滤器::过滤未作为主题模式或选项处理的自定义设置值。Filter Hook: Filter a Customize setting value not handled as a theme_mod or option.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_date['base'],指的是设置...

日期:2020-08-15 15:47:24 浏览:866

get_comment_author_url

过滤钩子:过滤评论作者的URL。Filter Hook: Filters the comment author’s URL.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/comment-template.php:32610...

日期:2020-08-10 23:06:14 浏览:903

network_admin_edit_{$_GET[‘action’]}

do_action( "network_admin_edit_{$_GET[‘action’]}" )操作挂钩:启动请求的处理程序操作。Action Hook: Fires the requested handler action.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$u GET['action']引用请求的操作的名称。源码(Source)更新版本源码位置使用被使用3.1.0 wp-admin/network/edit.php:3600...

日期:2020-08-02 09:56:09 浏览:848

network_sites_updated_message_{$_GET[‘updated’]}

apply_filters( "network_sites_updated_message_{$_GET[‘updated’]}", string $msg )筛选器挂钩:在网络管理中筛选特定的非默认站点更新消息。Filter Hook: Filters a specific, non-default site-updated message in the Network admin.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分$_GET['updated']引用了非默认的...

日期:2020-08-02 09:56:03 浏览:834

pre_wp_is_site_initialized

过滤器::过滤在访问数据库之前是否初始化站点的检查。Filter Hook: Filters the check for whether a site is initialized before the database is accessed.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/ms-site.php:93910...

日期:2020-07-29 10:15:38 浏览:809

WordPress 的SEO 教学:如何在网站中加入关键字(Meta Keywords)与Meta 描述(Meta Description)?

你想在WordPress 中添加关键字和meta 描述吗?关键字和meta 描述使你能够提高网站的SEO。在本文中,我们将向你展示如何在WordPress 中正确添加关键字和meta 描述。为什么要在WordPress 中添加关键字和Meta 描述?关键字和说明让搜寻引擎更了解您的帖子和页面的内容。关键词是人们寻找您发布的内容时,可能会搜索的重要词语或片语。而Meta Description则是对你的页面和文章的简要描述。如果你想要了解更多关于中继标签的资讯,可以参考Google的说明。Meta 关键字和描...

日期:2020-10-03 21:18:25 浏览:1620

谷歌的SEO是什么

SEO (Search Engine Optimization)中文是搜寻引擎最佳化,意思近于「关键字自然排序」、「网站排名优化」。简言之,SEO是以搜索引擎(如Google、Bing)为曝光媒体的行销手法。例如搜寻「wordpress教学」,会看到本站的「WordPress教学:12个课程…」排行Google第一:关键字:wordpress教学、wordpress课程…若搜寻「网站架设」,则会看到另一个网页排名第1:关键字:网站架设、架站…以上两个网页,每月从搜寻引擎导入自然流量,达2万4千:每月「有机搜...

日期:2020-10-30 17:23:57 浏览:1264