Semântica Computacional com Lean

10.2. Reconhecimento e Análise de Linguagens Livres de Contexto🔗

namespace Parsing

Uma gramática pode gerar palavras sobre um alfabeto de caracteres ou sentenças sobre um alfabeto de palavras ou tokens. Dada uma sequência, podemos usar a gramática para responder a duas perguntas.

Chamamos de reconhecimento o procedimento que responde se a sequência pertence à linguagem gerada pela gramática. Na análise, ou parsing, a resposta consiste nas árvores sintáticas que representam as derivações da sequência.

Vamos usar como exemplo a gramática abaixo, que gera os palíndromos sobre {a, b, c}. Um palíndromo é uma palavra igual à que obtemos ao invertê-la.

Uma regra de uma gramática livre de contexto tem um único não terminal à esquerda. Para testar uma regra com n símbolos à direita, dividimos a entrada em n pedaços consecutivos, de todos os modos possíveis. Para cada divisão, testamos se cada símbolo gera o pedaço que lhe corresponde.

A função split2 enumera as divisões em dois pedaços. Para a lista vazia, ela produz uma só divisão, com dois pedaços vazios. Para uma lista não vazia, a primeira divisão é o pedaço vazio seguido da lista inteira. As demais divisões são obtidas dividindo a cauda e recolocando o primeiro elemento no primeiro pedaço. O exemplo usa "Jan".toList para obter os caracteres e String.ofList para exibir os pedaços como textos.

A função splitN n generaliza esse procedimento. Em zero pedaços, só a lista vazia pode ser dividida, e há uma única divisão. Em um pedaço, a única divisão tem a lista inteira como único pedaço. Para dois ou mais pedaços, a função usa split2 para separar o primeiro e divide recursivamente o restante.

A::=ε
|a
|b
|c
|a A a
|b A b
|c A c
def split2 {α : Type} : List α → List (List α × List α) | [] => [([], [])] | x :: xs => ([], x :: xs) :: (split2 xs).map fun (ys, zs) => (x :: ys, zs) [("", "Jan"), ("J", "an"), ("Ja", "n"), ("Jan", "")]#eval split2 "Jan".toList |>.map λ (a, b) ↦ (String.ofList a, String.ofList b) def splitN {α : Type} : Nat → List α → List (List (List α)) | 0, [] => [[]] | 0, Variable name `a` 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] _a Note: This linter can be disabled with `set_option linter.unusedVariables false`a :: Variable name `as` 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] _as Note: This linter can be disabled with `set_option linter.unusedVariables false`as => [] | 1, xs => [[xs]] | n + 2, xs => (split2 xs).flatMap fun (ys, zs) => (splitN (n + 1) zs).map fun rs => ys :: rs [["", "", "Jan"], ["", "J", "an"], ["", "Ja", "n"], ["", "Jan", ""], ["J", "", "an"], ["J", "a", "n"], ["J", "an", ""], ["Ja", "", "n"], ["Ja", "n", ""], ["Jan", "", ""]]#eval splitN 3 "Jan".toList |>.map λ xs => xs.map String.ofList

O reconhecedor aceita diretamente as palavras geradas pelas regras A → ε, A → a, A → b e A → c. Para testar A → a A a, ele procura, entre as divisões de splitN 3 xs, uma que tenha ['a'] nas duas pontas. Se encontrar uma divisão assim, testa recursivamente se o pedaço do meio é um palíndromo. As regras A → b A b e A → c A c seguem o mesmo procedimento.

Na primeira tentativa, recognize₀, o padrão [['a'], ys, ['a']] identifica o pedaço central, mas não carrega a informação de que a divisão veio de splitN 3 xs. O Lean precisa dessa informação para verificar que a chamada sobre ys termina. A definição de recognize usa List.attach para associar cada divisão a uma prova de que ela pertence à lista de divisões.

A cláusula termination_by xs.length indica que a medida usada para justificar a recursão é o comprimento da entrada. A cláusula decreasing_by fornece a prova de que a medida diminui em cada chamada. O lema flatten_of_mem_splitN, no bloco de detalhes, mostra que concatenar os pedaços recupera a entrada. Aplicamos List.length à igualdade com congrArg. Como os dois pedaços externos têm um elemento cada, o pedaço central tem dois elementos a menos do que a entrada.

O mesmo raciocínio explica quando o método funciona para uma regra recursiva à esquerda, como V → V T. Se o pedaço de T tiver ao menos um símbolo, o pedaço de V é menor que a entrada. Se o pedaço de T for vazio, uma chamada para V sobre o primeiro pedaço receberá a entrada inteira. Podemos descartar essa divisão quando T não gera a palavra vazia. Em uma gramática que permite essa derivação, descartá-la sem outro tratamento pode perder análises.

As divisões juntam-se de volta na entradatheorem append_of_mem_split2 {α : Type} : ∀ {xs : List α} {p : List α × List α}, p ∈ split2 xs → 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 ∈ split2 xs ∧ (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) ∈ split2 xs⊢ (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 :: xs All goals completed! 🐙 α:Typex:αxs:List αys:List αzs:List αh:(ys, zs) ∈ split2 xs⊢ (x :: (ys, zs).fst, (ys, zs).snd).fst ++ (x :: (ys, zs).fst, (ys, zs).snd).snd = x :: xs All goals completed! 🐙 theorem flatten_of_mem_splitN {α : Type} : ∀ {n : Nat} {xs : List α} {l : List (List α)}, l ∈ splitN n xs → l.flatten = xs α:Typex✝:List αl:List (List α)h:l ∈ splitN 1 x✝⊢ l.flatten = x✝α:Typel:List (List α)h:l ∈ splitN 0 []⊢ l.flatten = [] α:Typex✝:List αl:List (List α)h:l ∈ splitN 1 x✝⊢ 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✝ ∈ splitN 0 (head✝ :: tail✝)⊢ x✝.flatten = head✝ :: tail✝ α:Typehead✝:αtail✝:List αx✝:List (List α)h:x✝ ∈ splitN 0 (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 ∈ split2 xs ∧ ∃ 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) ∈ split2 xsrs:List (List α)h2:rs ∈ splitN (n + 1) (ys, zs).snd⊢ ((ys, zs).fst :: rs).flatten = xs All goals completed! 🐙
def fail to show termination for Parsing.recognize₀ with errors failed to infer structural recursion: Cannot use parameter xs: failed to eliminate recursive application recognize₀ ys failed to prove termination, possible solutions: - Use `have`-expressions to prove the remaining goals - Use `termination_by` to specify a different well-founded relation - Use `decreasing_by` to specify your own tactic for discharging this kind of goal xs ys:List Char⊢ sizeOf ys < sizeOf xsrecognize₀ (xs : List Char) : Bool := xs == [] || xs == ['a'] || xs == ['b'] || xs == ['c'] || (splitN 3 xs).any fun | [['a'], ys, ['a']] => recognize₀ ys | [['b'], ys, ['b']] => recognize₀ ys | [['c'], ys, ['c']] => recognize₀ ys | _ => false def recognize (xs : List Char) : Bool := xs == [] || xs == ['a'] || xs == ['b'] || xs == ['c'] || (splitN 3 xs).attach.any fun | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => recognize ys | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => recognize ys | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => recognize ys | _ => false termination_by xs.length decreasing_by all_goals xs:List Charys:List Charh:[['c'], ys, ['c']] ∈ splitN 3 xsthis:[['c'], ys, ['c']].flatten.length = xs.length⊢ ys.length < xs.length xs:List Charys:List Charh:[['c'], ys, ['c']] ∈ splitN 3 xsthis:ys.length + 1 + 1 = xs.length⊢ ys.length < xs.length All goals completed! 🐙 true#eval recognize "aabcbbcbaa".toList false#eval recognize "aabcbbcba".toList

Podemos usar recognize para gerar palavras da linguagem. Primeiro enumeramos as palavras sobre um alfabeto dado e depois conservamos apenas as que o reconhecedor aceita.

A função generate n alphabet enumera as palavras de comprimento n. A única palavra de comprimento zero é a lista vazia. Para obter palavras de comprimento n + 1, a função antepõe cada símbolo do alfabeto a cada palavra de comprimento n. Como há palíndromos de comprimento arbitrário, fixamos um limite para que a enumeração caiba em uma lista finita. A função generateUpTo n alphabet reúne as palavras dos comprimentos de zero a n. A função language filtra essa lista com recognize.

def generate {α : Type} : Nat → List α → List (List α) | 0, _ => [[]] | n + 1, alphabet => alphabet.flatMap fun x => (generate n alphabet).map (x :: ·) def generateUpTo {α : Type} (n : Nat) (alphabet : List α) : List (List α) := (List.range (n + 1)).flatMap fun k => generate k alphabet def language (n : Nat) (alphabet : List Char) : List (List Char) := (generateUpTo n alphabet).filter recognize ["", "a", "b", "c", "aa", "bb", "cc", "aaa", "aba", "aca", "bab", "bbb", "bcb", "cac", "cbc", "ccc"]#eval language 3 "abc".toList |>.map String.ofList

O Mathlib representa a propriedade de ser palíndromo pelo predicado indutivo List.Palindrome. A lista vazia e as listas de um elemento são palíndromos. Se l é um palíndromo, acrescentar o mesmo elemento x às duas pontas produz outro, x :: (l ++ [x]). Esses casos correspondem às regras da nossa gramática, com a diferença de que o predicado permite qualquer elemento nas pontas.

O teorema recognize_iff_palindrome diz que recognize concorda com esse predicado para toda palavra w sobre {a, b, c}. Para listas, w ⊆ "abc".toList significa que cada elemento de w pertence a "abc".toList. Essa hipótese é necessária para garantir que todo palíndromo seja aceito. Por exemplo, xx é um palíndromo, mas contém um símbolo fora do alfabeto do reconhecedor.

A prova trata uma direção de cada vez, por indução em um limite para o comprimento da palavra. Na primeira direção, cada sucesso do reconhecedor corresponde a um dos casos de List.Palindrome. Na segunda, a forma do palíndromo determina uma divisão que o reconhecedor precisa testar. As equações de recognize podem ser usadas nas duas provas porque sua terminação foi demonstrada.

O reconhecedor e a definição de palíndromotheorem mem_split2_append {α : Type} : ∀ ys zs : 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! 🐙 theorem mem_splitN_flatten {α : Type} : ∀ l : List (List α), l ∈ splitN l.length l.flatten α:Type⊢ [] ∈ splitN [].length [].flatten α:Type⊢ [] ∈ splitN [].length [].flatten All goals completed! 🐙 α:Typeys:List α⊢ [ys] ∈ splitN [ys].length [ys].flatten α:Typeys:List α⊢ [ys] ∈ splitN [ys].length [ys].flatten All 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 :: rs refine ⟨(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! 🐙 theorem recognize_sound (n : Nat) : ∀ w : List Char, w.length ≤ n → recognize w → w.Palindrome := n:Nat⊢ ∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindrome induction n with ⊢ ∀ (w : List Char), w.length ≤ 0 → recognize w = true → w.Palindrome w:List Charhw:w.length ≤ 0hr:recognize w = true⊢ w.Palindrome w:List Charhr:recognize w = truehw:w = []⊢ w.Palindrome w:List Charhr:recognize w = truehw:w = []⊢ [].Palindrome All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindrome⊢ ∀ (w : List Char), w.length ≤ n + 1 → recognize w = true → w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1h:recognize w = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1h:(w == [] || w == ['a'] || w == ['b'] || w == ['c'] || (splitN 3 w).attach.any fun x => match x with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1h:(((w = [] ∨ w = ['a']) ∨ w = ['b']) ∨ w = ['c']) ∨ ∃ x, x ∈ (splitN 3 w).attach ∧ (match x with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:[].length ≤ n + 1⊢ [].Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['a'].length ≤ n + 1⊢ ['a'].Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['b'].length ≤ n + 1⊢ ['b'].Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['c'].length ≤ n + 1⊢ ['c'].Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachhm:(match ⟨l, hl⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:[].length ≤ n + 1⊢ [].Palindrome All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['a'].length ≤ n + 1⊢ ['a'].Palindrome All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['b'].length ≤ n + 1⊢ ['b'].Palindrome All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromehw:['c'].length ≤ n + 1⊢ ['c'].Palindrome All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachhm:(match ⟨l, hl⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['a'], ys✝, ['a']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['a'], ys✝, ['a']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['b'], ys✝, ['b']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['b'], ys✝, ['b']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝³:{ x // x ∈ splitN 3 w }x✝²:∀ (ys : List Char) (h : [['a'], ys, ['a']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['a'], ys, ['a']], h⟩ → Falsex✝¹:∀ (ys : List Char) (h : [['b'], ys, ['b']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['b'], ys, ['b']], h⟩ → Falsex✝:∀ (ys : List Char) (h : [['c'], ys, ['c']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['c'], ys, ['c']], h⟩ → Falsehm:false = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['a'], ys✝, ['a']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['a'], ys✝, ['a']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['b'], ys✝, ['b']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['b'], ys✝, ['b']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝³:{ x // x ∈ splitN 3 w }x✝²:∀ (ys : List Char) (h : [['a'], ys, ['a']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['a'], ys, ['a']], h⟩ → Falsex✝¹:∀ (ys : List Char) (h : [['b'], ys, ['b']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['b'], ys, ['b']], h⟩ → Falsex✝:∀ (ys : List Char) (h : [['c'], ys, ['c']] ∈ splitN 3 w), ⟨l, hl⟩ = ⟨[['c'], ys, ['c']], h⟩ → Falsehm:false = true⊢ w.Palindrome (try All goals completed! 🐙) n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['a'], ys✝, ['a']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['a'], ys✝, ['a']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['b'], ys✝, ['b']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['b'], ys✝, ['b']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindromen:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys✝:List Charh✝:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys:List Charhys:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = true⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys:List Charhys:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = truehe:[['c'], ys, ['c']].flatten = w⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromew:List Charhw:w.length ≤ n + 1l:List (List Char)hl:l ∈ splitN 3 wleft✝:⟨l, hl⟩ ∈ (splitN 3 w).attachx✝:{ x // x ∈ splitN 3 w }ys:List Charhys:[['c'], ys✝, ['c']] ∈ splitN 3 wheq✝:⟨l, hl⟩ = ⟨[['c'], ys✝, ['c']], h✝⟩hm:recognize ys✝ = truehe:'c' :: (ys ++ ['c']) = w⊢ w.Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromel:List (List Char)ys:List Charhm:recognize ys✝ = truehw:('c' :: (ys ++ ['c'])).length ≤ n + 1hl:l ∈ splitN 3 ('c' :: (ys ++ ['c']))left✝:⟨l, hl⟩ ∈ (splitN 3 ('c' :: (ys ++ ['c']))).attachx✝:{ x // x ∈ splitN 3 ('c' :: (ys ++ ['c'])) }hys:[['c'], ys, ['c']] ∈ splitN 3 ('c' :: (ys ++ ['c']))heq✝:⟨l, hl⟩ = ⟨[['c'], ys, ['c']], hys⟩⊢ ('c' :: (ys ++ ['c'])).Palindrome n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromel:List (List Char)ys:List Charhm:recognize ys✝ = truehw:('c' :: (ys ++ ['c'])).length ≤ n + 1hl:l ∈ splitN 3 ('c' :: (ys ++ ['c']))left✝:⟨l, hl⟩ ∈ (splitN 3 ('c' :: (ys ++ ['c']))).attachx✝:{ x // x ∈ splitN 3 ('c' :: (ys ++ ['c'])) }hys:[['c'], ys, ['c']] ∈ splitN 3 ('c' :: (ys ++ ['c']))heq✝:⟨l, hl⟩ = ⟨[['c'], ys, ['c']], hys⟩⊢ ys.Palindrome exact ih ys (n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromel:List (List Char)ys:List Charhm:recognize ys✝ = truehw:('c' :: (ys ++ ['c'])).length ≤ n + 1hl:l ∈ splitN 3 ('c' :: (ys ++ ['c']))left✝:⟨l, hl⟩ ∈ (splitN 3 ('c' :: (ys ++ ['c']))).attachx✝:{ x // x ∈ splitN 3 ('c' :: (ys ++ ['c'])) }hys:[['c'], ys, ['c']] ∈ splitN 3 ('c' :: (ys ++ ['c']))heq✝:⟨l, hl⟩ = ⟨[['c'], ys, ['c']], hys⟩⊢ ys.length ≤ n n:Natih:∀ (w : List Char), w.length ≤ n → recognize w = true → w.Palindromel:List (List Char)ys:List Charhm:recognize ys✝ = truehl:l ∈ splitN 3 ('c' :: (ys ++ ['c']))left✝:⟨l, hl⟩ ∈ (splitN 3 ('c' :: (ys ++ ['c']))).attachx✝:{ x // x ∈ splitN 3 ('c' :: (ys ++ ['c'])) }hys:[['c'], ys, ['c']] ∈ splitN 3 ('c' :: (ys ++ ['c']))heq✝:⟨l, hl⟩ = ⟨[['c'], ys, ['c']], hys⟩hw:ys.length + 1 ≤ n⊢ ys.length ≤ n; All goals completed! 🐙) hm theorem recognize_complete (n : Nat) : ∀ w : List Char, w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = true := n:Nat⊢ ∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = true induction n with ⊢ ∀ (w : List Char), w.length ≤ 0 → w ⊆ "abc".toList → w.Palindrome → recognize w = true w:List Charhw:w.length ≤ 0a✝¹:w ⊆ "abc".toLista✝:w.Palindrome⊢ recognize w = true w:List Chara✝¹:w ⊆ "abc".toLista✝:w.Palindromehw:w = []⊢ recognize w = true a✝¹:[] ⊆ "abc".toLista✝:[].Palindrome⊢ recognize [] = true a✝¹:[] ⊆ "abc".toLista✝:[].Palindrome⊢ ([] == [] || [] == ['a'] || [] == ['b'] || [] == ['c'] || (splitN 3 []).attach.any fun x => match x with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = true⊢ ∀ (w : List Char), w.length ≤ n + 1 → w ⊆ "abc".toList → w.Palindrome → recognize w = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truew:List Charhw:w.length ≤ n + 1ha:w ⊆ "abc".toListhp:w.Palindrome⊢ recognize w = true cases hp with n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:[].length ≤ n + 1ha:[] ⊆ "abc".toList⊢ recognize [] = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:[].length ≤ n + 1ha:[] ⊆ "abc".toList⊢ ([] == [] || [] == ['a'] || [] == ['b'] || [] == ['c'] || (splitN 3 []).attach.any fun x => match x with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true All goals completed! 🐙 n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charhw:[x].length ≤ n + 1ha:[x] ⊆ "abc".toList⊢ recognize [x] = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charhw:[x].length ≤ n + 1ha:[x] ⊆ "abc".toListhx:x ∈ "abc".toList⊢ recognize [x] = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charhw:[x].length ≤ n + 1ha:[x] ⊆ "abc".toListhx:x = 'a' ∨ x = 'b' ∨ x = 'c'⊢ recognize [x] = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['a'].length ≤ n + 1ha:['a'] ⊆ "abc".toList⊢ recognize ['a'] = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['b'].length ≤ n + 1ha:['b'] ⊆ "abc".toList⊢ recognize ['b'] = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['c'].length ≤ n + 1ha:['c'] ⊆ "abc".toList⊢ recognize ['c'] = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['a'].length ≤ n + 1ha:['a'] ⊆ "abc".toList⊢ recognize ['a'] = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['b'].length ≤ n + 1ha:['b'] ⊆ "abc".toList⊢ recognize ['b'] = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['c'].length ≤ n + 1ha:['c'] ⊆ "abc".toList⊢ recognize ['c'] = true (n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truehw:['c'].length ≤ n + 1ha:['c'] ⊆ "abc".toList⊢ (['c'] == [] || ['c'] == ['a'] || ['c'] == ['b'] || ['c'] == ['c'] || (splitN 3 ['c']).attach.any fun x => match x with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true; All goals completed! 🐙) n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl✝:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toList⊢ recognize (x :: (l✝ ++ [x])) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toList⊢ recognize (x :: (l✝ ++ [x])) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toList⊢ recognize (x :: (l ++ [x])) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toList⊢ recognize (x :: (l ++ [x])) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = true⊢ recognize (x :: (l ++ [x])) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = true⊢ (x :: (l ++ [x]) == [] || x :: (l ++ [x]) == ['a'] || x :: (l ++ [x]) == ['b'] || x :: (l ++ [x]) == ['c'] || (splitN 3 (x :: (l ++ [x]))).attach.any fun x_1 => match x_1 with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = true⊢ (((x :: (l ++ [x]) = [] ∨ x :: (l ++ [x]) = ['a']) ∨ x :: (l ++ [x]) = ['b']) ∨ x :: (l ++ [x]) = ['c']) ∨ ∃ x_1, x_1 ∈ (splitN 3 (x :: (l ++ [x]))).attach ∧ (match x_1 with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = true⊢ ∃ x_1, x_1 ∈ (splitN 3 (x :: (l ++ [x]))).attach ∧ (match x_1 with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = truehmem:[[x], l, [x]] ∈ splitN 3 (x :: (l ++ [x]))⊢ ∃ x_1, x_1 ∈ (splitN 3 (x :: (l ++ [x]))).attach ∧ (match x_1 with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhx:x ∈ "abc".toListhl':l ⊆ "abc".toListih':recognize l = truehmem:[[x], l, [x]] ∈ splitN 3 (x :: (l ++ [x]))⊢ (match ⟨[[x], l, [x]], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truex:Charl:List Charhl:l✝.Palindromehw:(x :: (l✝ ++ [x])).length ≤ n + 1ha:x :: (l✝ ++ [x]) ⊆ "abc".toListhl':l ⊆ "abc".toListih':recognize l = truehmem:[[x], l, [x]] ∈ splitN 3 (x :: (l ++ [x]))hx:x = 'a' ∨ x = 'b' ∨ x = 'c'⊢ (match ⟨[[x], l, [x]], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('a' :: (l ++ ['a'])).length ≤ n + 1ha:'a' :: (l ++ ['a']) ⊆ "abc".toListhmem:[['a'], l, ['a']] ∈ splitN 3 ('a' :: (l ++ ['a']))⊢ (match ⟨[['a'], l, ['a']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('b' :: (l ++ ['b'])).length ≤ n + 1ha:'b' :: (l ++ ['b']) ⊆ "abc".toListhmem:[['b'], l, ['b']] ∈ splitN 3 ('b' :: (l ++ ['b']))⊢ (match ⟨[['b'], l, ['b']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('c' :: (l ++ ['c'])).length ≤ n + 1ha:'c' :: (l ++ ['c']) ⊆ "abc".toListhmem:[['c'], l, ['c']] ∈ splitN 3 ('c' :: (l ++ ['c']))⊢ (match ⟨[['c'], l, ['c']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true n:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('a' :: (l ++ ['a'])).length ≤ n + 1ha:'a' :: (l ++ ['a']) ⊆ "abc".toListhmem:[['a'], l, ['a']] ∈ splitN 3 ('a' :: (l ++ ['a']))⊢ (match ⟨[['a'], l, ['a']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('b' :: (l ++ ['b'])).length ≤ n + 1ha:'b' :: (l ++ ['b']) ⊆ "abc".toListhmem:[['b'], l, ['b']] ∈ splitN 3 ('b' :: (l ++ ['b']))⊢ (match ⟨[['b'], l, ['b']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = truen:Natih:∀ (w : List Char), w.length ≤ n → w ⊆ "abc".toList → w.Palindrome → recognize w = truel:List Charhl:l✝.Palindromehl':l ⊆ "abc".toListih':recognize l = truehw:('c' :: (l ++ ['c'])).length ≤ n + 1ha:'c' :: (l ++ ['c']) ⊆ "abc".toListhmem:[['c'], l, ['c']] ∈ splitN 3 ('c' :: (l ++ ['c']))⊢ (match ⟨[['c'], l, ['c']], hmem⟩ with | ⟨[['a'], ys, ['a']], h⟩ => recognize ys | ⟨[['b'], ys, ['b']], h⟩ => recognize ys | ⟨[['c'], ys, ['c']], h⟩ => recognize ys | x => false) = true All goals completed! 🐙 theorem recognize_iff_palindrome (w : List Char) (hw : w ⊆ "abc".toList) : recognize w ↔ w.Palindrome := ⟨recognize_sound _ w (Nat.le_refl _), recognize_complete _ w (Nat.le_refl _) hw⟩

Para construir as árvores que a gramática atribui a uma palavra, seguimos as mesmas regras usadas no reconhecimento. A entrada continua sendo uma lista de caracteres. A análise devolve uma lista de árvores de tipo ParseTree Char Char, com caracteres nas folhas e o rótulo 'A' nos nós internos.

Cada uso de uma regra produz um nó. A regra A → ε produz um nó sem filhas, e uma regra como A → a produz um nó com uma folha. Para A → a A a, percorremos as divisões com ['a'] nas duas pontas. Para cada árvore obtida ao analisar o pedaço central, construímos uma árvore com essa subárvore entre duas folhas com o caractere a. A justificativa de que a chamada recursiva recebe uma palavra menor é a mesma usada para recognize.

O reconhecedor pode parar assim que uma regra der certo. Para analisar a palavra, reunimos com ++ os resultados das regras e usamos List.flatMap para reunir os resultados das divisões. Se a palavra não pertence à linguagem, a lista de árvores é vazia. Se a gramática atribui mais de uma árvore à palavra, a lista contém todas elas.

def parse (xs : List Char) : List (ParseTree Char Char) := (if xs == [] then [.branch 'A' []] else []) ++ (if xs == ['a'] then [.branch 'A' [.leaf 'a']] else []) ++ (if xs == ['b'] then [.branch 'A' [.leaf 'b']] else []) ++ (if xs == ['c'] then [.branch 'A' [.leaf 'c']] else []) ++ (splitN 3 xs).attach.flatMap fun | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => (parse ys).map fun t => .branch 'A' [.leaf 'a', t, .leaf 'a'] | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => (parse ys).map fun t => .branch 'A' [.leaf 'b', t, .leaf 'b'] | ⟨[['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] _h Note: This linter can be disabled with `set_option linter.unusedVariables false`h⟩ => (parse ys).map fun t => .branch 'A' [.leaf 'c', t, .leaf 'c'] | _ => [] termination_by xs.length decreasing_by all_goals xs:List Charys:List Charh:[['c'], ys, ['c']] ∈ splitN 3 xsthis:[['c'], ys, ['c']].flatten.length = xs.length⊢ ys.length < xs.length xs:List Charys:List Charh:[['c'], ys, ['c']] ∈ splitN 3 xsthis:ys.length + 1 + 1 = xs.length⊢ ys.length < xs.length All goals completed! 🐙 [[.A ]] #eval IO.println (parse "".toList) [] #eval IO.println (parse "aab".toList) [[.A a [.A a [.A b] a] a]] #eval IO.println (parse "aabaa".toList)
Árvores mais enxutas

Como a gramática tem um só não terminal, poderíamos omitir o nó A na regra A → a e devolver só a folha a. Nenhuma informação se perderia, porque o único rótulo possível é A. Mas a árvore deixaria de ter um nó para cada regra usada, e a correspondência entre a gramática e o parser ficaria menos direta. Na regra A → ε nem há essa opção pois uma árvore é uma folha ou um nó, sem o nó A, não sobra nada para devolver. Por isso mantemos um nó para cada regra.

Exercício★★(split-nonempty)

Numa gramática sem regras com ε, 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".

def declaration uses `sorry`split2' {α : Type} : List α → List (List α × List α) | [] | [_] => [] | x :: y :: ys => sorry def declaration uses `sorry`splitN' {α : Type} : Nat → List α → List (List (List α)) | 0, [] => [[]] | 0, _ :: _ => [] | 1, [] => [] | 1, xs => [[xs]] | n + 2, xs => sorry theorem declaration uses `sorry`split2'_jan : split2' "Jan".toList = [(['J'], ['a', 'n']), (['J', 'a'], ['n'])] := ⊢ split2' "Jan".toList = [(['J'], ['a', 'n']), (['J', 'a'], ['n'])] All goals completed! 🐙 theorem declaration uses `sorry`splitN'_jan : splitN' 3 "Jan".toList = [[['J'], ['a'], ['n']]] := ⊢ splitN' 3 "Jan".toList = [[['J'], ['a'], ['n']]] All goals completed! 🐙
end Parsing