- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试在 Agda 中形式化正则表达式 (RE) 的某些属性。我一直坚持 Kleene 星操作的幂等性证明。
我已经证明了这一点
xs <-[[ (e *) * ]] -> xs <-[[ e * ]]
即如果字符串 xs
是 RE (e *) *
的语言,那么它应该是 e *
。我的问题是如何证明对方? (lemmaKleeneIdem
中的漏洞)
xs <-[[ e * ]] -> xs <-[[ (e *) * ]]
这是我的形式化的一部分:
open import Data.List as List
open import Data.List.Properties
open List-solver renaming (nil to :[] ; _⊕_ to _:++_; _⊜_ to _:==_)
open import Data.Product renaming (_×_ to _*_)
open import Relation.Binary
open import Relation.Binary.PropositionalEquality renaming (_≡_ to _==_)
open import Relation.Nullary renaming (¬_ to not)
module Test {Token : Set}(eqTokenDec : Decidable {A = Token} _==_) where
infixr 5 _+_
infixr 6 _o_
infixl 7 _*
data RegExp : Set where
Emp : RegExp
Eps : RegExp
#_ : (a : Token) -> RegExp
_o_ : (e e' : RegExp) -> RegExp
_+_ : (e e' : RegExp) -> RegExp
_* : (e : RegExp) -> RegExp
-- regular expression membership
infix 3 _<-[[_]]
infixr 6 _*_<=_
infixr 6 _<+_ _+>_
data _<-[[_]] : List Token -> RegExp -> Set where
Eps : List.[] <-[[ Eps ]] -- epsilon: empty string
#_ : (a : Token) -> List.[ a ] <-[[ # a ]] -- single token
_*_<=_ : {xs ys zs : List Token}{e e' : RegExp} -- concatenation of two REs
(pr : xs <-[[ e ]])(pr' : ys <-[[ e' ]])
(eq : zs == xs ++ ys) -> zs <-[[ e o e' ]]
_<+_ : {xs : List Token}{e : RegExp}(e' : RegExp) -- choice left
-> (pr : xs <-[[ e ]]) -> xs <-[[ e + e' ]]
_+>_ : {xs : List Token}{e' : RegExp}(e : RegExp) -- choice right
-> (pr : xs <-[[ e' ]]) -> xs <-[[ e + e' ]]
_* : {xs : List Token}{e : RegExp} -> -- Kleene star
xs <-[[ Eps + e o e * ]] ->
xs <-[[ e * ]]
-- regular expression equivalence
infix 4 _:=:_
_:=:_ : forall (e e' : RegExp) -> Set
e :=: e' = forall (xs : List Token) -> (((pr : xs <-[[ e ]]) -> (xs <-[[ e' ]])) *
((pr : xs <-[[ e' ]]) -> (xs <-[[ e ]])))
subsetLemma : forall {xs} e -> xs <-[[ e ]] -> xs <-[[ e * ]]
subsetLemma {xs = xs} e pr = (_ +> pr * ((_ <+ Eps) *) <= solve 1 (\ xs -> xs :== xs :++ :[]) refl xs) *
lemmaKleeneIdem : (e : RegExp) -> e * :=: (e *) *
lemmaKleeneIdem e xs = subsetLemma (e *) , ?
任何关于我应该如何继续完成此证明的提示将不胜感激。
最佳答案
只是分享解决方案:
lemmaKleeneIdem : (e : RegExp) -> e * :=: (e *) *
lemmaKleeneIdem e xs = subsetLemma (e *) , subsetLemma' e
where
mem : forall {xs e} -> xs <-[[ e ]] -> List _
mem {xs = xs} _ = xs
assoc1 : forall {A : Set}(xs ys zs : List A) -> (xs ++ ys) ++ zs == xs ++ (ys ++ zs)
assoc1 = solve 3 (\ xs ys zs -> (xs :++ ys) :++ zs :== xs :++ (ys :++ zs)) refl
lem' : forall {xs ys zs} e -> zs == xs ++ ys -> xs <-[[ e ]] -> ys <-[[ e * ]] -> zs <-[[ e * ]]
lem' e refl pr pr' = (_ +> pr * pr' <= refl) *
lem : forall {xs ys zs} e -> zs == xs ++ ys -> xs <-[[ e * ]] -> ys <-[[ e * ]] -> zs <-[[ e * ]]
lem e refl ((.(e o e *) <+ Eps) *) q = q
lem e eq ((.Eps +> p * p₁ <= refl) *) q rewrite assoc1 (mem p) (mem p₁) (mem q)
= lem' e eq p (lem e refl p₁ q)
subsetLemma' : forall {xs} e -> xs <-[[ e * * ]] -> xs <-[[ e * ]]
subsetLemma' e ((.(e * o e * *) <+ pr) *) = ((e o e *) <+ pr) *
subsetLemma' e ((.Eps +> pr * pr₁ <= eq) *) = lem e eq pr (subsetLemma' e pr₁)
subsetLemma : forall {xs} e -> xs <-[[ e ]] -> xs <-[[ e * ]]
subsetLemma {xs = xs} e pr = (_ +> pr * ((_ <+ Eps) *) <= solve 1 (\ xs -> xs :== xs :++ :[]) refl xs) *
关于regex - 正则表达式中 Kleene 星幂等性的形式化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34374016/
假设我们有两种语言 L1 和 L2,下面的条件是否被认为是错误的? (L1L2)* = L1*L2* 我假设这是因为说: 条件左侧: L1 = {a,b} L2 = {c,d} C = L1.L2 C
我正在尝试在 Agda 中形式化正则表达式 (RE) 的某些属性。我一直坚持 Kleene 星操作的幂等性证明。 我已经证明了这一点 xs xs xs RegExp _o_ : (e e
我一直在努力理解关于关闭两个联合表达式的一个关键属性。基本上我需要知道 Kleene star 是如何工作的。 I.E 如果正则表达式 R = (0+1)* 表达式的计算结果是否必须类似于 00011
我正在寻找提供解决此问题的算法的引用资料: 问题:给定一个有限字母表 Σ 和一个有限语言 L ⊆ Σ* ,判断 L* 是否是一个自由幺半群。 同样,问题是在给定一组有限的字符串的情况下,确定这些字符串
刚开始欣赏正则表达式,我正在 regexone.com 上练习我的问题给出了关于 kleene "*"的解释。我自己想出了一个答案” [a-c]* 但是解决方法是: aa+b*c+ or a*b*c*
这看起来很简单,也许我遗漏了一些明显的东西。我想返回具有模式 (.*) 的字符串中的所有可变长度子字符串。不过,我发现我在 Firefox 控制台中出现了非常奇怪的行为: "666677888".ma
我正在学习自动机。你能帮我理解带 Kleene 闭包的自动机是如何工作的吗?假设我有字母 a、b、c,我需要找到以 Kleene 星号结尾的文本 - 例如 ab*bac - 它如何工作? 最佳答案 问
大多数来源,例如 http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html ,建议用 4 个节点构建 Kleene 闭
我最近开始使用 Racket 模式匹配系统,并遇到了一个我无法理解的问题。 如果我这样做: (match (list 1 2 3 4 5 6 7 8 9 10 11 12) [(list _
我试图为某人回答正则表达式问题,但遇到了一些让我摸不着头脑的事情。给出以下代码... public static void main(String[] args) throws IOException
(aa)*会有区别吗和 (a*a*) ? 有分配属性吗? 最佳答案 Kleene 星不分布。 (ab)*与 (a*b*) 非常不同. 在您的具体示例中,(aa)*将匹配两组 a s(因此,它只匹配 a
在过去的几周里,我学到了很多关于这方面的知识,但还不够。下面的代码可以编译运行,但是 TEST_ADAPT 中的代码不完整,我不确定如何建立连接。 对象是解析成一个没有variant依赖的plane
我有一个语法,它应该匹配字符序列后跟一个字符,该字符是第一个字符的子集。例如, boost::spirit::qi::rule grammar = *char_('a', 'z') >> char_(
我是 boost::spirit 的新手,正在尝试使用 x3 编写一个简单的解析器。我收到一个无法解释的错误。出于某种原因,我收到有关 boost::spirit::x3::unused_type 的
我想解析特殊的结构,把剩下的扔掉。但我不想使用 skipper 。 我想获得这些构造的 vector ,所以我使用 Kleene Star 解析器作为主要规则。但是,每当有东西被丢弃时,一个默认构造的
我想解析特殊的结构,把剩下的扔掉。但我不想使用 skipper 。 我想获得这些构造的 vector ,所以我使用 Kleene Star 解析器作为主要规则。但是,每当有东西被丢弃时,一个默认构造的
我们这里的问题是表明 在测试中使用 Kleene 代数。 在 b 的值由 p 保留的情况下,我们有交换条件 bp = pb;两个程序之间的等价性简化为等式 在 b 的值不被 p 保留的情况下,我们有交
特别是,这可以用 Javascript 实现吗? >> "Version 1.2.3.4".match(/\S+ (\d+)(\.\d+)*/) ["Version 1.2.3.4", "1", ".
这是一段非常简单的代码,它使用 boost::spirit::karma 以 graphviz 点语言生成格式化输出: #include #include #include #include
我是一名优秀的程序员,十分优秀!