时间戳

首页 > 解决方案 > 将 CFG 转换为正则表达式

regex - 将 CFG 转换为正则表达式

问题描述

这是一个生成 0、1 或 0 和 1 的字符串的 CFG，其排列方式如下(001, 011)，其中一个字符的计数必须比另一个字符大，例如 in00011111或00000111例如。

S → 0S1 | 0A | 0 | 1B | 1
A → 0A | 0
B → 1B | 1

我尝试使用本指南将其转换为正则表达式，但由于0S1在该指南中找不到与它类似的任何内容，我无法转换，因此我被困在这里。

S → 0S1 | 0+ | 0 | 1+ | 1    
A → 0A | 0    = 0+
B → 1B | 1    = 1+

我以前的尝试之一是0+0+1|0+1+1|1+|0+，但它不接受我上面提到的字符串，比如00011111and 00000111。

标签： regexcontext-free-grammarcontext-free-languageautomata-theory

解决方案

即插即用

^(?!01$)(?!0011$)(?!000111$)(?!00001111$)(?=[01]{1,8}$)0*1*$

您无法将其完美地转换为正则表达式，但您可以通过确保输入不具有相同数量的0and来接近1。这最多匹配 8 位数字。

这个怎么运作

  • ^首先你从一行的开头开始
  • (?!01$)确保字符不是01
  • (?!0011$)确保字符不是0011
  • 000111和_00001111
  • 然后确保有从1到8零和一（这是必需的，以确保输入不是由更多的数字组成，例如000000111111，因为它们的对称性没有得到验证）
  • 然后匹配这些零和一直到行尾
  • 对于更长的输入，您需要添加更多文本，最多10 位数字是这样的：（^(?!01$)(?!0011$)(?!000111$)(?!00001111$)(?!0000011111$)(?=[01]{1,10}$)0*1*$您通过添加一个对称验证来跳 2）
  • 仅通过正则表达式无法通过其他方式实现，请参阅说明。

解释

和很容易，正如您所看到的A和。第一个之后的连接也很容易：, , , , 全部混合成一个导致. 问题在于第一个串联。B0+1+S00+011+1(0+|1+)0S1

所以问题可以简化为S = 0S1。这个语法是递归的。但既不是left linear也不是right linear。要识别此语法的输入，您需要“记住”0您找到了多少，以便能够匹配相同数量的1，但是从正则语法（通常和正则表达式）创建的有限状态机可以没有计算历史。它们只是状态和转换，机器从一种状态“跳跃”到另一种状态，并且不记得经过转换的“路径”。

出于这个原因，您需要更强大的机器（如下推自动机），可以从上下文无关语法（如您的）构造。

推荐阅读