10.2. Reconhecendo e analisando linguagens livres de contexto🔗
namespaceParsingdefsplit2{α:Type}:Listα→List(Listα×Listα)|[]=>[([],[])]|x::xs=>([],x::xs)::(split2xs).mapfun(ys,zs)=>(x::ys,zs)[("","Jan"),("J","an"),("Ja","n"),("Jan","")]#evalsplit2"Jan".toList|>.mapλ(a,b)↦(String.ofLista,String.ofListb)defsplitN{α:Type}:Nat→Listα→List(List(Listα))|0,[]=>[[]]|0,_::_=>[]|1,xs=>[[xs]]|n+2,xs=>(split2xs).flatMapfun(ys,zs)=>(splitN(n+1)zs).mapfunrs=>ys::rs[["","","Jan"],["","J","an"],["","Ja","n"],["","Jan",""],["J","","an"],["J","a","n"],["J","an",""],["Ja","","n"],["Ja","n",""],["Jan","",""]]#evalsplitN3"Jan".toList|>.map(·.mapString.ofList)As divisões juntam-se de volta na entradatheoremappend_of_mem_split2{α:Type}:∀{xs:Listα}{p:Listα×Listα},p∈split2xs→p.1++p.2=xsα:Typep:Listα×Listαh:p∈split2[]⊢ p.fst++p.snd=[]α:Typep:Listα×Listαh:p∈split2[]⊢ p.fst++p.snd=[]α:Typep:Listα×Listαh:p=([],[])⊢ p.fst++p.snd=[]All goals completed! 🐙α:Typex:αxs:Listαp:Listα×Listαh:p∈split2(x::xs)⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listαp:Listα×Listαh:p∈split2(x::xs)⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listαp:Listα×Listαh:p=([],x::xs)∨∃a,a∈split2xs∧(x::a.fst,a.snd)=p⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listα⊢ ([],x::xs).fst++([],x::xs).snd=x::xsα:Typex:αxs:Listαys:Listαzs:Listαh:(ys,zs)∈split2xs⊢ (x::(ys,zs).fst,(ys,zs).snd).fst++(x::(ys,zs).fst,(ys,zs).snd).snd=x::xsα:Typex:αxs:Listα⊢ ([],x::xs).fst++([],x::xs).snd=x::xsAll goals completed! 🐙α:Typex:αxs:Listαys:Listαzs:Listαh:(ys,zs)∈split2xs⊢ (x::(ys,zs).fst,(ys,zs).snd).fst++(x::(ys,zs).fst,(ys,zs).snd).snd=x::xsAll goals completed! 🐙theoremflatten_of_mem_splitN{α:Type}:∀{n:Nat}{xs:Listα}{l:List(Listα)},l∈splitNnxs→l.flatten=xsα:Typex✝:Listαl:List(Listα)h:l∈splitN1x✝⊢ l.flatten=x✝α:Typel:List(Listα)h:l∈splitN0[]⊢ l.flatten=[]α:Typex✝:Listαl:List(Listα)h:l∈splitN1x✝⊢ l.flatten=x✝α:Typex✝:Listαl:List(Listα)h:l=[x✝]⊢ l.flatten=x✝All goals completed! 🐙α:Typehead✝:αtail✝:Listαx✝:List(Listα)h:x✝∈splitN0(head✝::tail✝)⊢ x✝.flatten=head✝::tail✝α:Typehead✝:αtail✝:Listαx✝:List(Listα)h:x✝∈splitN0(head✝::tail✝)⊢ x✝.flatten=head✝::tail✝All goals completed! 🐙α:Typen:Natxs:Listαl:List(Listα)h:l∈splitN(n+2)xs⊢ l.flatten=xsα:Typen:Natxs:Listαl:List(Listα)h:l∈splitN(n+2)xs⊢ l.flatten=xsα:Typen:Natxs:Listαl:List(Listα)h:∃a,a∈split2xs∧∃a_1,a_1∈splitN(n+1)a.snd∧a.fst::a_1=l⊢ l.flatten=xsα:Typen:Natxs:Listαys:Listαzs:Listαh1:(ys,zs)∈split2xsrs:List(Listα)h2:rs∈splitN(n+1)(ys,zs).snd⊢ ((ys,zs).fst::rs).flatten=xsAll goals completed! 🐙defrecognize(xs:ListChar):Bool:=xs==[]||xs==['a']||xs==['b']||xs==['c']||(splitN3xs).attach.anyfun|⟨[['a'],ys,['a']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|⟨[['b'],ys,['b']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|⟨[['c'],ys,['c']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|_=>falsetermination_byxs.lengthdecreasing_byall_goalsxs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:[['c'],ys,['c']].flatten.length=xs.length⊢ ys.length<xs.lengthxs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:ys.length+1+1=xs.length⊢ ys.length<xs.lengthAll goals completed! 🐙true#evalrecognize"aabcbbcbaa".toListfalse#evalrecognize"aabcbbcba".toListdefgener{α:Type}:Nat→Listα→List(Listα)|0,_=>[[]]|n+1,alphabet=>alphabet.flatMapfunx=>(genernalphabet).map(x::·)defgenerUpTo{α:Type}(n:Nat)(alphabet:Listα):List(Listα):=(List.range(n+1)).flatMapfunk=>generkalphabet["","a","b","c","aa","bb","cc","aaa","aba","aca","bab","bbb","bcb","cac","cbc","ccc"]#eval((generUpTo3"abc".toList).filterrecognize).mapString.ofListO reconhecedor e a definição de palíndromotheoremmem_split2_append{α:Type}:∀yszs:Listα,(ys,zs)∈split2(ys++zs)α:Type⊢ ([],[])∈split2([]++[])α:Type⊢ ([],[])∈split2([]++[])All goals completed! 🐙α:Typez:αzs:Listα⊢ ([],z::zs)∈split2([]++z::zs)α:Typez:αzs:Listα⊢ ([],z::zs)∈split2([]++z::zs)All goals completed! 🐙α:Typey:αys:Listαzs:Listα⊢ (y::ys,zs)∈split2(y::ys++zs)α:Typey:αys:Listαzs:Listα⊢ (y::ys,zs)∈split2(y::ys++zs)α:Typey:αys:Listαzs:Listα⊢ (y::ys,zs)=([],y::(ys++zs))∨∃a,a∈split2(ys++zs)∧(y::a.fst,a.snd)=(y::ys,zs)All goals completed! 🐙theoremmem_splitN_flatten{α:Type}:∀l:List(Listα),l∈splitNl.lengthl.flattenα:Type⊢ []∈splitN[].length[].flattenα:Type⊢ []∈splitN[].length[].flattenAll goals completed! 🐙α:Typeys:Listα⊢ [ys]∈splitN[ys].length[ys].flattenα:Typeys:Listα⊢ [ys]∈splitN[ys].length[ys].flattenAll goals completed! 🐙α:Typeys:Listαzs:Listαrs:List(Listα)⊢ ys::zs::rs∈splitN(ys::zs::rs).length(ys::zs::rs).flattenα:Typeys:Listαzs:Listαrs:List(Listα)⊢ ys::zs::rs∈splitN(ys::zs::rs).length(ys::zs::rs).flattenα:Typeys:Listαzs:Listαrs:List(Listα)⊢ ys::zs::rs∈splitN(rs.length+1+1)(ys++(zs++rs.flatten))α:Typeys:Listαzs:Listαrs:List(Listα)⊢ ∃a,a∈split2(ys++(zs++rs.flatten))∧∃a_1,a_1∈splitN(rs.length+1)a.snd∧a.fst::a_1=ys::zs::rsrefine⟨(ys,(zs::rs).flatten),α:Typeys:Listαzs:Listαrs:List(Listα)⊢ (ys,(zs::rs).flatten)∈split2(ys++(zs++rs.flatten))All goals completed! 🐙,zs::rs,?_,rfl⟩All goals completed! 🐙theoremrecognize_sound(n:Nat):∀w:ListChar,w.length≤n→recognizew→w.Palindrome:=n:Nat⊢ ∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromeinductionnwith⊢ ∀(w:ListChar),w.length≤0→recognizew=true→w.Palindromew:ListCharhw:w.length≤0hr:recognizew=true⊢ w.Palindromew:ListCharhr:recognizew=truehw:w=[]⊢ w.Palindromezerow:ListCharhr:recognizew=truehw:w=[]⊢ [].Palindromeexact.nilAll goals completed! 🐙|succnih=>succn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindrome⊢ ∀(w:ListChar),w.length≤n+1→recognizew=true→w.Palindromeintrowhwhsuccn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1h:recognizew=true⊢ w.Palindromerw[recognizesuccn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1h:(w==[]||w==['a']||w==['b']||w==['c']||(splitN3w).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true⊢ w.Palindrome]athsuccn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1h:(w==[]||w==['a']||w==['b']||w==['c']||(splitN3w).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true⊢ w.Palindromesimponly[Bool.or_eq_true,beq_iff_eq,List.any_eq_true]athsuccn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1h:(((w=[]∨w=['a'])∨w=['b'])∨w=['c'])∨∃x,x∈(splitN3w).attach∧(matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true⊢ w.Palindromercaseshwith(((rfl|rfl)|rfl)|rfl)|⟨⟨l,hl⟩,_,hm⟩succ.inl.inl.inl.inln:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:[].length≤n+1⊢ [].Palindromesucc.inl.inl.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['a'].length≤n+1⊢ ['a'].Palindromesucc.inl.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['b'].length≤n+1⊢ ['b'].Palindromesucc.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['c'].length≤n+1⊢ ['c'].Palindromesucc.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachhm:(match⟨l,hl⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true⊢ w.Palindrome·succ.inl.inl.inl.inln:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:[].length≤n+1⊢ [].Palindromeexact.nilAll goals completed! 🐙·succ.inl.inl.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['a'].length≤n+1⊢ ['a'].Palindromeexact.singleton_All goals completed! 🐙·succ.inl.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['b'].length≤n+1⊢ ['b'].Palindromeexact.singleton_All goals completed! 🐙·succ.inl.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromehw:['c'].length≤n+1⊢ ['c'].Palindromeexact.singleton_All goals completed! 🐙·succ.inrn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachhm:(match⟨l,hl⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true⊢ w.Palindromesplitathmh_1n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['a'],ys✝,['a']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['a'],ys✝,['a']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_2n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['b'],ys✝,['b']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['b'],ys✝,['b']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_4n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝³:{x//x∈splitN3w}x✝²:∀(ys:ListChar)(h:[['a'],ys,['a']]∈splitN3w),⟨l,hl⟩=⟨[['a'],ys,['a']],h⟩→Falsex✝¹:∀(ys:ListChar)(h:[['b'],ys,['b']]∈splitN3w),⟨l,hl⟩=⟨[['b'],ys,['b']],h⟩→Falsex✝:∀(ys:ListChar)(h:[['c'],ys,['c']]∈splitN3w),⟨l,hl⟩=⟨[['c'],ys,['c']],h⟩→Falsehm:false=true⊢ w.Palindrome<;>h_1n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['a'],ys✝,['a']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['a'],ys✝,['a']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_2n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['b'],ys✝,['b']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['b'],ys✝,['b']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_4n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝³:{x//x∈splitN3w}x✝²:∀(ys:ListChar)(h:[['a'],ys,['a']]∈splitN3w),⟨l,hl⟩=⟨[['a'],ys,['a']],h⟩→Falsex✝¹:∀(ys:ListChar)(h:[['b'],ys,['b']]∈splitN3w),⟨l,hl⟩=⟨[['b'],ys,['b']],h⟩→Falsex✝:∀(ys:ListChar)(h:[['c'],ys,['c']]∈splitN3w),⟨l,hl⟩=⟨[['c'],ys,['c']],h⟩→Falsehm:false=true⊢ w.Palindrome(trycontradictionAll goals completed! 🐙)<;>h_1n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['a'],ys✝,['a']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['a'],ys✝,['a']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_2n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['b'],ys✝,['b']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['b'],ys✝,['b']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromeh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=true⊢ w.Palindrome·h_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys✝:ListCharh✝:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromerename_iyshys_h_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys:ListCharhys:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=true⊢ w.Palindromehavehe:=flatten_of_mem_splitNhysh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys:ListCharhys:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=truehe:[['c'],ys,['c']].flatten=w⊢ w.Palindromesimpatheh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromew:ListCharhw:w.length≤n+1l:List(ListChar)hl:l∈splitN3wleft✝:⟨l,hl⟩∈(splitN3w).attachx✝:{x//x∈splitN3w}ys:ListCharhys:[['c'],ys✝,['c']]∈splitN3wheq✝:⟨l,hl⟩=⟨[['c'],ys✝,['c']],h✝⟩hm:recognizeys✝=truehe:'c'::(ys++['c'])=w⊢ w.Palindromesubstheh_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromel:List(ListChar)ys:ListCharhm:recognizeys✝=truehw:('c'::(ys++['c'])).length≤n+1hl:l∈splitN3('c'::(ys++['c']))left✝:⟨l,hl⟩∈(splitN3('c'::(ys++['c']))).attachx✝:{x//x∈splitN3('c'::(ys++['c']))}hys:[['c'],ys,['c']]∈splitN3('c'::(ys++['c']))heq✝:⟨l,hl⟩=⟨[['c'],ys,['c']],hys⟩⊢ ('c'::(ys++['c'])).PalindromeapplyList.Palindrome.cons_concath_3n:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromel:List(ListChar)ys:ListCharhm:recognizeys✝=truehw:('c'::(ys++['c'])).length≤n+1hl:l∈splitN3('c'::(ys++['c']))left✝:⟨l,hl⟩∈(splitN3('c'::(ys++['c']))).attachx✝:{x//x∈splitN3('c'::(ys++['c']))}hys:[['c'],ys,['c']]∈splitN3('c'::(ys++['c']))heq✝:⟨l,hl⟩=⟨[['c'],ys,['c']],hys⟩⊢ ys.Palindromeexactihys(byn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromel:List(ListChar)ys:ListCharhm:recognizeys✝=truehw:('c'::(ys++['c'])).length≤n+1hl:l∈splitN3('c'::(ys++['c']))left✝:⟨l,hl⟩∈(splitN3('c'::(ys++['c']))).attachx✝:{x//x∈splitN3('c'::(ys++['c']))}hys:[['c'],ys,['c']]∈splitN3('c'::(ys++['c']))heq✝:⟨l,hl⟩=⟨[['c'],ys,['c']],hys⟩⊢ ys.length≤nsimpathwn:Natih:∀(w:ListChar),w.length≤n→recognizew=true→w.Palindromel:List(ListChar)ys:ListCharhm:recognizeys✝=truehl:l∈splitN3('c'::(ys++['c']))left✝:⟨l,hl⟩∈(splitN3('c'::(ys++['c']))).attachx✝:{x//x∈splitN3('c'::(ys++['c']))}hys:[['c'],ys,['c']]∈splitN3('c'::(ys++['c']))heq✝:⟨l,hl⟩=⟨[['c'],ys,['c']],hys⟩hw:ys.length+1≤n⊢ ys.length≤n;omegaAll goals completed! 🐙)hmtheoremrecognize_complete(n:Nat):∀w:ListChar,w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=true:=byn:Nat⊢ ∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=trueinductionnwith|zero=>zero⊢ ∀(w:ListChar),w.length≤0→w⊆"abc".toList→w.Palindrome→recognizew=trueintrowhw__zerow:ListCharhw:w.length≤0a✝¹:w⊆"abc".toLista✝:w.Palindrome⊢ recognizew=truesimpathwzerow:ListChara✝¹:w⊆"abc".toLista✝:w.Palindromehw:w=[]⊢ recognizew=truesubsthwzeroa✝¹:[]⊆"abc".toLista✝:[].Palindrome⊢ recognize[]=truerw[recognizezeroa✝¹:[]⊆"abc".toLista✝:[].Palindrome⊢ ([]==[]||[]==['a']||[]==['b']||[]==['c']||(splitN3[]).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true]zeroa✝¹:[]⊆"abc".toLista✝:[].Palindrome⊢ ([]==[]||[]==['a']||[]==['b']||[]==['c']||(splitN3[]).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesimpAll goals completed! 🐙|succnih=>succn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=true⊢ ∀(w:ListChar),w.length≤n+1→w⊆"abc".toList→w.Palindrome→recognizew=trueintrowhwhahpsuccn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truew:ListCharhw:w.length≤n+1ha:w⊆"abc".toListhp:w.Palindrome⊢ recognizew=truecaseshpwith|nil=>succ.niln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:[].length≤n+1ha:[]⊆"abc".toList⊢ recognize[]=truerw[recognizesucc.niln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:[].length≤n+1ha:[]⊆"abc".toList⊢ ([]==[]||[]==['a']||[]==['b']||[]==['c']||(splitN3[]).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true]succ.niln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:[].length≤n+1ha:[]⊆"abc".toList⊢ ([]==[]||[]==['a']||[]==['b']||[]==['c']||(splitN3[]).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesimpAll goals completed! 🐙|singletonx=>succ.singletonn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charhw:[x].length≤n+1ha:[x]⊆"abc".toList⊢ recognize[x]=truehavehx:x∈"abc".toList:=ha(byn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charhw:[x].length≤n+1ha:[x]⊆"abc".toList⊢ x∈[x]simpAll goals completed! 🐙)succ.singletonn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charhw:[x].length≤n+1ha:[x]⊆"abc".toListhx:x∈"abc".toList⊢ recognize[x]=truesimpathxsucc.singletonn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charhw:[x].length≤n+1ha:[x]⊆"abc".toListhx:x='a'∨x='b'∨x='c'⊢ recognize[x]=truercaseshxwithrfl|rfl|rflsucc.singleton.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['a'].length≤n+1ha:['a']⊆"abc".toList⊢ recognize['a']=truesucc.singleton.inr.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['b'].length≤n+1ha:['b']⊆"abc".toList⊢ recognize['b']=truesucc.singleton.inr.inrn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['c'].length≤n+1ha:['c']⊆"abc".toList⊢ recognize['c']=true<;>succ.singleton.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['a'].length≤n+1ha:['a']⊆"abc".toList⊢ recognize['a']=truesucc.singleton.inr.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['b'].length≤n+1ha:['b']⊆"abc".toList⊢ recognize['b']=truesucc.singleton.inr.inrn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['c'].length≤n+1ha:['c']⊆"abc".toList⊢ recognize['c']=true(rw[recognizesucc.singleton.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['a'].length≤n+1ha:['a']⊆"abc".toList⊢ (['a']==[]||['a']==['a']||['a']==['b']||['a']==['c']||(splitN3['a']).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true]succ.singleton.inr.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['b'].length≤n+1ha:['b']⊆"abc".toList⊢ (['b']==[]||['b']==['a']||['b']==['b']||['b']==['c']||(splitN3['b']).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesucc.singleton.inr.inrn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truehw:['c'].length≤n+1ha:['c']⊆"abc".toList⊢ (['c']==[]||['c']==['a']||['c']==['b']||['c']==['c']||(splitN3['c']).attach.anyfunx=>matchxwith|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true;simpAll goals completed! 🐙)|cons_concatxhl=>succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl✝:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toList⊢ recognize(x::(l✝++[x]))=truerename_ilsucc.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toList⊢ recognize(x::(l✝++[x]))=truehavehx:x∈"abc".toList:=ha(byn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toList⊢ x∈x::(l++[x])simpAll goals completed! 🐙)succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toList⊢ recognize(x::(l++[x]))=truehavehl':l⊆"abc".toList:=funchc=>ha(byn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListc:Charhc:c∈l⊢ c∈x::(l++[x])simp[hc]All goals completed! 🐙)succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toList⊢ recognize(x::(l++[x]))=truehaveih':=ihl(byn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toList⊢ l.length≤nsimpathwn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromeha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListhw:l.length+1≤n⊢ l.length≤n;omegaAll goals completed! 🐙)hl'hlsucc.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=true⊢ recognize(x::(l++[x]))=truerw[recognizesucc.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=true⊢ (x::(l++[x])==[]||x::(l++[x])==['a']||x::(l++[x])==['b']||x::(l++[x])==['c']||(splitN3(x::(l++[x]))).attach.anyfunx_1=>matchx_1with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true]succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=true⊢ (x::(l++[x])==[]||x::(l++[x])==['a']||x::(l++[x])==['b']||x::(l++[x])==['c']||(splitN3(x::(l++[x]))).attach.anyfunx_1=>matchx_1with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesimponly[Bool.or_eq_true,beq_iff_eq,List.any_eq_true]succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=true⊢ (((x::(l++[x])=[]∨x::(l++[x])=['a'])∨x::(l++[x])=['b'])∨x::(l++[x])=['c'])∨∃x_1,x_1∈(splitN3(x::(l++[x]))).attach∧(matchx_1with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truerightsucc.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=true⊢ ∃x_1,x_1∈(splitN3(x::(l++[x]))).attach∧(matchx_1with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truehavehmem:[[x],l,[x]]∈splitN3(x::(l++[x])):=byn:Nat⊢ ∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truesimpausingmem_splitN_flatten[[x],l,[x]]succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=truehmem:[[x],l,[x]]∈splitN3(x::(l++[x]))⊢ ∃x_1,x_1∈(splitN3(x::(l++[x]))).attach∧(matchx_1with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truerefine⟨⟨_,hmem⟩,List.mem_attach__,?_⟩succ.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhx:x∈"abc".toListhl':l⊆"abc".toListih':recognizel=truehmem:[[x],l,[x]]∈splitN3(x::(l++[x]))⊢ (match⟨[[x],l,[x]],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesimpathxsucc.cons_concatn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truex:Charl:ListCharhl:l✝.Palindromehw:(x::(l✝++[x])).length≤n+1ha:x::(l✝++[x])⊆"abc".toListhl':l⊆"abc".toListih':recognizel=truehmem:[[x],l,[x]]∈splitN3(x::(l++[x]))hx:x='a'∨x='b'∨x='c'⊢ (match⟨[[x],l,[x]],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truercaseshxwithrfl|rfl|rflsucc.cons_concat.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('a'::(l++['a'])).length≤n+1ha:'a'::(l++['a'])⊆"abc".toListhmem:[['a'],l,['a']]∈splitN3('a'::(l++['a']))⊢ (match⟨[['a'],l,['a']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesucc.cons_concat.inr.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('b'::(l++['b'])).length≤n+1ha:'b'::(l++['b'])⊆"abc".toListhmem:[['b'],l,['b']]∈splitN3('b'::(l++['b']))⊢ (match⟨[['b'],l,['b']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesucc.cons_concat.inr.inrn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('c'::(l++['c'])).length≤n+1ha:'c'::(l++['c'])⊆"abc".toListhmem:[['c'],l,['c']]∈splitN3('c'::(l++['c']))⊢ (match⟨[['c'],l,['c']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=true<;>succ.cons_concat.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('a'::(l++['a'])).length≤n+1ha:'a'::(l++['a'])⊆"abc".toListhmem:[['a'],l,['a']]∈splitN3('a'::(l++['a']))⊢ (match⟨[['a'],l,['a']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesucc.cons_concat.inr.inln:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('b'::(l++['b'])).length≤n+1ha:'b'::(l++['b'])⊆"abc".toListhmem:[['b'],l,['b']]∈splitN3('b'::(l++['b']))⊢ (match⟨[['b'],l,['b']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesucc.cons_concat.inr.inrn:Natih:∀(w:ListChar),w.length≤n→w⊆"abc".toList→w.Palindrome→recognizew=truel:ListCharhl:l✝.Palindromehl':l⊆"abc".toListih':recognizel=truehw:('c'::(l++['c'])).length≤n+1ha:'c'::(l++['c'])⊆"abc".toListhmem:[['c'],l,['c']]∈splitN3('c'::(l++['c']))⊢ (match⟨[['c'],l,['c']],hmem⟩with|⟨[['a'],ys,['a']],h⟩=>recognizeys|⟨[['b'],ys,['b']],h⟩=>recognizeys|⟨[['c'],ys,['c']],h⟩=>recognizeys|x=>false)=truesimpausingih'All goals completed! 🐙theoremrecognize_iff_palindrome(w:ListChar)(hw:w⊆"abc".toList):recognizew↔w.Palindrome:=⟨recognize_sound_w(Nat.le_refl_),recognize_complete_w(Nat.le_refl_)hw⟩theoremsubset_of_mem_gener{α:Type}(alphabet:Listα):∀nw,w∈genernalphabet→w⊆alphabet|0,w,h=>α:Typealphabet:Listαw:Listαh:w∈gener0alphabet⊢ w⊆alphabetbyα:Typealphabet:Listαw:Listαh:w∈gener0alphabet⊢ w⊆alphabetsimp[gener]athα:Typealphabet:Listαw:Listαh:w=[]⊢ w⊆alphabetsimp[h]All goals completed! 🐙|n+1,w,h=>α:Typealphabet:Listαn:Natw:Listαh:w∈gener(n+1)alphabet⊢ w⊆alphabetbyα:Typealphabet:Listαn:Natw:Listαh:w∈gener(n+1)alphabet⊢ w⊆alphabetsimponly[gener,List.mem_flatMap,List.mem_map]athα:Typealphabet:Listαn:Natw:Listαh:∃a,a∈alphabet∧∃a_1,a_1∈genernalphabet∧a::a_1=w⊢ w⊆alphabetobtain⟨x,hx,v,hv,rfl⟩:=hα:Typealphabet:Listαn:Natx:αhx:x∈alphabetv:Listαhv:v∈genernalphabet⊢ x::v⊆alphabetintrochcα:Typealphabet:Listαn:Natx:αhx:x∈alphabetv:Listαhv:v∈genernalphabetc:αhc:c∈x::v⊢ c∈alphabetsimpathcα:Typealphabet:Listαn:Natx:αhx:x∈alphabetv:Listαhv:v∈genernalphabetc:αhc:c=x∨c∈v⊢ c∈alphabetrcaseshcwithrfl|hcinlα:Typealphabet:Listαn:Natv:Listαhv:v∈genernalphabetc:αhx:c∈alphabet⊢ c∈alphabetinrα:Typealphabet:Listαn:Natx:αhx:x∈alphabetv:Listαhv:v∈genernalphabetc:αhc:c∈v⊢ c∈alphabet·inlα:Typealphabet:Listαn:Natv:Listαhv:v∈genernalphabetc:αhx:c∈alphabet⊢ c∈alphabetexacthxAll goals completed! 🐙·inrα:Typealphabet:Listαn:Natx:αhx:x∈alphabetv:Listαhv:v∈genernalphabetc:αhc:c∈v⊢ c∈alphabetexactsubset_of_mem_generalphabetnvhvhcAll goals completed! 🐙theoremrecognize_generUpTo(n:Nat):∀w∈generUpTon"abc".toList,recognizew=true↔w.Palindrome:=byn:Nat⊢ ∀(w:ListChar),w∈generUpTon"abc".toList→(recognizew=true↔w.Palindrome)introwhwn:Natw:ListCharhw:w∈generUpTon"abc".toList⊢ recognizew=true↔w.Palindromesimponly[generUpTo,List.mem_flatMap]athwn:Natw:ListCharhw:∃a,a∈List.range(n+1)∧w∈genera"abc".toList⊢ recognizew=true↔w.Palindromeobtain⟨k,_,hk⟩:=hwn:Natw:ListChark:Natleft✝:k∈List.range(n+1)hk:w∈generk"abc".toList⊢ recognizew=true↔w.Palindromeexactrecognize_iff_palindromew(subset_of_mem_gener_kwhk)All goals completed! 🐙defparse(xs:ListChar):List(ParseTreeCharChar):=(ifxs==[]then[.ep]else[])++(ifxs==['a']then[.leaf'a']else[])++(ifxs==['b']then[.leaf'b']else[])++(ifxs==['c']then[.leaf'c']else[])++(splitN3xs).attach.flatMapfun|⟨[['a'],ys,['a']],_h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'a',t,.leaf'a']|⟨[['b'],ys,['b']],_h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'b',t,.leaf'b']|⟨[['c'],ys,['c']],_h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'c',t,.leaf'c']|_=>[]termination_byxs.lengthdecreasing_byall_goalshave:=congrArgList.length(flatten_of_mem_splitN_h)xs:ListCharys:ListChar_h:[['c'],ys,['c']]∈splitN3xsthis:[['c'],ys,['c']].flatten.length=xs.length⊢ ys.length<xs.lengthsimpatthisxs:ListCharys:ListChar_h:[['c'],ys,['c']]∈splitN3xsthis:ys.length+1+1=xs.length⊢ ys.length<xs.lengthomegaAll goals completed! 🐙[[.A a [.A a b a] a]]
#evalIO.println(parse"aabaa".toList)[[.A a [.A a [.A b [] b] a] a]]
#evalIO.println(parse"aabbaa".toList)[]
#evalIO.println(parse"aabcbbcba".toList)
Exercício★★(split-nonempty)
Numa gramática sem regras ε, nenhum pedaço da divisão pode ser vazio.
Defina split2' e splitN', que dão só as divisões sem pedaços vazios.
Confira o resultado em "Jan".