Documentation

Mathlib.Computability.Language

Languages #

This file contains the definition and operations on formal languages over an alphabet. Note that "strings" are implemented as lists over the alphabet. Union and concatenation define a Kleene algebra over the languages. In addition to that, we define a reversal of a language and prove that it behaves well with respect to other language operations.

def Language (α : Type u_4) :
Type u_4

A language is a set of strings over an alphabet.

Equations
Instances For
    instance instMembershipListLanguage {α : Type u_1} :
    Equations
    • instMembershipListLanguage = { mem := Set.Mem }
    instance instSingletonListLanguage {α : Type u_1} :
    Equations
    • instSingletonListLanguage = { singleton := Set.singleton }
    instance instInsertListLanguage {α : Type u_1} :
    Insert (List α) (Language α)
    Equations
    • instInsertListLanguage = { insert := Set.insert }
    Equations
    • instCompleteAtomicBooleanAlgebraLanguage = Set.completeAtomicBooleanAlgebra
    instance Language.instZero {α : Type u_1} :

    Zero language has no elements.

    Equations
    • Language.instZero = { zero := }
    instance Language.instOne {α : Type u_1} :

    1 : Language α contains only one element [].

    Equations
    • Language.instOne = { one := {[]} }
    instance Language.instInhabited {α : Type u_1} :
    Equations
    • Language.instInhabited = { default := }
    instance Language.instAdd {α : Type u_1} :

    The sum of two languages is their union.

    Equations
    • Language.instAdd = { add := fun (x1 x2 : Set (List α)) => x1 x2 }
    instance Language.instMul {α : Type u_1} :

    The product of two languages l and m is the language made of the strings x ++ y where x ∈ l and y ∈ m.

    Equations
    theorem Language.zero_def {α : Type u_1} :
    0 =
    theorem Language.one_def {α : Type u_1} :
    1 = {[]}
    theorem Language.add_def {α : Type u_1} (l : Language α) (m : Language α) :
    l + m = l m
    theorem Language.mul_def {α : Type u_1} (l : Language α) (m : Language α) :
    l * m = Set.image2 (fun (x1 x2 : List α) => x1 ++ x2) l m
    instance Language.instKStar {α : Type u_1} :

    The Kleene star of a language L is the set of all strings which can be written by concatenating strings from L.

    Equations
    theorem Language.kstar_def {α : Type u_1} (l : Language α) :
    KStar.kstar l = {x : List α | ∃ (L : List (List α)), x = L.join yL, y l}
    theorem Language.ext_iff {α : Type u_1} {l : Language α} {m : Language α} :
    l = m ∀ (x : List α), x l x m
    theorem Language.ext {α : Type u_1} {l : Language α} {m : Language α} (h : ∀ (x : List α), x l x m) :
    l = m
    @[simp]
    theorem Language.not_mem_zero {α : Type u_1} (x : List α) :
    x0
    @[simp]
    theorem Language.mem_one {α : Type u_1} (x : List α) :
    x 1 x = []
    theorem Language.nil_mem_one {α : Type u_1} :
    [] 1
    theorem Language.mem_add {α : Type u_1} (l : Language α) (m : Language α) (x : List α) :
    x l + m x l x m
    theorem Language.mem_mul {α : Type u_1} {l : Language α} {m : Language α} {x : List α} :
    x l * m al, bm, a ++ b = x
    theorem Language.append_mem_mul {α : Type u_1} {l : Language α} {m : Language α} {a : List α} {b : List α} :
    a lb ma ++ b l * m
    theorem Language.mem_kstar {α : Type u_1} {l : Language α} {x : List α} :
    x KStar.kstar l ∃ (L : List (List α)), x = L.join yL, y l
    theorem Language.join_mem_kstar {α : Type u_1} {l : Language α} {L : List (List α)} (h : yL, y l) :
    L.join KStar.kstar l
    theorem Language.nil_mem_kstar {α : Type u_1} (l : Language α) :
    instance Language.instSemiring {α : Type u_1} :
    Equations
    • Language.instSemiring = Semiring.mk npowRec
    @[simp]
    theorem Language.add_self {α : Type u_1} (l : Language α) :
    l + l = l
    def Language.map {α : Type u_1} {β : Type u_2} (f : αβ) :

    Maps the alphabet of a language.

    Equations
    Instances For
      @[simp]
      theorem Language.map_id {α : Type u_1} (l : Language α) :
      (Language.map id) l = l
      @[simp]
      theorem Language.map_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} (g : βγ) (f : αβ) (l : Language α) :
      theorem Language.mem_kstar_iff_exists_nonempty {α : Type u_1} {l : Language α} {x : List α} :
      x KStar.kstar l ∃ (S : List (List α)), x = S.join yS, y l y []
      theorem Language.kstar_def_nonempty {α : Type u_1} (l : Language α) :
      KStar.kstar l = {x : List α | ∃ (S : List (List α)), x = S.join yS, y l y []}
      theorem Language.le_iff {α : Type u_1} (l : Language α) (m : Language α) :
      l m l + m = m
      theorem Language.le_mul_congr {α : Type u_1} {l₁ : Language α} {l₂ : Language α} {m₁ : Language α} {m₂ : Language α} :
      l₁ m₁l₂ m₂l₁ * l₂ m₁ * m₂
      theorem Language.le_add_congr {α : Type u_1} {l₁ : Language α} {l₂ : Language α} {m₁ : Language α} {m₂ : Language α} :
      l₁ m₁l₂ m₂l₁ + l₂ m₁ + m₂
      theorem Language.mem_iSup {α : Type u_1} {ι : Sort v} {l : ιLanguage α} {x : List α} :
      x ⨆ (i : ι), l i ∃ (i : ι), x l i
      theorem Language.iSup_mul {α : Type u_1} {ι : Sort v} (l : ιLanguage α) (m : Language α) :
      (⨆ (i : ι), l i) * m = ⨆ (i : ι), l i * m
      theorem Language.mul_iSup {α : Type u_1} {ι : Sort v} (l : ιLanguage α) (m : Language α) :
      m * ⨆ (i : ι), l i = ⨆ (i : ι), m * l i
      theorem Language.iSup_add {α : Type u_1} {ι : Sort v} [Nonempty ι] (l : ιLanguage α) (m : Language α) :
      (⨆ (i : ι), l i) + m = ⨆ (i : ι), l i + m
      theorem Language.add_iSup {α : Type u_1} {ι : Sort v} [Nonempty ι] (l : ιLanguage α) (m : Language α) :
      m + ⨆ (i : ι), l i = ⨆ (i : ι), m + l i
      theorem Language.mem_pow {α : Type u_1} {l : Language α} {x : List α} {n : } :
      x l ^ n ∃ (S : List (List α)), x = S.join S.length = n yS, y l
      theorem Language.kstar_eq_iSup_pow {α : Type u_1} (l : Language α) :
      KStar.kstar l = ⨆ (i : ), l ^ i
      @[simp]
      theorem Language.map_kstar {α : Type u_1} {β : Type u_2} (f : αβ) (l : Language α) :
      Equations
      def Language.reverse {α : Type u_1} (l : Language α) :

      Language l.reverse is defined as the set of words from l backwards.

      Equations
      • l.reverse = {w : List α | w.reverse l}
      Instances For
        @[simp]
        theorem Language.mem_reverse {α : Type u_1} {l : Language α} {a : List α} :
        a l.reverse a.reverse l
        theorem Language.reverse_mem_reverse {α : Type u_1} {l : Language α} {a : List α} :
        a.reverse l.reverse a l
        theorem Language.reverse_eq_image {α : Type u_1} (l : Language α) :
        l.reverse = List.reverse '' l
        @[simp]
        @[simp]
        theorem Language.reverse_involutive {α : Type u_1} :
        Function.Involutive Language.reverse
        theorem Language.reverse_bijective {α : Type u_1} :
        Function.Bijective Language.reverse
        theorem Language.reverse_injective {α : Type u_1} :
        Function.Injective Language.reverse
        theorem Language.reverse_surjective {α : Type u_1} :
        Function.Surjective Language.reverse
        @[simp]
        theorem Language.reverse_reverse {α : Type u_1} (l : Language α) :
        l.reverse.reverse = l
        @[simp]
        theorem Language.reverse_add {α : Type u_1} (l : Language α) (m : Language α) :
        (l + m).reverse = l.reverse + m.reverse
        @[simp]
        theorem Language.reverse_mul {α : Type u_1} (l : Language α) (m : Language α) :
        (l * m).reverse = m.reverse * l.reverse
        @[simp]
        theorem Language.reverse_iSup {α : Type u_1} {ι : Sort u_4} (l : ιLanguage α) :
        (⨆ (i : ι), l i).reverse = ⨆ (i : ι), (l i).reverse
        @[simp]
        theorem Language.reverse_iInf {α : Type u_1} {ι : Sort u_4} (l : ιLanguage α) :
        (⨅ (i : ι), l i).reverse = ⨅ (i : ι), (l i).reverse
        @[simp]
        theorem Language.reverseIso_symm_apply (α : Type u_1) (l' : (Language α)ᵐᵒᵖ) :
        (Language.reverseIso α).symm l' = (MulOpposite.unop l').reverse
        @[simp]
        theorem Language.reverseIso_apply (α : Type u_1) (l : Language α) :

        Language.reverse as a ring isomorphism to the opposite ring.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[simp]
          theorem Language.reverse_pow {α : Type u_1} (l : Language α) (n : ) :
          (l ^ n).reverse = l.reverse ^ n
          @[simp]
          theorem Language.reverse_kstar {α : Type u_1} (l : Language α) :
          (KStar.kstar l).reverse = KStar.kstar l.reverse
          inductive Symbol (T : Type u_1) (N : Type u_2) :
          Type (max u_1 u_2)

          Symbols for use by all kinds of grammars.

          • terminal: {T : Type u_1} → {N : Type u_2} → TSymbol T N

            Terminal symbols (of the same type as the language)

          • nonterminal: {T : Type u_1} → {N : Type u_2} → NSymbol T N

            Nonterminal symbols (must not be present at the end of word being generated)

          Instances For
            instance instDecidableEqSymbol :
            {T : Type u_4} → {N : Type u_5} → [inst : DecidableEq T] → [inst : DecidableEq N] → DecidableEq (Symbol T N)
            Equations
            • instDecidableEqSymbol = decEqSymbol✝
            instance instReprSymbol :
            {T : Type u_4} → {N : Type u_5} → [inst : Repr T] → [inst : Repr N] → Repr (Symbol T N)
            Equations
            • instReprSymbol = { reprPrec := reprSymbol✝ }
            instance instFintypeSymbol :
            {T : Type u_4} → {N : Type u_5} → [inst : Fintype T] → [inst : Fintype N] → Fintype (Symbol T N)
            Equations